HashMap和HashTable底層原理以及常見面試題
1.HashMap VS HashTable
1.1.首先說下 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存儲函數(shù)的實現(xiàn)put(K key, V value)
根據(jù)下面put方法的源代碼可以看出,當程序試圖將一個key-value對放入HashMap中時
- 1.程序首先計算該key的hashCode()值
- 2.然后對該哈希碼值進行再哈希
- 3.然后把哈希值和(數(shù)組長度-1)進行按位與操作,得到存儲的數(shù)組下標
- 4.如果該位置處設有鏈表節(jié)點,那么就直接把包含<key,value>的節(jié)點放入該位置。如果該位置有結(jié)點,就對鏈表進行遍歷,看是否有hash,key和要放入的節(jié)點相同的節(jié)點,如果有的話,就替換該節(jié)點的value值,如果沒有相同的話,就創(chuàng)建節(jié)點放入值,并把該節(jié)點插入到鏈表表頭(頭插法)。
public V put(K key, V value) { //HashMap允許存放null鍵和null值。 //當key為nu11時, 調(diào)用putForNullKey方法,將valve放置在數(shù)組第一個位置。 if (key = null) return putForNullKey(value); //根據(jù)key的keyCode重新計算hash值。 int hash = hash(key .hashCode()); //搜索指定hash值在對應table中的索 int i = indexFor(hash, table . length); //如果i索引處的Entry不為null,通過循環(huán)不斷遍歷e元素的下一個元素。 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 指向原來的Entry table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //如果Hap中的key-value對的數(shù)里超過了極限 if (size++ >= threshold) //把table對象的長度擴充到原理的2倍 resize(2*table.length); }
二倍擴容
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); }
擴展:為何數(shù)組的長度是2的n次方呢?
1.這個方法非常巧妙,它通過h & (table.length-1)來得到該對象的保存位,而HashMap底層數(shù)組的長度總是2的n次方,2^n -1得到的二進制數(shù)的每個位上的值都為1,那么與全部為1的一一個數(shù)進行與操作,速度會大大提升。
2.當length總是2的n次方時,h& (length-1)運 算等價王對length取模,也就是h%length,但是&比%縣有更高的效率。
3.當數(shù)組長度為2的n次冪的時候,不同的key算得的index相同的幾率較小,那么數(shù)據(jù)在數(shù)組上分布就比較均勻,也就是說碰擁的幾率小,相對的,查詢的時候就不用遍歷某個位置上的鏈表,這樣查詢效率也就較高了。
HashMap讀取函數(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ù)組的長度-1進行與操作,定位到數(shù)組的某個位置,2. 然后對該列的鏈表進行遍歷,一般情況下,hashMap的這種查找速度是非??斓?,hash 值相同的元(O就會造成鏈表中數(shù)據(jù)很多,而鏈表中的數(shù)據(jù)查找是通過應歷所有鏈表中的元素進行的,這可能會影響到查找速度,找到即返回。特別注意:當返回為null時,你不能判斷是沒有找到指定元素,還是在hashmap中存著一一個value為null的元素,因為hashmap允許value為null.
HashMap的擴容機制:
當HashMap中的結(jié)點個數(shù)超過數(shù)組大小loadEactor*(加載因子)時,就會進行數(shù)組擴容,loadFactor的默認值為0.75.世就是說,默認情況下,數(shù)組大小為16,那么當HashMap電結(jié)點個數(shù)超過160.75=12的時候,就把數(shù)組的大小和展為216=32,即擴大一倍,然后重新計算每個元素在數(shù)組中的位置,并放進去,而這是一個非常消耗性能的操作。
多線程下HashMap出現(xiàn)的問題:
1.多線程put操作后,get操作導致死循環(huán)導致cpu100%的現(xiàn)象。主要是多線程同時put時,如果同時觸發(fā)了rehash操作,會導政擴客后的HashMap中的鏈表中出現(xiàn)循環(huán)節(jié)點進而使得后面get的時候,會死循環(huán)。
2.多線程put操作,導致元素丟失,也是發(fā)生在個線程對hashmap 擴容時。
2.hashTable的原理。
它的原理和hashMap基本一致。
3.HashMap和HashTable的區(qū)別。
1.Hashtable 是線程安全的,方法是Synchronized 的,適合在多線程環(huán)境中使用,效率稍低: HashMap不是線程安全的,方法不是Synchronized的,效率稍高,適合在單線程環(huán)境下使用,所以在多線程場合下使用的話,需要手動同步HashMap,Collctions. synchronizedMap()。
PS:HashTable的效率比較低的原因?
在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪間HashTable的同步方法時,訪問其他同步方法的線程就可能會進入阻嘉或者輪訓狀態(tài)。如線程1使用put進行添加元素,線程2不但不能使用put方法添加元素,并且也不能使用get方法來獲取元素,所以競爭越激烈改率越低.
2.HashMap的key和value都可以為null值,HashTable 的key和value都不允許L Null值。
3.HashMap中數(shù)組的默認大小是16,而且一定是2的倍數(shù),擴容后的數(shù)組長度是之前數(shù)組長度的2倍。HashTable中數(shù)組默認大小是11.擴容后的數(shù)組長度是之前數(shù)組長度的2倍+1。
4.哈希直的使用不同。
而HashMap重新計算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的表長永遠是2^n。 }
HashTable直接使用對象的hashCode值:
int hash = key.hashCode(); //注意區(qū)分2者的hash值!! int index = (hash & 0x7FFFFFFF) % tab.length;
4.判斷是否含有某個鍵
在HashMap中,null 可以作為鍵,這樣的鍵只有一個,可以有一個或多個鍵所對應的值為null,當get()方法返回null值時,既可以表示HashMap中沒有該鍵,也可以表示該鍵所對應的值為null。因此,在HashMap中不能用get()方法來判斷HashMap中是否存在某個鍵,而應該用containsKey()方法來判析。Hashtable的鍵值都不能為null,所以可以用get()方 法來判斷是否含有某個鍵。
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。如果你想了解更多相關內(nèi)容請查看下面相關鏈接
相關文章
InterProcessMutex實現(xiàn)zookeeper分布式鎖原理
本文主要介紹了InterProcessMutex實現(xiàn)zookeeper分布式鎖原理,文中根據(jù)實例編碼詳細介紹的十分詳盡,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-03-03一文探究ArrayBlockQueue函數(shù)及應用場景
這篇文章主要為大家介紹了一文探究ArrayBlockQueue函數(shù)及應用場景,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-03-03Java?stream?sorted使用?Comparator?進行多字段排序的方法
這篇文章主要介紹了Java?stream?sorted使用?Comparator?進行多字段排序,主要講解使用Java?Stream流排序器Comparator對List集合進行多字段排序的方法,包括復雜實體對象多字段升降序排序方法,需要的朋友可以參考下2023-03-03