天天看點
傳回

HashMap源碼分析java運算符HashMap資料結構hash 計算原理get 取值原理put 存值原理resize 擴容原理周遊

文章目錄

  • java運算符
      • & 與運算符：
      • | 或運算符：
      • ^ 異或運算符：
      • >> 右移運算
      • >>>：無符号右移
  • HashMap資料結構
      • 預設容量
      • 最大容量
      • 擴容門檻值
      • 預設加載因子
      • 加載因子
      • 由Node轉為TreeNode的門檻值
      • 由TreeNode轉為Node的門檻值
      • 資料
      • 存儲：使用數組存儲Node節點
  • hash 計算原理
  • get 取值原理
  • put 存值原理
  • resize 擴容原理
  • 周遊

java運算符

& 與運算符： 

1&1=1
1&0=0
0&1=0
0&0=0
都為真則為真

| 或運算符： 

1|1=1
1|0=1
0|1=1
0|0=0
有一個為真則為真

^ 異或運算符： 

1^1=0
1^0=1
0^1=1
0^0=0
一樣則為假，不一樣則為真

>> 右移運算 

16>>2=16/2/2=4
32>>2=32/2/2=8
-32>>3=-32/2/2/2=-4
二進制中的數值整體向右移動，預設位置用0填充，符号位不變。

>>>：無符号右移 

16>>>2=16/2/2=4
32>>>2=32/2/2=8
-2>>1=2147483647
與

>>

 差別在于負數的運算，如果是負數，預設位置用1填充。

HashMap資料結構

預設容量

最大容量

擴容門檻值

預設加載因子

加載因子

由Node轉為TreeNode的門檻值

當map中的key的hash相同個數超過8時，會由Node轉為TreeNode。

由TreeNode轉為Node的門檻值

同上，反過來。

資料

  • Node 
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
  • TreeNode：紅黑樹 
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
    }

存儲：使用數組存儲Node節點 

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;// 不會存儲資料，通過内部方法操作table資料。

hash 計算原理 

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
上面代碼就是HashMap計算hash值原理，對hash值又進一步的計算，主要是對後面的個十百千萬進行了異或運算，更進一步避免哈希沖突吧。

以下是

String

類重寫的

hashCode()

方法。

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
加入我們使用

String

 類型作為

Key

 。哈希值最大為

2147483647

 HashMap計算結果：

Integer.MAX_VALUE ^ (Integer.MAX_VALUE >>> 16)=2147450880

 由此可以看出隻是對萬位及一下的數值進行了修改。

get 取值原理 

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
           
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {// 通過hash與容量計算出索引位置，擷取索引的資料。
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))// 判斷第一個節點的key跟查詢的key相同。比較hash和索引或者hash和equlas，這就是為什麼重寫hashcode就需要重寫equals方法了。
                return first;
            if ((e = first.next) != null) {// 不相同就周遊該節點之後的所有節點
                if (first instanceof TreeNode)// 如果是TreeNode就走TreeNode的方法
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&// 判斷節點的key是否跟查詢key相同。
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);// 知道節點的下一個節點不存在停止周遊，說明真沒有，就傳回null。
            }
        }
        return null;
    }
上面代碼核心點：

tab[(n - 1) & hash]

=>從數組中擷取索引值為[(數組長度-1) & 哈希值]的值

因為&特征是都為真才為真，是以

(n - 1) & hash

 計算結果不會超過數組長度。不會發生數組下邊越界問題。
綜上所述：map查詢值是非常快的，隻需要通過hash和數組容量計算索引位置即可。如果存在hash沖突，那麼就通過next屬性周遊擁有相同hash值的節點（最多8個）。超過8個就會轉為TreeNode。通過二分法查找。
為什麼會這麼取值呢？看接下來的存值原理。

put 存值原理 

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
           
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)// 通過hash與容量計算将要存放的索引
            tab[i] = newNode(hash, key, value, null);// 如果目前索引沒有值，那麼存儲Node
        else {// 如果目前索引已經有值，說明hash可能沖突了。
            Node<K,V> e; K k;
            if (p.hash == hash &&// 如果hash值相等，并且引用相等或者equals為true。
                ((k = p.key) == key || (key != null && key.equals(k))))// 這就是為什麼重寫hashCode就要重寫equals的原因。
                e = p;
            else if (p instanceof TreeNode)// 如果是數節點
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// hash沖突了。
                for (int binCount = 0; ; ++binCount) {// 周遊沖突值
                    if ((e = p.next) == null) {// 如果已經存在的節點.next不存在
                        p.next = newNode(hash, key, value, null);// 就将put的資料作為p.next節點
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 如果沖突超過TREEIFY_THRESHOLD = 8 - 1 那麼轉為樹結構存儲。
                            treeifyBin(tab, hash);// 轉換為樹結構存儲
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))// 判斷是否同一個key
                        break;
                    p = e;// 繼續判斷下一個節點
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)// 如果是調用的putIfAbsent()并且oldValue!=null則不會替換。
                    e.value = value;// 替換值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)// 如果大小超出了門檻值（容量*加載因子）那麼就擴容
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  • 調用put存一個key-value。

  • (n - 1) & hash

     根據key的hash值&容量-1，來計算key将要存放的索引。
  • 判斷目前的索引是否為空
    • 如果為空：說明沒有值，直接建立新的Node放到該索引位置。
    • 如果不為空：說明該索引位置已經有值了。判斷已存在的key和要存放的key是否相同。
      • 如果相同：key的hash以及引用或者equals都相同，說明是同一個key。替換為新的value。
      • 如果不同：說明hash沖突了。就需要周遊擁有相同hash的節點。判斷是否有相同的key。
        • 如果存在相同的key，那麼替換為新的value。
        • 如果不存在相同的key，那麼就建立新的Node。判斷相同的個數是否超過TREEIFY_THRESHOLD - 1。
          • 如果超過：那麼将這些重複的hash的節點轉為TreeNode。
          • 如果沒有超過：那麼将最後一個重複節點的next屬性指向新添加的Node。
