hashMap的實現原理

• Java8以前底層數據結構：數組+鏈表。

• Java8及以后底層數據結構：數組+鏈表+紅黑樹。默認情況下鏈表長度超過8變成紅黑樹（整個hashMap元素數量超過64），紅黑樹節點樹小于6變回鏈表。

hashMap是如何解決hash沖突的問題的

• 如果發生了碰撞，新添加的元素將以鏈表的方式鏈接到后面。

• 如果鏈表長度超過閥值，就把鏈表轉成紅黑樹。

• 如果鏈表長度低于6，就把紅黑樹轉回鏈表。

hashMap的擴容

數組每個下標對應的位置稱為hash槽，默認情況下，當擁有元素的hash槽數量超過當前容量乘以0.75，就會觸發擴容操作，擴容為當前容量的2倍。

源碼翻看

hashMap的屬性

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {//序列號，序列化的時候使用。private static final long serialVersionUID = 362498820763181265L;/*** 默認容量，1向左移位4個，00000001變成00010000，也就是2的4次方為16* 使用移位是因為移位是計算機基礎運算，效率比加減乘除快。**/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//最大容量，2的30次方。static final int MAXIMUM_CAPACITY = 1 << 30;//加載因子，用于擴容使用。這個參數的意義是：當數組長度達到當前長度 * 0.75時 需要擴容了！static final float DEFAULT_LOAD_FACTOR = 0.75f;//當某個桶節點數量大于8時，會轉換為紅黑樹。static final int TREEIFY_THRESHOLD = 8;//當某個桶節點數量小于6時，會轉換為鏈表，前提是它當前是紅黑樹結構。static final int UNTREEIFY_THRESHOLD = 6;//當整個hashMap中元素數量大于64時，也會進行轉為紅黑樹結構。static final int MIN_TREEIFY_CAPACITY = 64;//存儲元素的數組，transient關鍵字表示該屬性不能被序列化transient Node<K,V>[] table;//將數據轉換成set的另一種存儲形式，這個變量主要用于迭代功能。transient Set<Map.Entry<K,V>> entrySet;//元素數量transient int size;//統計該map修改的次數transient int modCount;//臨界值，也就是元素數量達到臨界值時，會進行擴容。int threshold;//也是加載因子，只不過這個是變量。final float loadFactor;

構造方法

構造方法中 ，都是依靠第三個方法來執行的，但是前三個方法都沒有進行數組的初始化操作，即使調用了構造方法此時存放HaspMap中數組元素的table表長度依舊為0 。在第四個構造方法中調用了inflateTable()方法完成了table的初始化操作，并將m中的元素添加到HashMap中。

/** * 構造方法 1 無參構造方法，使用默認初始容量16與默認負載因子0.75構造一個空的HashMap。*/public HashMap() {// 初始化加載因子this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/** * 構造方法 2 傳入初始容量，通過默認負載因子構造一個空的HashMap* 調用了HashMap(int initialCapacity, float loadFactor)構造方法。*/public HashMap(int initialCapacity) {// 調用構造方法3，并傳入加載因子this(initialCapacity, DEFAULT_LOAD_FACTOR);}/** * 構造方法 3 傳入初始容量和負載因子來構造一個空的HashMap。*/public HashMap(int initialCapacity, float loadFactor) {// 初始容量不能小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);// 初始容量不能大于MAXIMUM_CAPACITY（最大容量）if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 校驗負載因子合法性if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " + loadFactor);this.loadFactor = loadFactor;// 計算下次resize的閾值this.threshold = tableSizeFor(initialCapacity);}/** * 構造方法 4 指定集合，轉化為HashMap，使用默認初始容量與默認負載因子。*/public HashMap(Map<? extends K, ? extends V> m) {// 初始化加載因子this.loadFactor = DEFAULT_LOAD_FACTOR;// 將m中的所有元素添加至hashMap中putMapEntries(m, false);}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//獲取該map的實際長度int s = m.size();if (s > 0) {//判斷table是否初始化，如果沒有初始化if (table == null) { // pre-size/*** 求出需要的容量，因為實際使用的長度=容量*0.75得來的，* +1是因為小數相除，基本都不會是整數，容量大小不能為小數的，* 后面轉換為int，多余的小數就要被丟掉，所以+1，* 例如，map實際長度22，22/0.75=29.3,所需要的容量肯定為30，* 如果剛剛好除得整數呢，除得整數的話，容量大小多1也沒什么影響**/float ft = ((float)s / loadFactor) + 1.0F;//判斷該容量大小是否超出上限。int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);/*** 對臨界值進行初始化，tableSizeFor(t)這個方法會返回大于t值的，且離其最近的2次冪，* 例如t為29，則返回的值是32**/if (t > threshold)threshold = tableSizeFor(t);}//如果table已經初始化，則進行擴容操作，resize()就是擴容。else if (s > threshold)resize();//遍歷，把map中的數據轉到hashMap中。for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();putVal(hash(key), key, value, false, evict);}}}

擴容方法

final Node<K,V>[] resize() {// 把之前的數組變成 oldTabNode<K,V>[] oldTab = table;//old 的長度int oldCap = (oldTab == null) ? 0 : oldTab.length;//old 的臨界值int oldThr = threshold;//初始化new的長度和臨界值int newCap, newThr = 0;//oldCap > 0也就是說不是首次初始化，因為hashMap用的是懶加載if (oldCap > 0) {// 大于最大值if (oldCap >= MAXIMUM_CAPACITY) {//臨界值為整數的最大值threshold = Integer.MAX_VALUE;return oldTab; // 不需要擴容，直接返回 old}// 沒有超過最大值，擴容兩倍，并且擴容后的長度要小于最大值，old 長度也要大于16else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 臨界值擴容為 old 的臨界值2倍newThr = oldThr << 1; }/*** 如果oldCap<0，但是已經初始化了，像把元素刪除完之后的情況，那么它的臨界值肯定還存在，* 如果是首次初始化，它的臨界值則為0**/else if (oldThr > 0) // old 的臨界值 大于0newCap = oldThr;// 首次初始化，給與默認的值else { newCap = DEFAULT_INITIAL_CAPACITY;// 臨界值 等于 容量 * 加載因子newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 初始化時容量小于默認值16的，此時newThr沒有賦值，計算新的resize上限if (newThr == 0) {// new的臨界值float ft = (float)newCap * loadFactor;// 判斷是否new容量是否大于最大值，臨界值是否大于最大值newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 把上面各種情況分析出的臨界值，在此處真正進行改變，也就是容量和臨界值都改變了。threshold = newThr;// 表示忽略該警告@SuppressWarnings({"rawtypes","unchecked"})// 初始化Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 賦予當前的tabletable = newTab;// 此處是把old中的元素，遍歷到new中if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {// 臨時變量Node<K,V> e;// 當前哈希桶的位置值不為null，也就是數組下標處有值，因為有值表示可能會發生沖突if ((e = oldTab[j]) != null) {// 把已經賦值之后的變量置位null，為了好回收，釋放內存oldTab[j] = null;// 如果下標處的節點沒有下一個元素if (e.next == null)// 把該變量的值存入newCap中，e.hash & (newCap - 1)并不等于jnewTab[e.hash & (newCap - 1)] = e;// 該節點為紅黑樹結構，也就是存在哈希沖突，該哈希桶中有多個元素else if (e instanceof TreeNode)//把此樹進行轉移到newCap中((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { /*** 此處表示為鏈表結構，同樣把鏈表轉移到newCap中，* 就是把鏈表遍歷后，把值轉過去，在置位null**/Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 原索引if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 原索引+oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}//返回擴容后的hashMapreturn newTab;}

添加方法

public V put(K key, V value) {/*** 四個參數，* 第一個hash值，* 第四個參數表示如果該key存在值，如果為null的話，則插入新的value，* 最后一個參數，在hashMap中沒有用，可以不用管，使用默認的即可**/return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab 哈希數組，p 該哈希桶的首節點，n hashMap的長度，i 計算出的數組下標Node<K,V>[] tab; Node<K,V> p; int n, i;// 獲取長度并進行擴容，使用的是懶加載，table一開始是沒有加載的，等put后才開始加載if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/*** 如果計算出的該哈希桶的位置沒有值，則把新插入的key-value放到此處，* 此處就算沒有插入成功，也就是發生哈希沖突時也會把哈希桶的首節點賦予p**/if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//發生哈希沖突的幾種情況else {// e 臨時節點的作用， k 存放該當前節點的key Node<K,V> e; K k;// 第一種，插入的key-value的hash值，key都與當前節點的相等，e = p，則表示為首節點if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 第二種，hash值不等于首節點，判斷該p是否屬于紅黑樹的節點else if (p instanceof TreeNode)/*** 為紅黑樹的節點，則在紅黑樹中進行添加，* 如果該節點已經存在，則返回該節點（不為null），* 該值很重要，用來判斷put操作是否成功，如果添加成功返回null**/e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 第三種，hash值不等于首節點，不為紅黑樹的節點，則為鏈表的節點else {// 遍歷該鏈表for (int binCount = 0; ; ++binCount) {// 如果找到尾部，則表明添加的key-value沒有重復，在尾部進行添加if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 判斷是否要轉換為紅黑樹結構if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);break;}// 如果鏈表中有重復的key，e則為當前重復的節點，結束循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 在循環中判斷e是否為null，如果為null則表示加了一個新節點，// 不是null則表示找到了hash、key都一致的Node。if (e != null) { V oldValue = e.value;// 判斷是否更新value值// map提供putIfAbsent方法，如果key存在，不更新value// 但是如果value==null任何情況下都更改此值if (!onlyIfAbsent || oldValue == null)e.value = value;// 此方法是空方法，什么都沒實現，用戶可以根據需要進行覆蓋afterNodeAccess(e);return oldValue;}}// 到了此步驟，則表明待插入的key-value是沒有key的重復，因為插入成功e節點的值為null// 修改次數+1++modCount;// 實際長度+1，判斷是否大于臨界值，大于則擴容if (++size > threshold)resize();// 此方法是空方法，什么都沒實現，用戶可以根據需要進行覆蓋afterNodeInsertion(evict);// 添加成功return null;}

刪除方法

public V remove(Object key) {//臨時變量Node<K,V> e;/*** 調用removeNode(hash(key), key, null, false, true)進行刪除，* 第三個value為null，表示，把key的節點直接都刪除了，不需要用到值，* 如果設為值，則還需要去進行查找操作**/return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}/*** 第一參數為哈希值，* 第二個為key，* 第三個value，* 第四個為是為true的話，則表示刪除它key對應的value，不刪除key,* 第四個如果為false，則表示刪除后，不移動節點**/final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {// tab 哈希數組，p 數組下標的節點，n 長度，index 當前數組下標Node<K,V>[] tab; Node<K,V> p; int n, index;// 哈希數組不為null，且長度大于0，然后獲得到要刪除key的節點所在是數組下標位置if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {// nodee 存儲要刪除的節點，e 臨時變量，k 當前節點的key，v 當前節點的valueNode<K,V> node = null, e; K k; V v;// 如果數組下標的節點正好是要刪除的節點，把值賦給臨時變量nodeif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;// 也就是要刪除的節點，在鏈表或者紅黑樹上，先判斷是否為紅黑樹的節點else if ((e = p.next) != null) {if (p instanceof TreeNode)// 遍歷紅黑樹，找到該節點并返回node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else { // 表示為鏈表節點，一樣的遍歷找到該節點do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}/*** 注意，如果進入了鏈表中的遍歷，那么此處的p不再是數組下標的節點，* 而是要刪除結點的上一個結點**/p = e;} while ((e = e.next) != null);}}// 找到要刪除的節點后，判斷!matchValue，我們正常的remove刪除，!matchValue都為trueif (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {// 如果刪除的節點是紅黑樹結構，則去紅黑樹中刪除if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);// 如果是鏈表結構，且刪除的節點為數組下標節點，也就是頭結點，直接讓下一個作為頭else if (node == p)tab[index] = node.next;else /*** 為鏈表結構，刪除的節點在鏈表中，把要刪除的下一個結點設為上一個結點的下一個節點**/p.next = node.next;// 修改計數器++modCount;// 長度減一--size;/*** 此方法在hashMap中是為了讓子類去實現，主要是對刪除結點后的鏈表關系進行處理**/afterNodeRemoval(node);// 返回刪除的節點return node;}}// 返回null則表示沒有該節點，刪除失敗return null;}

獲取方法

public V get(Object key) {Node<K,V> e;//也是調用getNode方法來完成的return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) {// first 頭結點，e 臨時變量，n 長度,k keyNode<K,V>[] tab; Node<K,V> first, e; int n; K k;// table不為空 && table長度大于0 && table索引位置(根據hash值計算出)節點不為空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// first的key等于傳入的key則返回first對象if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//first的key不等于傳入的key則說明是鏈表，向下遍歷if ((e = first.next) != null) {// 判斷是否為TreeNode，是則為紅黑樹// 如果是紅黑樹節點，則調用紅黑樹的查找目標節點方法getTreeNodeif (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//走下列步驟表示是鏈表，循環至節點的key與傳入的key值相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//找不到符合的返回空return null;}

計算哈希

static final int hash(Object key) {int h;// 如果key == null 則將數據存入下標0的位置return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

總結：

• 所以key值可以為null，存入下標0的位置
• 默認創建的hashmap默認長度為16
• HashMap使用的是懶加載，構造完HashMap對象后，只要不進行put 方法插入元素，HashMap并不會去初始化或者擴容table。當首次調用put方法時，HashMap會發現table為空然后調用resize方法進行初始化

總結

以上是生活随笔為你收集整理的【源码解析】hashMap源码跟进的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。