HashMap的實(shí)現(xiàn)原理
1.HashMap概述
HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)打厘。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵余掖。此類不保證映射的順序贿肩，特別是它不保證該順序恒久不變。
2.HashMap的數(shù)據(jù)結(jié)構(gòu)
在 Java 編程語言中徒扶，最基本的結(jié)構(gòu)就是兩種，一個(gè)是數(shù)組根穷，另外一個(gè)是指針（引用）姜骡，HashMap 就是通過這兩個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)屿良，即數(shù)組和鏈表的結(jié)合體圈澈。
每個(gè)元素存儲(chǔ)的是一個(gè)鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲(chǔ)到數(shù)組中呢? 一般情況是通過hash(key)%len獲得管引，也就是元素的key的哈希值對(duì)數(shù)組長度取模得到士败。比如上述哈希表中闯两，12%16=12,28%16=12,108%16=12,140%16=12褥伴。所以12、28漾狼、108以及140都存儲(chǔ)在數(shù)組下標(biāo)為12的位置重慢。
HashMap其實(shí)也是一個(gè)線性的數(shù)組實(shí)現(xiàn)的,所以可以理解為其存儲(chǔ)數(shù)據(jù)的容器就是一個(gè)線性數(shù)組。這可能讓我們很不解逊躁，一個(gè)線性的數(shù)組怎么實(shí)現(xiàn)按鍵值對(duì)來存取數(shù)據(jù)呢似踱？這里HashMap有做一些處理。
首先HashMap里面實(shí)現(xiàn)一個(gè)靜態(tài)內(nèi)部類Entry稽煤，其重要的屬性有 key , value, next核芽，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對(duì)實(shí)現(xiàn)的一個(gè)基礎(chǔ)bean，我們上面說到HashMap的基礎(chǔ)就是一個(gè)線性數(shù)組酵熙，這個(gè)數(shù)組就是Entry[]轧简，Map里面的內(nèi)容都保存在Entry[]里面。
3. HashMap的初始化過程
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
DEFAULT_LOAD_FACTOR : 負(fù)載因子的默認(rèn)值0.75 表示數(shù)據(jù)填充的臨界值,即數(shù)據(jù)達(dá)到總數(shù)據(jù)的75%時(shí)就開始準(zhǔn)備擴(kuò)容了.
DEFAULT_INITIAL_CAPACITY : 默認(rèn)傳入Map中的數(shù)據(jù)默認(rèn)值為1<<4 (實(shí)際就是16)
從上面看出 現(xiàn)實(shí)調(diào)用自己的構(gòu)造方法,然后創(chuàng)建存儲(chǔ)的Table(實(shí)際是數(shù)組),最后把值添加到創(chuàng)建的table中
-
this(var1,var2)實(shí)際調(diào)用的構(gòu)造方法
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
threshold = initialCapacity;
init();
}
initialCapacity : ==即初始化申請(qǐng)空間的值,不等于Map實(shí)際初始化的內(nèi)部數(shù)組的長度(稍后解釋為什么)==,若不填寫默認(rèn)是使用DEFAULT_INITIAL_CAPACITY也就是16
initialCapacity的最大值為1 << 30 也就是2^30次方
loadFactor : 負(fù)載因子的初始化值,若不填寫默認(rèn)為DEFAULT_LOAD_FACTOR也就是0.75
threshold : 下次擴(kuò)容時(shí)的申請(qǐng)空間值
-
inflateTable方法
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
這里面有個(gè)重點(diǎn)
實(shí)際申請(qǐng)的內(nèi)部數(shù)組的大小 int capacity = roundUpToPowerOf2(toSize);
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
return rounded;
}
這段代碼在傳入的number在正常數(shù)值都會(huì)走 Integer.highestOneBit(number)和Integer.bitCount(number)
里面的代碼都是位運(yùn)算 ==roundUpToPowerOf2這個(gè)方法實(shí)際上的功能就是返回一個(gè)最小的是2^n且它大于等于number的值==
例如 number= 4 那么roundUpToPowerOf2的返回值就是2^2 = 4
number = 5 那么roundUpToPowerOf2的返回值就是2^3 = 8
那么問題來了 為啥內(nèi)部數(shù)組大小為啥是2^n呢?
而當(dāng)數(shù)組長度為16時(shí)匾二，即為2的n次方時(shí)哮独，2n-1得到的二進(jìn)制數(shù)的每個(gè)位上的值都為1（比如(24-1)2=1111），這使得在低位上&時(shí)察藐，得到的和原h(huán)ash的低位相同皮璧，加之hash(int h)方法對(duì)key的hashCode的進(jìn)一步優(yōu)化，加入了高位計(jì)算分飞，就使得只有相同的hash值的兩個(gè)值才會(huì)被放到數(shù)組中的同一個(gè)位置上形成鏈表悴务。
所以說，當(dāng)數(shù)組長度為2的n次冪的時(shí)候譬猫，不同的key算得得index相同的幾率較小惨寿，那么數(shù)據(jù)在數(shù)組上分布就比較均勻邦泄，也就是說碰撞的幾率小，相對(duì)的裂垦，查詢的時(shí)候就不用遍歷某個(gè)位置上的鏈表顺囊，這樣查詢效率也就較高了。
-
putAllForCreate方法
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
這里是個(gè)foreach循環(huán),將m中的數(shù)據(jù)拿出來一一添加到map, 下面看具體的putForCreate方法
/**
* This method is used instead of put by constructors and
* pseudoconstructors (clone, readObject). It does not resize the table,
* check for comodification, etc. It calls createEntry rather than
* addEntry.
*/
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
1.計(jì)算key的hash值
key==null -> hash=0
key!=null -> hash = hash(key)
2.計(jì)算數(shù)組下標(biāo)(根據(jù)hash值求余,即余數(shù)相同的hash值放到相同的數(shù)組下標(biāo)對(duì)應(yīng)的一個(gè)鏈表上)按位取并蕉拢，作用上相當(dāng)于取模mod或者取余%特碳。這意味著數(shù)組下標(biāo)相同，并不表示hashCode相同晕换。
/**
* Returns index for hash code h.
*/
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);
}
3.在對(duì)應(yīng)的key上賦值或者添加一組map
4.HashMap的存取實(shí)現(xiàn)
HashMap的基本存取過程基本如下
// 存儲(chǔ)時(shí):
int hash = key.hashCode(); // 這個(gè)hashCode方法這里不詳述,只要理解每個(gè)key的hash是一個(gè)固定的int值
int index = hash % Entry[].length;
Entry[index] = value;
// 取值時(shí):
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];
-
存儲(chǔ)數(shù)據(jù)
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
從上面的源代碼中可以看出：
1.Map支持key=null
private V putForNullKey(V value) {
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
從上面的代碼中可以看到當(dāng)key==null 會(huì)將值放到table[0]索引下,并且當(dāng)數(shù)據(jù)重復(fù)時(shí),新數(shù)據(jù)會(huì)覆蓋原數(shù)據(jù),并返回原數(shù)據(jù),若不重復(fù)則添加到table hash=0,bucketIndex=0;
2.當(dāng)我們往HashMap中put元素的時(shí)候午乓，先根據(jù)key的hashCode重新計(jì)算hash值，根據(jù)hash值得到這個(gè)元素在數(shù)組中的位置（即下標(biāo)）闸准，如果數(shù)組該位置上已經(jīng)存放有其他元素了益愈，那么在這個(gè)位置上的元素將以鏈表的形式存放，新加入的放在鏈頭夷家，最先加入的放在鏈尾蒸其。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上库快。
addEntry方法
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); //參數(shù)e, 是Entry.next
// 如果 Map 中的 key-value 對(duì)的數(shù)量超過了極限
if (size++ >= threshold)
// 把 table 對(duì)象的長度擴(kuò)充到原來的2倍。
resize(2 * table.length);
}
儲(chǔ)HashMap中的key-value對(duì)時(shí)义屏，完全沒有考慮Entry中的value靠汁，僅僅只是根據(jù)key來計(jì)算并決定每個(gè)Entry的存儲(chǔ)位置。我們完全可以把 Map 集合中的 value 當(dāng)成 key 的附屬闽铐，當(dāng)系統(tǒng)決定了 key 的存儲(chǔ)位置之后蝶怔，value 隨之保存在那里即可。
hash(int h)方法根據(jù)key的hashCode重新計(jì)算一次散列兄墅。此算法加入了高位計(jì)算踢星，防止低位不變，高位變化時(shí)察迟，造成的hash沖突斩狱。
當(dāng)然HashMap里面也包含一些優(yōu)化方面的實(shí)現(xiàn)，這里也說一下扎瓶。比如：Entry[]的長度一定后所踊，隨著map里面數(shù)據(jù)的越來越長，這樣同一個(gè)index的鏈就會(huì)很長概荷，會(huì)不會(huì)影響性能秕岛？HashMap里面設(shè)置一個(gè)因子(loadFactor)，隨著map的size越來越大，Entry[]會(huì)以一定的規(guī)則加長長度继薛。
-
讀取數(shù)據(jù)
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
當(dāng)key=null 直接取table的索引為0下的值;
當(dāng)key!=null
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
從HashMap中g(shù)et元素時(shí)修壕，首先計(jì)算key的hashCode，在通過indexFor方法找到數(shù)組中對(duì)應(yīng)位置的某一元素遏考，然后通過key的equals方法在對(duì)應(yīng)位置的鏈表中找到需要的元素慈鸠。
歸納起來簡單地說，HashMap 在底層將 key-value 當(dāng)成一個(gè)整體進(jìn)行處理灌具，這個(gè)整體就是一個(gè) Entry 對(duì)象青团。HashMap 底層采用一個(gè) Entry[] 數(shù)組來保存所有的 key-value 對(duì)，當(dāng)需要存儲(chǔ)一個(gè) Entry 對(duì)象時(shí)咖楣，會(huì)根據(jù)hash算法來決定其在數(shù)組中的存儲(chǔ)位置督笆，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲(chǔ)位置；當(dāng)需要取出一個(gè)Entry時(shí)诱贿，也會(huì)根據(jù)hash算法找到其在數(shù)組中的存儲(chǔ)位置娃肿，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。
5.HashMap的擴(kuò)容
當(dāng)HashMap中的元素越來越多的時(shí)候珠十，hash沖突的幾率也就越來越高料扰，因?yàn)閿?shù)組的長度是固定的。所以為了提高查詢的效率宵睦，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容记罚，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中墅诡，這是一個(gè)常用的操作壳嚎，而在HashMap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置末早，并放進(jìn)去烟馅，這就是resize。
那么HashMap什么時(shí)候進(jìn)行擴(kuò)容呢然磷？當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小*loadFactor時(shí)郑趁，就會(huì)進(jìn)行數(shù)組擴(kuò)容
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果當(dāng)前的數(shù)組長度已經(jīng)達(dá)到最大值，則不在進(jìn)行調(diào)整
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根據(jù)傳入?yún)?shù)的長度定義新的數(shù)組
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
//按照新的規(guī)則姿搜，將舊數(shù)組中的元素轉(zhuǎn)移到新數(shù)組中
transfer(newTable);
table = newTable;
//更新臨界值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
舊數(shù)組的數(shù)據(jù)轉(zhuǎn)到新數(shù)組
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
6.Fail-Fast機(jī)制：
我們知道java.util.HashMap不是線程安全的寡润，因此如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException舅柜，這就是所謂fail-fast策略梭纹。
這一策略在源碼中的實(shí)現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)致份，對(duì)HashMap內(nèi)容的修改都將增加這個(gè)值变抽，那么在迭代器初始化過程中會(huì)將這個(gè)值賦給迭代器的expectedModCount。
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
HashMapEntry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
在迭代過程中，判斷modCount跟expectedModCount是否相等绍载，如果不相等就表示已經(jīng)有其他線程修改了Map：
注意到modCount聲明為volatile诡宗，保證線程之間修改的可見性。（volatile之所以線程安全是因?yàn)楸籿olatile修飾的變量不保存緩存击儡，直接在內(nèi)存中修改塔沃，因此能夠保證線程之間修改的可見性）
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMapEntry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
HashMapEntry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
在HashMap的API中指出：
由所有HashMap類的“collection 視圖方法”所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對(duì)映射進(jìn)行修改阳谍，除非通過迭代器本身的 remove 方法芳悲，其他任何時(shí)間任何方式的修改，迭代器都將拋出ConcurrentModificationException边坤。因此名扛，面對(duì)并發(fā)的修改，迭代器很快就會(huì)完全失敗茧痒，而不保證在將來不確定的時(shí)間發(fā)生任意不確定行為的風(fēng)險(xiǎn)肮韧。
注意，迭代器的快速失敗行為不能得到保證旺订，一般來說弄企，存在非同步的并發(fā)修改時(shí)，不可能作出任何堅(jiān)決的保證区拳【辛欤快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此樱调，編寫依賴于此異常的程序的做法是錯(cuò)誤的约素，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯(cuò)誤.
解決辦法
- 第一、使用線程安全的ConcurrentHashMap或HashTable,它就不會(huì)產(chǎn)生ConcurrentModificationException異常笆凌，也就是它使用迭代器完全不會(huì)產(chǎn)生fail-fast機(jī)制
- 第二.Collections.synchronizedMap將HashMap包裝起來
返回由指定映射支持的同步（線程安全的）映射圣猎。為了保證按順序訪問，必須通過返回的映射完成對(duì)底層映射的所有訪問乞而。在返回的映射或其任意 collection 視圖上進(jìn)行迭代時(shí)送悔，強(qiáng)制用戶手工在返回的映射上進(jìn)行同步：
Map m = Collections.synchronizedMap(new HashMap());
...
Set s = m.keySet(); //不需要加鎖
...
synchronized(m) { // 對(duì)Map的對(duì)象m加鎖
Iterator i = s.iterator(); // 必須加鎖的模塊
while (i.hasNext())
foo(i.next());
}