綜上所述：hash沖突并不會占用數組的索引位置，而是在已存在的索引位置标記next屬性。

resize 擴容原理

  • 計算下次擴容的門檻值 
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
上述代碼用于初始化時如果自定義容量，那麼計算門檻值。預設threshold=0。
  • 初始化代碼：可以自定義初始化容量和加載因子。 
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

通過無參構造map：loadFactor=0.75 threshold=0

自定義構造map：

loadFactor = loadFactor

threshold = tableSizeFor(initialCapacity) 0->1;3>4;5>8;100>128。大于容量的最近的2的n次方值。

  • 重新修改大小 
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;// 聲明舊數組
        int oldCap = (oldTab == null) ? 0 : oldTab.length;// 聲明就容量，如果沒資料則為0，否則為數組長度。
        int oldThr = threshold;// 聲明舊門檻值
        int newCap, newThr = 0;// 聲明新容量=0,新門檻值=0。
        if (oldCap > 0) {// 如果舊容量大于0，說明map已經添加了值。
            if (oldCap >= MAXIMUM_CAPACITY) {// 如果大于最大容量
                threshold = Integer.MAX_VALUE;// 門檻值為最大容量
                return oldTab;// 傳回舊的數組
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)// 如果新容量=舊容量*2 小于最大容量，并且舊容量大于等于預設容量16
                newThr = oldThr << 1; // double threshold // 新門檻值 = 舊門檻值 * 2
        } else if (oldThr > 0) { // 說明初始化時自定義了map容量，oldThr就是初始化容量最近的2的n次方值。
            newCap = oldThr;// 如果就門檻值大于0，那麼新門檻值等于舊門檻值
        } else {// 說明通過無參構造初始化的map。新容量=預設容量，新門檻值=預設加載因子*預設容量
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {// 如果自定義了容量，會走一次這個代碼。設定門檻值=容量*加載因子
            float ft = (float)newCap * loadFactor;
            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];// 建立新容量的數組
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {// 周遊舊數組
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {// 如果不為空
                    oldTab[j] = null;// 之前索引設定為null，友善垃圾回收
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;// 如果沒有hash沖突元素，那麼重新根據hash計算索引位置并存放。
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order 有hash沖突，重新配置設定索引。
                        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) {// 如果索引位置為0
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

綜上所述：不管是否初始化容量，容量永遠是2的n次方。門檻值=容量*加載因子。

并且每次擴容都是2倍擴容。

每次擴容都會根據hash重新計算索引。

為什麼預設加載因子為0.75，為了達到一個空間和沖突率的平衡吧。

周遊 

abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot

        HashIterator() {// 初始化疊代器
            expectedModCount = modCount;// 用于fast-fail，如果再疊代期間發生modCount不一緻情況直接抛異常。
            Node<K,V>[] t = table;
            current = next = null;// 目前為空
            index = 0;
            if (t != null && size > 0) { // advance to first entry
            	// 周遊數組，找到第一個節點不為空的索引。
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }
		// 通過next是否為空判斷是否有下一個。
        public final boolean hasNext() {
            return next != null;
        }
		// 擷取下一個節點
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)// 如果資料發生改變，抛異常
                throw new ConcurrentModificationException();
            if (e == null)// e為空則抛異常
                throw new NoSuchElementException();
            // 這一行代碼用來尋找下一個節點，可能是下一個索引上，可能是目前索引上的hash沖突節點。
            if ((next = (current = e).next) == null && (t = table) != null) {
            	// 當node.next==null時，即目前索引位置的hash沖突讀取完了，才會找下一個不為空的索引。
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;// 傳回目前節點
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
由上述代碼可以得知：

key

 周遊，

value

 周遊，

entry

 周遊都是

HashIterator

 的子類。是以核心代碼就在

HashIterator

中。

主要的是

nextNode

方法，可以多看幾遍，這個方法傳回的是目前的節點，尋找的是下一個節點。

如果找不到下一個節點了，那麼就沒有元素了。

hasNode()

 方法也會傳回

false

。

如果繼續調用

nextNode()

 ，那麼會抛出

throw new NoSuchElementException();

 異常

關于TreeNode感興趣的可以去看源碼。

java hashmap
上一篇: json python無效文法,Python json.loads的無效控制字元
下一篇: HashMap簡略源碼解析

繼續閱讀