HashMap和HashTable底層原理以及常見面試題

1．HashMap VS HashTable

1.1.首先說(shuō)下 HashMap 的原理。

HashMap 的數(shù)據(jù)結(jié)構(gòu)

/**
The table, resized as necessary. Length MUST Always be a power of two.
**/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V>{
   final K key;
   V value;
    Entry<K,V> next;
    final int hash;
    ...
 }

HashMap存儲(chǔ)函數(shù)的實(shí)現(xiàn)put(K key, V value)

根據(jù)下面put方法的源代碼可以看出，當(dāng)程序試圖將一個(gè)key-value對(duì)放入HashMap中時(shí)

• 1.程序首先計(jì)算該key的hashCode()值
• 2.然后對(duì)該哈希碼值進(jìn)行再哈希
• 3.然后把哈希值和(數(shù)組長(zhǎng)度-1)進(jìn)行按位與操作，得到存儲(chǔ)的數(shù)組下標(biāo)
• 4.如果該位置處設(shè)有鏈表節(jié)點(diǎn)，那么就直接把包含<key,value>的節(jié)點(diǎn)放入該位置。如果該位置有結(jié)點(diǎn)，就對(duì)鏈表進(jìn)行遍歷，看是否有hash,key和要放入的節(jié)點(diǎn)相同的節(jié)點(diǎn)，如果有的話，就替換該節(jié)點(diǎn)的value值，如果沒有相同的話，就創(chuàng)建節(jié)點(diǎn)放入值，并把該節(jié)點(diǎn)插入到鏈表表頭(頭插法)。

public V put(K key, V value) {
 //HashMap允許存放null鍵和null值。
 //當(dāng)key為nu11時(shí)， 調(diào)用putForNullKey方法，將valve放置在數(shù)組第一個(gè)位置。
 if (key = null)
 return putForNullKey(value);
 //根據(jù)key的keyCode重新計(jì)算hash值。
 int hash = hash(key .hashCode());
 //搜索指定hash值在對(duì)應(yīng)table中的索
 int i = indexFor(hash, table . length);
 //如果i索引處的Entry不為null,通過循環(huán)不斷遍歷e元素的下一個(gè)元素。
 for (Entry<K,V> e = table[i]; e != null;e = e.next) {
  Object k;
  if (e.hash == hash && ((k == e.key) == key || key. equals(k))) {
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
  }
 }
 //如果讀引處的Entry為null，表明此處還沒有Entry
 omodCount++;
 //將key、 value添加到索引處。
 addEntry(hash, key, value, i);
 return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
 //獲取指定bucketIndex 索引處的Entry
 Entry<K,V> e = table[bucketIndex];
 //將新創(chuàng)健的Entry 放入bucketIndex索引處，并讓新的Entry 指向原來(lái)的Entry
 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
 //如果Hap中的key-value對(duì)的數(shù)里超過了極限
 if (size++ >= threshold)
 //把table對(duì)象的長(zhǎng)度擴(kuò)充到原理的2倍
  resize(2*table.length);
}

二倍擴(kuò)容

 void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  }

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
      while(null != e) {
        Entry<K,V> next = e.next;
        if (rehash) {
          e.hash = null == e.key ? 0 : hash(e.key);
        }
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
      }
    }
  }

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
  }

static int hash(int h){
 h ^ =(h>>>20)^ (h>>>12);
 return h ^ (h>>>7) ^ (h>>>4);
}

擴(kuò)展:為何數(shù)組的長(zhǎng)度是2的n次方呢?

1.這個(gè)方法非常巧妙，它通過h & (table.length-1)來(lái)得到該對(duì)象的保存位，而HashMap底層數(shù)組的長(zhǎng)度總是2的n次方，2^n -1得到的二進(jìn)制數(shù)的每個(gè)位上的值都為1,那么與全部為1的一一個(gè)數(shù)進(jìn)行與操作，速度會(huì)大大提升。

2.當(dāng)length總是2的n次方時(shí)，h& (length-1)運(yùn) 算等價(jià)王對(duì)length取模，也就是h%length,但是&比%縣有更高的效率。

3.當(dāng)數(shù)組長(zhǎng)度為2的n次冪的時(shí)候，不同的key算得的index相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說(shuō)碰擁的幾率小，相對(duì)的，查詢的時(shí)候就不用遍歷某個(gè)位置上的鏈表，這樣查詢效率也就較高了。

HashMap讀取函數(shù)的實(shí)現(xiàn)get

