java8中HashMap哈希表的簡單介紹

導讀：資料結構哈希表也稱散串列，是一種鍵(key) 值（value）映射關系的資料結構，這種結構在java中是通過HashMap類實作的，接下來我們一起來學習這個類，

1.類核心成員

HashMap類底層原理是維護陣列、單向鏈表、紅黑樹實作哈希表，該中核心成員分別是：

1.table是Node型別的陣列

2.Node是單向鏈表

3.TreeNode是紅黑樹

package java.util; 

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable { 
    
    transient Node<K,V>[] table;//table是Node型別的資料

    static class Node<K,V> implements Map.Entry<K,V> {} //單向鏈表

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {} //紅黑樹
}

2.哈希表本質

在java8中,哈希表是HashMap型別的實體，這個實體本質是一個陣列，陣列元素是Node型別，或者是紅黑樹TreeNode，其中TreeNode是Node的派生類，在向這個陣列添加資料的時候，Node與TreeNode會相互轉換，從而降低時間復雜度，

//TreeNode繼承LinkedHashMap類中內部類Entry
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}

//Entry繼承HashMap類中內部類Node
static class Entry<K,V> extends HashMap.Node<K,V> {}

3.哈希表的鍵(key)-值(value)映射關系的實作

陣列資料結構是下標是int型別，從下標0開始，那么鍵(key)是如何實作映射關系的呢？

在putVal()方法中有這么一句代碼 tab[i = (n - 1) & hash]，i是陣列tab的下標，tab下標值范圍0~(n-1)，hash是key通過哈希函式生成的值，同一個key生成的hash值是一樣的，(n-1)&hash運算的結果在 0~（n-1）范圍，也就是陣列tab下標范圍，從而實作了key值對陣列下標的對應，同學們一定發現了不同的key值hash后有可能結果相同，比如“Aa”和“BB”的hash值相同，會導致陣列下標碰撞，那么這個類是如何處理，保存資料呢?

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//保存key的hash值
        final K key;//保存key值
        V value;//保存value值
        Node<K,V> next; //保存下一個Node元素的值
}

4.哈希表保存值的流程

1.判斷陣列下標是否有值，這個下標為空則寫入這個Node

2.如果陣列下標有值，則處理下標碰撞

2.1 如果坑位元素p的哈希值與新元素的哈希值相同,并且元素p的key值與新元素key相同 或者 key不為null并且key.equals(k)，則為視為同一個key值，不做處理;

2.2 如果坑位元素p是TreeNode，則寫入TreeNode;

2.3 不是TreeNode就是Node型別，則加入鏈表Node尾部，

以上就是HashMap保存元素以及處理下標碰撞的流程，

//回傳V值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果tab為null或者長度為0
        if ((tab = table) == null || (n = tab.length) == 0)
            //n的值是陣列的長度
            n = (tab = resize()).length;
        //key值hash后與陣列長度減1位，位運算后獲取陣列下標，并判斷改下標陣列元素是否為空
        if ((p = tab[i = (n - 1) & hash]) == null)
            //這個下標元素為空則賦值
            tab[i] = newNode(hash, key, value, null);
        else {//發生處理下標碰撞
            //宣告一個Node型別區域變數e,K型別(與實參型別一致的型別)的k
            Node<K,V> e; K k;
            //p為已經存在的舊元素
            //如果坑位元素p的哈希值與新元素的哈希值相同,
            if (p.hash == hash &&
                //并且坑位元素p的key值與新元素key相同 或者 key不為null并且key.equals(k)
                //則為視為一個元素,不做任何處理（即去重）
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果坑位元素p是紅黑樹TreeNode型別，則寫入這個紅黑樹
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //不是紅黑樹TreeNode，只能是Node單向鏈表
            else {
                //無限回圈
                for (int binCount = 0; ; ++binCount) {
                    //e值為鏈表的下一個
                    if ((e = p.next) == null) {
                        //鏈表尾處追加
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        //退出回圈
                        break;
                    }
                    //并且坑位元素p的key值與新元素key相同 或者 key不為null并且key.equals(k)
                    //則為視為一個元素,不做任何處理（即去重）
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //p的值也為鏈表的最后一個
                    p = e;
                }
            }
            
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }