一冯吓、HashMap
1.HashMap概述:
HashMap是基于哈希表的Map接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作,并允許使用null值和null鍵。此類不保證映射的順序融蹂,特別是它不保證該順序恒久不變。
2.HashMap的數(shù)據(jù)結(jié)構(gòu):
在Java編程語言中弄企,最基本的結(jié)構(gòu)就是兩種超燃,一個是數(shù)組,另外一個是模擬指針(引用)桩蓉,所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造淋纲,HashMap也不例外。HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)院究,即數(shù)組和鏈表的結(jié)合體洽瞬。如下圖,HashMap底層就是一個數(shù)組結(jié)構(gòu)业汰,數(shù)組中的每一項又是一個鏈表伙窃。當新建一個HashMap的時候,就會初始化一個數(shù)組样漆。
源碼:
/**
* 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;?
? ? ……?
}
Entry就是數(shù)組中的元素为障,每個Map.Entry其實就是一個Key-Value對,它持有一個指向下一個元素的引用放祟,這就構(gòu)成了鏈表鳍怨。
3.HashMap的存儲實現(xiàn):
public V put(K key, V value) {?
? ? // HashMap允許存放null鍵和null值。?
? ? // 當key為null時跪妥,調(diào)用putForNullKey方法鞋喇,將value放置在數(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;?
? ? ? ? }?
? ? }?
? ? // 如果i索引處的Entry為null罐韩,表明此處還沒有Entry。?
? ? modCount++;?
? ? // 將key污朽、value添加到i索引處散吵。?
? ? addEntry(hash, key, value, i);?
? ? return null;?
}?
從源碼得:當我們往HashMap中put元素時,先根據(jù)key的hashCode重新計算hash值蟆肆,根據(jù)hash值得到這個元素在數(shù)組的位置(下標)错蝴,如果數(shù)組該位置已經(jīng)存放了其他元素了,那么在這個位置上的元素將以鏈表的形式存放颓芭,新加入的放在鏈頭顷锰,最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素亡问,就直接將該元素放到此數(shù)組中的該位置上官紫。
addEntry(hash,key,value,i)方法根據(jù)計算出的hash值,將Key-Value對放在數(shù)組table的i索引處州藕。addEntry是HashMap提供的一個包訪問權(quán)限的方法束世,方法如下:
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);?
? ? // 如果 Map 中的 key-value 對的數(shù)量超過了極限?
? ? if (size++ >= threshold)?
? ? // 把 table 對象的長度擴充到原來的2倍床玻。?
? ? ? ? resize(2 * table.length);?
}?
當系統(tǒng)決定存儲HashMap中的Key-Value對時毁涉,完全沒有考慮Entry中的Value,僅僅只是根據(jù)key來計算并決定每個Entry的存儲位置锈死。即當系統(tǒng)決定了key的存儲位置之后贫堰,value隨之保存在那里即可穆壕。
hash(int h)方法根據(jù)key的hashCode重新計算一次散列。此算法加入了高位計算其屏,防止低位不變喇勋,高位變化時,造成的hash沖突偎行。
static int hash(int h) {?
? ? h ^= (h >>> 20) ^ (h >>> 12);?
? ? return h ^ (h >>> 7) ^ (h >>> 4);?
}?
我們得知在HashMap中要找到某個元素川背,需要根據(jù)key得到hash值來求得對應數(shù)組中的位置。如何計算這個位置就是hash算法蛤袒。上面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合熄云,所以我們當然希望這個HashMap中的元素位置盡量的分布均勻些,盡量使得每個位置上的元素數(shù)量只有一個妙真,那么當我們用hash算法求得這個位置的時候缴允,馬上就可以知道對應位置的元素就是我們要的,而不用再去遍歷鏈表隐孽,這樣就大大的優(yōu)化了查詢的效率癌椿。
對于任意給定的對象,只要它的HashCode()返回值相同菱阵,那么程序調(diào)用Hash(int h)方法所計算得到的hash值總是相同的踢俄。我們首先想到的就是把Hash值對數(shù)組的長度取模運算,這么一來晴及,元素的分布相對來說是比較均勻的都办。但是模運算的消耗還是比較大的,HashMap中:調(diào)用indexFor(int h,int length)方法來計算該對象應該保存在table數(shù)組的哪個索引處虑稼。
static int indexFor(int h, int length) {?
? ? return h & (length-1);?
}
HashMap底層數(shù)組的長度總是2的n次方琳钉,這是HashMap在速度上的優(yōu)化。
當數(shù)組長度為2的n次冪的時候蛛倦,不同的Key算得的index相同的幾率較小歌懒,那么數(shù)據(jù)在數(shù)組上分布就比較均勻,也就是碰撞的幾率·比較小溯壶。相對的及皂,查詢的時候就不用遍歷某個位置上的鏈表,這樣查詢的效率也就比較高了且改。
4.HashMap的讀取實現(xiàn):
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) {?
? ? ? ? Object k;?
? ? ? ? if (e.hash == hash && ((k = e.key) == key || key.equals(k)))?
? ? ? ? ? ? return e.value;?
? ? }?
? ? return null;?
}?
從HashMap中get元素時验烧,首先計算key的hashCode,找到數(shù)組中對應位置的某一個元素又跛,然后通過key的equals方法在對應位置的鏈表中找到需要的元素碍拆。即:HashMap在底層將key-Value當成一個整體進行處理,這個整體就是一個Entry對象。HashMap底層采用了一個Entry[]數(shù)組來保存所有的鍵值對感混,當需要存儲一個Entry對象時端幼,會根據(jù)hash算法來決定其在數(shù)組中的存儲位置,在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置浩习;當需要取出一個Entry時静暂,也會根據(jù)hash算法找到其在數(shù)組中的存儲位置济丘,在根據(jù)equals方法從該位置上的鏈表中取出該Entry谱秽。
5.HashMap的resize(rehash):
當hashMap中的元素越來越多的時候,hash沖突的幾率也越來越高摹迷,因為數(shù)組的長度是固定的疟赊。所以為了提高查詢的效率,就要對HashMap的數(shù)組進行擴容峡碉,數(shù)組擴容這個操作也會出現(xiàn)在ArrayList中近哟,這是一個常用的操作,而在HashMap數(shù)組擴容之后鲫寄,最消耗性能的點就出現(xiàn)了:原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置吉执,并放進去,這就是resize地来。當HashMap中的元素個數(shù)超過數(shù)組大小loadFactor時戳玫,就會進行數(shù)組擴容,loadFactor的默認值為0.75未斑,這是一個折中的取值咕宿。也就是說,默認情況下蜡秽,數(shù)組大小為16府阀,那么當HashMap中元素個數(shù)超過16*0.75=12的時候,就把數(shù)組的大小擴容為2*16=32芽突,即擴大一倍试浙,然后重新計算每個元素在數(shù)組中的位置,而這是一個非常消耗性能的操作寞蚌,所以如果我們已經(jīng)預知HashMap中元素的個數(shù)田巴,那么預設元素的個數(shù)能夠有效的提高HashMap的性能。
6.Fail-Fast機制:
我們知道HashMap不是線程安全的睬澡,因此如果在使用迭代器的過程中有其他線程修改了Map固额,那么將拋出ConcurrentModificationException,這就是所謂fail-fast策略煞聪。這一策略在源碼中的實現(xiàn)是用過modCount域(修改次數(shù))對HashMap內(nèi)容的修改都將增加這個值斗躏,那么在迭代器初始化過程中會將這個值賦給迭代器的expectModCount。在迭代過程中,判斷modCount跟expectModCount是否相等啄糙,如果不想等就表示已經(jīng)有其他線程修改了Map笛臣。(modCount聲明為volatile,保證了線程之間的可見性)隧饼。
final Entry<K,V> nextEntry() {? ?
? ? if (modCount != expectedModCount)? ?
? ? ? ? throw new ConcurrentModificationException();
7.關于HashMap的問題:
為什么String沈堡、Integer這樣的wrapper類適合作為鍵?
String燕雁、Integer這樣的wrapper類作為HashMap的鍵是在適合不過了诞丽,而且String最為常用,因為String是不可變的拐格,也是final的僧免,而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點捏浊。不可變性是必要的懂衩,因為為了要計算HashCode(),就要防止鍵值改變,如果鍵值在放入時和獲取時返回不同的hashCode的話金踪,那么就不能從HashMap中找到你想要的對象浊洞。不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的胡岔,那么請這么做法希。因為獲取對象的時候要用到equals()和hashCode()方法,那么鍵對象正確的重寫這兩個方法是非常重要的姐军。如果兩個不相等的對象返回不同的hashCode的話铁材,那么碰撞的幾率就會小些,這樣就能提高HashMap的性能奕锌。
我們可以使用自定義的對象作為鍵嗎著觉?
這是前一個問題的延伸。當然你可能使用任何對象作為鍵惊暴,只要它遵循了equals()和hashCode()方法的定義規(guī)則饼丘,并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的辽话,那么它已經(jīng)滿足了作為鍵的條件肄鸽,因為當它創(chuàng)建之后就已經(jīng)不能改變了。
我們可以使用ConcurrentHashMap來代替HashTable嗎油啤?
這是另外一個很熱門的面試題典徘,因為ConcurrentHashMap越來越多人用了。我們知道HashTable是synchronized的益咬,但是ConcurrentHashMap同步性能更好逮诲,因為它僅僅根據(jù)同步級別對Map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable,但是HashTable提供更強的線程安全性梅鹦。
二裆甩、HashTable
1.HashTable概述:
和HashMap一樣,HashTable也是一個散列表齐唆,它存儲的內(nèi)容是鍵值對映射嗤栓。HashTable繼承于Dictionary,實現(xiàn)了Map箍邮、Cloneable茉帅、java.io.Serializable接口。HashTable的函數(shù)都是同步的媒殉,這意味著它是線程安全的担敌。它的Key摔敛、Value都不可以為null廷蓉。此外,HashTable中的映射不是有序的马昙。
HashTable的實例有兩個參數(shù)影響其性能:初始容量和加載因子桃犬。容量是哈希表中桶的數(shù)量,初始容量就是哈希表創(chuàng)建時的容量行楞。注意攒暇,哈希表的狀態(tài)為open:在發(fā)生“哈希沖突”的情況下,單個桶會存儲多個條目子房,這些條目必須按順序搜索形用。加載因子是對哈希表在其容量自動增加之前可以達到多滿的一個尺度。初始容量和加載因子這兩個參數(shù)只是對該實現(xiàn)的提示证杭。關于何時以及是否調(diào)用rehash方法的具體細節(jié)則依賴于該實現(xiàn)田度。通常,默認加載因子是0.75解愤。
2.Hash Table的數(shù)據(jù)結(jié)構(gòu):
HashTable與Map關系如下
public class Hashtable<K,V>?
? ? extends Dictionary<K,V>?
? ? implements Map<K,V>, Cloneable, java.io.Serializable
HashTable并沒有去繼承AbstractMap镇饺,而是選擇繼承了Dictionary類,Dictionary是個被廢棄的抽象類送讲。
3.實現(xiàn)原理:
成員變量跟HashMap基本類似奸笤,但是HashMap更加規(guī)范,HashMap內(nèi)部還定義了一些常量哼鬓,比如默認的負載因子监右,默認的容量,最大容量等异希。
public Hashtable(int initialCapacity, float loadFactor) {//可指定初始容量和加載因子?
? ? ? ? if (initialCapacity < 0)?
? ? ? ? ? ? throw new IllegalArgumentException("Illegal Capacity: "+?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? initialCapacity);?
? ? ? ? if (loadFactor <= 0 || Float.isNaN(loadFactor))?
? ? ? ? ? ? throw new IllegalArgumentException("Illegal Load: "+loadFactor);?
? ? ? ? if (initialCapacity==0)?
? ? ? ? ? ? initialCapacity = 1;//初始容量最小值為1?
? ? ? ? this.loadFactor = loadFactor;?
? ? ? ? table = new Entry[initialCapacity];//創(chuàng)建桶數(shù)組?
? ? ? ? threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//初始化容量閾值?
? ? ? ? useAltHashing = sun.misc.VM.isBooted() &&?
? ? ? ? ? ? ? ? (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);?
? ? }?
? ? /**
? ? * Constructs a new, empty hashtable with the specified initial capacity
? ? * and default load factor (0.75).
? ? */?
? ? public Hashtable(int initialCapacity) {?
? ? ? ? this(initialCapacity, 0.75f);//默認負載因子為0.75?
? ? }?
? ? public Hashtable() {?
? ? ? ? this(11, 0.75f);//默認容量為11健盒,負載因子為0.75?
? ? }?
? ? /**
? ? * Constructs a new hashtable with the same mappings as the given
? ? * Map.? The hashtable is created with an initial capacity sufficient to
? ? * hold the mappings in the given Map and a default load factor (0.75).
? ? */?
? ? public Hashtable(Map<? extends K, ? extends V> t) {?
? ? ? ? this(Math.max(2*t.size(), 11), 0.75f);?
? ? ? ? putAll(t);?
? ? }?
——HashTable的默認容量為11,默認負載因子為0.75。(HashMap默認容量是16味榛,默認負載因子也是0.75)
——HashTable的容量可以為任意整數(shù)椭坚,最小值為1,而HashMap的容量始終為2的n次方搏色。
——為避免擴容帶來的性能問題善茎,建議指定合理容量。跟HashMap一樣频轿,HashTable內(nèi)部也有一個靜態(tài)類叫Entry垂涯,其實是個鍵值對,保存了鍵和值的引用航邢。也可以理解為一個單鏈表的節(jié)點耕赘,因為其持有下一個Entry對象的引用。
4.HashTable的存取實現(xiàn):
HashTable和HashMap存儲的都是鍵值對對象膳殷,而不是單獨的鍵或值操骡。
public synchronized V put(K key, V value) {//向哈希表中添加鍵值對?
? ? ? ? // Make sure the value is not null?
? ? ? ? if (value == null) {//確保值不能為空?
? ? ? ? ? ? throw new NullPointerException();?
? ? ? ? }?
? ? ? ? // Makes sure the key is not already in the hashtable.?
? ? ? ? Entry tab[] = table;?
? ? ? ? int hash = hash(key);//根據(jù)鍵生成hash值---->若key為null,此方法會拋異常?
? ? ? ? int index = (hash & 0x7FFFFFFF) % tab.length;//通過hash值找到其存儲位置?
? ? ? ? for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {/遍歷鏈表?
? ? ? ? ? ? if ((e.hash == hash) && e.key.equals(key)) {//若鍵相同赚窃,則新值覆蓋舊值?
? ? ? ? ? ? ? ? V old = e.value;?
? ? ? ? ? ? ? ? e.value = value;?
? ? ? ? ? ? ? ? return old;?
? ? ? ? ? ? }?
? ? ? ? }?
? ? ? ? modCount++;?
? ? ? ? if (count >= threshold) {//當前容量超過閾值。需要擴容?
? ? ? ? ? ? // Rehash the table if the threshold is exceeded?
? ? ? ? ? ? rehash();//重新構(gòu)建桶數(shù)組勒极,并對數(shù)組中所有鍵值對重哈希是掰,耗時!?
? ? ? ? ? ? tab = table;?
? ? ? ? ? ? hash = hash(key);?
? ? ? ? ? ? index = (hash & 0x7FFFFFFF) % tab.length;//這里是取摸運算?
? ? ? ? }?
? ? ? ? // Creates the new entry.?
? ? ? ? Entry<K,V> e = tab[index];?
? ? ? ? //將新結(jié)點插到鏈表首部?
? ? ? ? tab[index] = new Entry<>(hash, key, value, e);//生成一個新結(jié)點?
? ? ? ? count++;?
? ? ? ? return null;?
? ? }?
public synchronized V get(Object key) {//根據(jù)鍵取出對應索引?
? ? ? Entry tab[] = table;?
? ? ? int hash = hash(key);//先根據(jù)key計算hash值?
? ? ? int index = (hash & 0x7FFFFFFF) % tab.length;//再根據(jù)hash值找到索引?
? ? ? for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {//遍歷entry鏈?
? ? ? ? ? if ((e.hash == hash) && e.key.equals(key)) {//若找到該鍵?
? ? ? ? ? ? ? return e.value;//返回對應的值?
? ? ? ? ? }?
? ? ? }?
? ? ? return null;//否則返回null?
? }?
——HashTable并不允許值和鍵為空辱匿,若為空键痛,則拋出空指針異常。
——HashMap計算索引的方式是h&(length-1)匾七,而HashTable用的是模運算絮短,效率上是低于HashMap的。
——HashTable計算索引時將hash值先與上0x7fffffff乐尊,這是為了保證hash值始終為整數(shù)戚丸。
——HashTable中若干方法都添加了synchronized關鍵字,也就意味著這個HashTable是個線程安全的類扔嵌,這是它與HashMap最大的不同點限府。
——HashTable每次擴容都是舊容量的2倍加2,而HashMap為舊容量的2倍痢缎。