public V get(object key) {
   if (key = null)
   return getForNullKey();
   int hash ”hash(key.hashCode());
   for (Entry<K,V> e = table[indexFor(hash, table. length)];
    e!=null;
    e = e.next) {
    0bject k;
    if (e.hash=hash && ((k=e.key)==key II key.equals(k)){
    return e.value;
    }
   return null;
}

hashMap的get方法1. 是首先通過key的兩次hash后的值與數(shù)組的長(zhǎng)度-1進(jìn)行與操作，定位到數(shù)組的某個(gè)位置，2. 然后對(duì)該列的鏈表進(jìn)行遍歷，一般情況下，hashMap的這種查找速度是非?？斓模琱ash 值相同的元(O就會(huì)造成鏈表中數(shù)據(jù)很多，而鏈表中的數(shù)據(jù)查找是通過應(yīng)歷所有鏈表中的元素進(jìn)行的，這可能會(huì)影響到查找速度，找到即返回。特別注意:當(dāng)返回為null時(shí)，你不能判斷是沒有找到指定元素，還是在hashmap中存著一一個(gè)value為null的元素，因?yàn)閔ashmap允許value為null.

HashMap的擴(kuò)容機(jī)制:

當(dāng)HashMap中的結(jié)點(diǎn)個(gè)數(shù)超過數(shù)組大小loadEactor*(加載因子)時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容,loadFactor的默認(rèn)值為0.75.世就是說(shuō)，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap電結(jié)點(diǎn)個(gè)數(shù)超過160.75=12的時(shí)候，就把數(shù)組的大小和展為216=32,即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，并放進(jìn)去，而這是一個(gè)非常消耗性能的操作。

多線程下HashMap出現(xiàn)的問題:

1.多線程put操作后，get操作導(dǎo)致死循環(huán)導(dǎo)致cpu100%的現(xiàn)象。主要是多線程同時(shí)put時(shí)，如果同時(shí)觸發(fā)了rehash操作，會(huì)導(dǎo)政擴(kuò)客后的HashMap中的鏈表中出現(xiàn)循環(huán)節(jié)點(diǎn)進(jìn)而使得后面get的時(shí)候，會(huì)死循環(huán)。

2.多線程put操作，導(dǎo)致元素丟失，也是發(fā)生在個(gè)線程對(duì)hashmap 擴(kuò)容時(shí)。

2.hashTable的原理。

它的原理和hashMap基本一致。

3.HashMap和HashTable的區(qū)別。

1.Hashtable 是線程安全的，方法是Synchronized 的，適合在多線程環(huán)境中使用，效率稍低: HashMap不是線程安全的，方法不是Synchronized的，效率稍高，適合在單線程環(huán)境下使用，所以在多線程場(chǎng)合下使用的話，需要手動(dòng)同步HashMap，Collctions. synchronizedMap()。

PS:HashTable的效率比較低的原因?

在線程競(jìng)爭(zhēng)激烈的情況下HashTable的效率非常低下。因?yàn)楫?dāng)一個(gè)線程訪間HashTable的同步方法時(shí)，訪問其他同步方法的線程就可能會(huì)進(jìn)入阻嘉或者輪訓(xùn)狀態(tài)。如線程1使用put進(jìn)行添加元素，線程2不但不能使用put方法添加元素，并且也不能使用get方法來(lái)獲取元素，所以競(jìng)爭(zhēng)越激烈改率越低.

2.HashMap的key和value都可以為null值，HashTable 的key和value都不允許L Null值。

3.HashMap中數(shù)組的默認(rèn)大小是16，而且一定是2的倍數(shù)，擴(kuò)容后的數(shù)組長(zhǎng)度是之前數(shù)組長(zhǎng)度的2倍。HashTable中數(shù)組默認(rèn)大小是11.擴(kuò)容后的數(shù)組長(zhǎng)度是之前數(shù)組長(zhǎng)度的2倍+1。

4.哈希直的使用不同。

而HashMap重新計(jì)算hash值，面且用&代替求模:

int hash = hash(key.hashcode0);
int i= indexFor(hash, table.length);
static int hash(Objectx) {
 int h = x.hashCode();
 h += ~(h<<9);h^= (h>>> 14);
 h+=(h<< 4);
 h ^= (h>>> 10);
 returm h;
}

static int indexFor(int h, int length) {
 return h & (length-1); //hashmap的表長(zhǎng)永遠(yuǎn)是2^n。
}

HashTable直接使用對(duì)象的hashCode值:

int hash = key.hashCode(); //注意區(qū)分2者的hash值!! int index = (hash & 0x7FFFFFFF) % tab.length;

4.判斷是否含有某個(gè)鍵

在HashMap中，null 可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null,當(dāng)get()方法返回null值時(shí)，既可以表示HashMap中沒有該鍵，也可以表示該鍵所對(duì)應(yīng)的值為null。因此，在HashMap中不能用get()方法來(lái)判斷HashMap中是否存在某個(gè)鍵，而應(yīng)該用containsKey()方法來(lái)判析。Hashtable的鍵值都不能為null,所以可以用get()方 法來(lái)判斷是否含有某個(gè)鍵。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)億速云的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接