一.hashMap實(shí)現(xiàn)原理分析
- HashMap底層實(shí)現(xiàn)方式：
散列鏈表加匈，即數(shù)組+鏈表 -
hash表：也叫散列表,是通過(guò)關(guān)鍵碼值(key-value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)炫隶。
- 原理：
通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄 - 好處：這種數(shù)據(jù)結(jié)構(gòu)可以加快查找的速度淋叶。
這里就需要將幾種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)進(jìn)行比較了。
數(shù)組
優(yōu)點(diǎn)：查詢快伪阶，隨機(jī)訪問(wèn)快
缺點(diǎn)：插入煞檩，刪除慢鏈表
優(yōu)點(diǎn)：插入，刪除慢
缺點(diǎn)：隨機(jī)訪問(wèn)慢-
hash表：通過(guò)索引的方式使得查詢的時(shí)候提高查詢的效率
優(yōu)點(diǎn)：插入快栅贴，刪除快斟湃，查找快
缺點(diǎn)：基于數(shù)組的，數(shù)組創(chuàng)建后難于拓展檐薯，當(dāng)hash表被基本填滿后凝赛，性能下降非常嚴(yán)重。因此在使用hash表的時(shí)候需要提前預(yù)估表中要存多少個(gè)數(shù)據(jù)，避免擴(kuò)展哄酝。/** * hashMap是將key-value看成一個(gè)數(shù)據(jù)實(shí)體entry來(lái)存儲(chǔ)的友存，而且每個(gè)實(shí)體的索引值只與key有關(guān)，與value無(wú)關(guān) */ public class HashMap<K, V> { //hashMap長(zhǎng)度 private int size; //數(shù)組最小長(zhǎng)度 private static final int MINIMUM_CAPACITY = 4; //數(shù)組最大長(zhǎng)度 private static final int MAXIMUM_CAPACITY = 1 << 30; //空表的數(shù)組長(zhǎng)度為2陶衅，意味著一建立就要強(qiáng)制擴(kuò)容屡立，這個(gè)是自己指定的 private static final Map.Entry[] EMPTY_TABLE = new HashMapEntry[MINIMUM_CAPACITY >> 1]; //裝填因子，即數(shù)組擴(kuò)容的閾值 private int threshold; private HashMapEntry<K, V>[] table;//核心數(shù)組 //在hashmap中允許key為空搀军，而且只能有一個(gè)膨俐，并且單獨(dú)存儲(chǔ)，沒(méi)有存儲(chǔ)在核心數(shù)組里面 private HashMapEntry<K, V> entryForNullKey; @SuppressWarnings("unchecked") public HashMap() {//空參構(gòu)造函數(shù) table = (HashMapEntry<K, V>[]) EMPTY_TABLE; threshold = -1; } @SuppressWarnings("unchecked") public HashMap(int capacity) { if (capacity < 0) { throw new IllegalArgumentException(); } if (capacity == 0) { table = (HashMapEntry<K, V>[]) EMPTY_TABLE; threshold = -1; return; } //如果傳進(jìn)來(lái)的數(shù)組參數(shù)比最小數(shù)組長(zhǎng)度還小罩句，那數(shù)組長(zhǎng)度就為最小長(zhǎng)度 if (capacity < MINIMUM_CAPACITY) { capacity = MINIMUM_CAPACITY; } else if (capacity > MAXIMUM_CAPACITY) { capacity = MAXIMUM_CAPACITY; } else { capacity = roundUp2PowerOf2(capacity); } makeTable(capacity); } /** * 插入一個(gè)元素 * @param key * @param value * @return */ public V put(K key, V value) { if (key == null) { return putValueForNullKey(value); } else { /** * 如果鍵值對(duì)不為空焚刺，則先要找到key-value的位置 * 1.先生成key的hash值 * 2.根據(jù)hash值找到數(shù)組的角標(biāo) * 3.根據(jù)角標(biāo)插入對(duì)應(yīng)的位置 */ //鍵的hash值 int hash = secondaryHash(key.hashCode()); HashMapEntry<K, V>[] tab = table; /** * 得到數(shù)組的角標(biāo) * &運(yùn)算的作用：0~min(a,b),可以取到最小值的最大值 */ int index = hash & (tab.length - 1); //如果存在指定的元素則覆蓋，不存在則插入 //對(duì)羊肉串進(jìn)行遍歷 for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { /** * key與hash值之間的關(guān)系 * key相同门烂，hash值一定相同乳愉；反之，hash值相同屯远，key不一定相同 */ if (e.hash == hash && key.equals(e.key)) { //同一個(gè)元素蔓姚，則覆蓋 V oldValue = e.getValue(); e.setValue(value); return oldValue; } } //沒(méi)有覆蓋，直接插入元素,但不一定是在數(shù)組中增加一個(gè)元素慨丐，可能是在某個(gè)羊肉串后面添加一個(gè)節(jié)點(diǎn) /** * @see makeTable(int capacity) * @link{makeTable(int capacity) } * 雖然閾值定義的是capacity的3/4坡脐，但是capacity是個(gè)正數(shù)，所以threshold一個(gè)整數(shù) */ if (size++ > threshold) { //假如一個(gè)元素插入成功房揭，但是超過(guò)了閾值备闲，就需要擴(kuò)容 /** * 1.創(chuàng)建一個(gè)新的容量的數(shù)組 */ tab = doubleCapacity(); index = hash & (tab.length - 1); } addNewEntry(key, value, hash, index); } return value; } public V get(Object key){ if (key == null) { HashMapEntry<K,V> e=entryForNullKey; return e==null?null:e.getValue(); }else { int hash=secondaryHash(key.hashCode()); HashMapEntry<K,V>[] tab=table; int index=hash&(tab.length-1); for (HashMapEntry<K,V> e=tab[index];e!=null;e=e.next){ K eKey = e.key; if (eKey==key||(e.hash==hash&&key.equals(eKey))) { return e.value; } } return null; } } /** * 將key-value鍵值對(duì)添加到index的位置 * @param key * @param value * @param hash * @param index */ private void addNewEntry(K key, V value, int hash, int index) { //添加到隊(duì)頭的位置 table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]); } /** * 雙倍擴(kuò)容 * @return */ @SuppressWarnings("unchecked") private HashMapEntry<K, V>[] doubleCapacity() { HashMapEntry<K, V>[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { return oldTable; } else { int newCapacity = oldCapacity << 1; // TODO: 這里是否要判斷newCapacity>MAXIMUM_CAPACITY? if (newCapacity >= MAXIMUM_CAPACITY) { newCapacity = MAXIMUM_CAPACITY; } //這里不能采用new的方式，因?yàn)檫@樣就與舊的table產(chǎn)生不了聯(lián)系 HashMapEntry<K, V>[] newTable = makeTable(newCapacity); /** * 雙倍擴(kuò)容時(shí)捅暴，表有可能是空表恬砂，即 * @link{<code>EMPTY_TABLE</code>}， 此時(shí)數(shù)組長(zhǎng)度為4伶唯，但是size為0 */ if (size == 0) { return newTable; } /** * 雙倍擴(kuò)容之后觉既，需要重新散列 */ for (int j = 0; j < oldTable.length; j++) { //拿到每個(gè)羊肉串 HashMapEntry<K, V> e = oldTable[j]; if (e == null) { continue; } /** * e.hash & oldCapacity <===> e.hash & oldTable.length===>結(jié)果的范圍：[0,oldTable.length] * 對(duì)比： * int index = hash & (tab.length - 1)===>結(jié)果的范圍：[0,oldTable.length-1] * “|”的作用：2*max（a惧盹，b）> a|b >max(a,b) */ int highBit = e.hash & oldCapacity;//0-oldTable.length //斷鏈標(biāo)志位 HashMapEntry<K, V> broken = null; newTable[j | highBit] = e;//重新散列成功oldTable.length-2*oldTable.length-1 /** * e=n： 每次指針后移的時(shí)候乳幸，都保留當(dāng)前結(jié)點(diǎn)的前一個(gè)元素 **/ for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) { int nextHighBit = n.hash & oldCapacity; if (nextHighBit != highBit) { if (broken == null) { int nextNewIndex = j | nextHighBit;//新的索引 newTable[nextNewIndex] = n; } else { broken.next = n; } broken = e; highBit = nextHighBit; } if (broken != null) { broken.next = null; } } } return newTable; } } /** * hashMap 鍵的hash算法 * 可以看到：對(duì)鍵進(jìn)行單獨(dú)的hash運(yùn)算 * @param h key的hash值 * @return 算法的意義：目的就是為了將h打散，而且在0到max 之間均勻分布 * 異或算法的作用：補(bǔ)位钧椰，多樣化 */ private int secondaryHash(int h) { //拿到高12位粹断， 拿到高20位 h ^= (h >>> 20) ^ (h >>> 12); // 拿到自己 拿到高25位， 拿到高28位 return h ^ (h >>> 7) ^ (h >>> 4); } /** * 給放空key的鍵值對(duì)賦值 * @param value * @return */ private V putValueForNullKey(V value) { HashMapEntry<K, V> newEntry = entryForNullKey; //如果空鍵的鍵值對(duì)不存在嫡霞，則重新創(chuàng)建 if (newEntry == null) { addEntryForNullKey(value); //雖然空鍵鍵值對(duì)單獨(dú)存放瓶埋，但是也是hashmap集合中的一個(gè)元素，所以要size++ size++; return null; } else { V oldValue = newEntry.getValue(); newEntry.setValue(value); return oldValue; } } /** * 創(chuàng)建空鍵鍵值對(duì),hash值只與key有關(guān)，鍵為null的鍵值對(duì)單獨(dú)存放养筒，所以next為空 * @param value */ private void addEntryForNullKey(V value) { entryForNullKey = new HashMapEntry<>(null, value, 0, null); } /** * 根據(jù)容量創(chuàng)建核心數(shù)組 * @param capacity */ private HashMapEntry<K, V>[] makeTable(int capacity) { //table=new HashMapEntry[capacity];//不要這么寫(xiě) HashMapEntry<K, V>[] newTable = new HashMapEntry[capacity]; table = newTable;//盡量不要操作全局變量曾撤，把全局變量轉(zhuǎn)成局部變量，通過(guò)操作局部變量達(dá)到操作全局變量的目的晕粪，防止bug threshold = (capacity >> 1) + (capacity >> 2);//3/4; return newTable; } /** * 將任意一個(gè)數(shù)轉(zhuǎn)換成2的冪次方 * 是2的冪次方的數(shù)的特點(diǎn)： * 2 =10=1+1 * 4 =100=11+1 * 8 =1000=111+1 * 16=10000=1111+1 * 32=100000=11111+1 * <p> * @param i * @return */ private int roundUp2PowerOf2(int i) { i--; i = i >>> 1; i = i >>> 2; i = i >>> 4; i = i >>> 8; i = i >>> 16; return i; } /** * 1. 成員變量可以是任意數(shù)據(jù)類型挤悉，基本數(shù)據(jù)類型，引用數(shù)據(jù)類型巫湘，類就屬于引用數(shù)據(jù)類型装悲， * 因此內(nèi)部類的另一種理解方式就是將其看成外部類的成員變量， * <code>成員變量</code>也是<code>全局變量</code>尚氛，是整個(gè)類中都要使用的變量 * 成員變量表示一個(gè)類的屬性诀诊，這個(gè)屬性自然在這個(gè)類中都成立，自然全局可用 * <p> * 2.hashMap是將key-value看成一個(gè)數(shù)據(jù)實(shí)體entry來(lái)存儲(chǔ)的阅嘶，而且每個(gè)實(shí)體的索引值只與key有關(guān)属瓣，與value無(wú)關(guān) * 因此在entry中需要一個(gè)構(gòu)造函數(shù)將key和value封裝成entry */ private static class HashMapEntry<K, V> implements Map.Entry<K, V> { //每個(gè)鍵值對(duì)的鍵是唯一的，一旦被賦值讯柔，就不能被修改了奠涌，通過(guò)final修飾來(lái)達(dá)到這個(gè)目的 final K key; V value; final int hash;//hash是有key有關(guān)的hash算法生成的，因此也不能被被外界修改 HashMapEntry<K, V> next;//指向下一個(gè)節(jié)點(diǎn)的指針 public HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) { this.key = key; this.value = value; this.hash = hash; this.next = next; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } /** * 任何一個(gè)對(duì)象都有hashcode方法磷杏，這個(gè)是從Object類繼承過(guò)來(lái)的溜畅，hash算法是自己指定的 * @return */ @Override public int hashCode() { return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode()); } } }
