HashMap繼承于AbstractMap，實(shí)現(xiàn)了Map接口，同時(shí)標(biāo)記了Cloneable和Serializable接口。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, SerializableHashMap提供了四個(gè)構(gòu)造函數(shù)： (1) HashMap()：構(gòu)造一個(gè)初始容量為16和加載因子為0.75的空HashMap。 (2) HashMap(int initialCapacity)：構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子0.75的空HashMap。 (3) HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個(gè)帶指定初始容量和指定加載因子的空HashMap。 (4) HashMap(Map
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); } PRivate void inflateTable(int toSize) { // Find a power of 2 >= toSize，計(jì)算出大于toSize的最小的2的n次方值。 int capacity = roundUpToPowerOf2(toSize); // 設(shè)置HashMap的容量極限，當(dāng)HashMap的容量達(dá)到該極限時(shí)就會(huì)進(jìn)行擴(kuò)容操作 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化table數(shù)組 table = new Entry[capacity]; // Initialize the hashing mask value. We defer initialization until we really need it. initHashSeedAsNeeded(capacity); }初始容量是創(chuàng)建哈希表時(shí)的桶的數(shù)量， 加載因子是哈希表容量擴(kuò)展前可以達(dá)到多滿(mǎn)的一種尺度，它衡量的是一個(gè)散列表的空間的使用程度。負(fù)載因子越大，表示散列表的裝填程度越高、對(duì)空間的利用更充分，后果卻是查找效率的降低；而負(fù)載因子太小，那么散列表的數(shù)據(jù)將過(guò)于稀疏，對(duì)空間的利用存在著浪費(fèi)。
從構(gòu)造函數(shù)中可以看出，HashMap本質(zhì)是一個(gè)table數(shù)組，table數(shù)組里的元素是Entry鏈表。Entry為HashMap的內(nèi)部類(lèi)，它包含了鍵key、值value、下一個(gè)節(jié)點(diǎn)next以及hash值，正是由于Entry才構(gòu)成了table數(shù)組的項(xiàng)為鏈表。
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } // 部分源碼略去put(K key, V value)方法的源碼如下。基本過(guò)程是： 1. 判斷key是否為null，若為null，則直接調(diào)用putForNullKey方法。 2. key不為空則計(jì)算key的hash值，再根據(jù)hash值搜索key落在哪個(gè)桶上。 3. 對(duì)該桶上的Entry鏈表進(jìn)行遍歷，如果該鏈表上存在相同的key，則覆蓋原來(lái)key的value，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } // 當(dāng)key為null，調(diào)用putForNullKey方法，保存null到table的第一個(gè)位置，這就是HashMap允許為null的原因 if (key == null) return putForNullKey(value); // 計(jì)算key的hash值 int hash = hash(key); // 計(jì)算key的hash值在table數(shù)組中的位置，即落在哪一個(gè)桶上 int i = indexFor(hash, table.length); // 迭代該桶上的Entry鏈表,找到key保存的位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 判斷該鏈表上是否有相同的hash值和相同的key（僅僅判斷hash值是否相同是不夠的） if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 若存在相同，則直接覆蓋value，返回舊value V oldValue = e.value; e.value = value; e.recordaccess(this); return oldValue; } } //修改次數(shù)增加1 modCount++; // 該鏈表上不存在相同的hash值和key，則將key、value添加至i位置處 addEntry(hash, key, value, i); return null; }以上的存儲(chǔ)機(jī)制也解釋了HashSet是如何保證元素唯一性的。
這里需要強(qiáng)調(diào)下indexFor方法。HashMap就是通過(guò)該方法實(shí)現(xiàn)均勻分布table數(shù)據(jù)和充分利用空間的。初始化時(shí)，我們保證了capacity是大于初始容量的最小的2的n次方值。當(dāng)length = 2^n時(shí)，不同的hash值發(fā)生碰撞的概率比較小，從而數(shù)據(jù)在table數(shù)組中分布較均勻，查詢(xún)速度也較快。
/** * 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); }最后看一下鏈的產(chǎn)生和擴(kuò)容問(wèn)題。 1. 鏈的產(chǎn)生：系統(tǒng)總是將新創(chuàng)建的Entry放入bucketIndex索引處。如果bucketIndex處已經(jīng)有了對(duì)象，那么新添加的Entry對(duì)象將指向原有的Entry對(duì)象，形成一條Entry鏈；如果bucketIndex處還沒(méi)有Entry對(duì)象，那么新添加的Entry對(duì)象將指向null。在table數(shù)組未擴(kuò)容的情況下，兩個(gè)元素的hash值相同，就意味著它們會(huì)在同一個(gè)桶上。 2. 擴(kuò)容問(wèn)題：當(dāng)HashMap中元素的數(shù)量等于table數(shù)組長(zhǎng)度*加載因子，就會(huì)觸發(fā)擴(kuò)容操作。擴(kuò)容操作需盡量避免，因?yàn)樗枰匦掠?jì)算這些元素在新table數(shù)組中的位置并進(jìn)行復(fù)制處理。
void addEntry(int hash, K key, V value, int bucketIndex) { // 若HashMap中元素的個(gè)數(shù)超過(guò)極限了，則容量擴(kuò)大兩倍 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { // 獲取bucketIndex處的Entry Entry<K,V> e = table[bucketIndex]; // 將新創(chuàng)建的Entry放入bucketIndex索引處，并讓新的Entry指向原來(lái)的Entry e table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
