java集合–HashMap（三）

1.HashMap原理的簡單概述

在前面兩節我們搞懂了equals()方法和hashCode()方法，同時明白了什麼是散列集和HashMap的基本用法。古人說：知其然知其是以然。我們知道怎樣使用HashMap，我們還有必要知道其原理，這一節可能需要重複讀好幾遍才能看明白。

get()方法

當我們調用get()方法時，會先通過hash值計算出key進而找到該元素在桶（bucket）的位置。如果該位置上隻有一個元素則直接命中，即找到。如果該不止一個元素，則會調用equals()方法周遊連結清單進行比較，如果找到即傳回該值，沒有找到則傳回為空。
put()方法

當我們調用put()方法時，會先通過hash值計算出key映射到哪個桶（bucket）。如果桶上沒有碰撞沖突（即該桶上沒有元素），則直接插入。如果出現碰撞沖突，則以連結清單的方式插入。

2.HashMap屬性介紹

基本屬性

//預設的初始容量為 16
static final int DEFAULT_INITIAL_CAPACITY =  << ;

//最大的容量上限為 2^30
static final int MAXIMUM_CAPACITY =  << ;

//預設的負載因子為 0.75
static final float DEFAULT_LOAD_FACTOR = f;

//變成樹型結構的臨界值為 8
static final int TREEIFY_THRESHOLD = ;

//恢複鍊式結構的臨界值為 6
static final int UNTREEIFY_THRESHOLD = ;

//哈希表
transient Node<K,V>[] table;

//哈希表中鍵值對的個數
transient int size;

//哈希表被修改的次數
transient int modCount;

//它是通過 capacity*load factor 計算出來的，當 size 到達這個值時，就會進行擴容操作
int threshold;

//負載因子
final float loadFactor;

//當哈希表的大小超過這個門檻值，才會把鍊式結構轉化成樹型結構，否則僅采取擴容來嘗試減少沖突
static final int MIN_TREEIFY_CAPACITY = ;

靜态内部類

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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

上面是Node 類的定義，它是 HashMap 中的一個靜态内部類，哈希表中的每一個節點都是 Node 類型。我們可以看到，Node 類中有 4 個屬性，其中除了 key 和value 之外，還有 hash 和 next 兩個屬性。hash 是用來存儲 key 的哈希值的，next是在建構連結清單時用來指向後繼節點的。

3.HashMap方法介紹

get()方法

//get 方法主要調用的是 getNode 方法，是以重點要看 getNode 方法的實作
        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;

        //如果哈希表不為空 && key 對應的桶上不為空
        if ((tab = table) != null && (n = tab.length) >  &&
            (first = tab[(n - ) & hash]) != null) {
            //是否直接命中
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
                //判斷是否有後續節點
            if ((e = first.next) != null) {
            //如果目前的桶是采用紅黑樹處理沖突，則調用紅黑樹的 get 方法去擷取節點
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    //不是紅黑樹的話，那就是傳統的鍊式結構了，通過循環的方法判斷鍊中是否存在該 key
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

實作步驟大緻如下：

1、通過 hash 值擷取該 key 映射到的桶。

2、桶上的 key 就是要查找的 key，則直接命中。

3、桶上的 key 不是要查找的 key，則檢視後續節點：

（1）如果後續節點是樹節點，通過調用樹的方法查找該 key。

（2）如果後續節點是鍊式節點，則通過循環周遊鍊查找該 key。

put()方法

//put 方法的具體實作也是在 putVal 方法中，是以我們重點看下面的 putVal 方法
 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) == )
            n = (tab = resize()).length;
        //如果目前桶沒有碰撞沖突，則直接把鍵值對插入，完事
        if ((p = tab[i = (n - ) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果桶上節點的 key 與目前 key 重複，那你就是我要找的節點了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是采用紅黑樹的方式處理沖突，則通過紅黑樹的 putTreeVal 方法去插入這個鍵值對
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //否則就是傳統的鍊式結構
            else {
            //采用循環周遊的方式，判斷鍊中是否有重複的 key
                for (int binCount = ; ; ++binCount) {
                //到了鍊尾還沒找到重複的 key，則說明 HashMap 沒有包含該鍵
                    if ((e = p.next) == null) {
                    //建立一個新節點插入到尾部
                        p.next = newNode(hash, key, value, null);
                        //如果鍊的長度大于 TREEIFY_THRESHOLD 這個臨界值，則把鍊變為紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //找到了重複的 key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    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;
    }

put 方法比較複雜，實作步驟大緻如下：

1、先通過 hash 值計算出 key 映射到哪個桶。

2、如果桶上沒有碰撞沖突，則直接插入。

3、如果出現碰撞沖突了，則需要處理沖突：

（1）如果該桶使用紅黑樹處理沖突，則調用紅黑樹的方法插入。

（2）否則采用傳統的鍊式方法插入。如果鍊的長度到達臨界值，則把鍊轉變為紅

黑樹。

4、如果桶中存在重複的鍵，則為該鍵替換新值。

5、如果 size 大于門檻值，則進行擴容。

remove()方法

//remove 方法的具體實作在 removeNode 方法中
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果目前 key 映射到的桶不為空
    if ((tab = table) != null && (n = tab.length) >  &&
        (p = tab[index = (n - ) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //如果桶上的節點就是要找的 key，則直接命中
        if (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 = e;
                } while ((e = e.next) != null);
            }
        }
        //比對找到的 key 的 value 跟要删除的是否比對
        if (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;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

删除和插入的步驟差不多。

上面就是關于HashMap屬性和方法的主要介紹。代碼有點長，讀者初讀可以不必在意細節，隻需要了解HashMap的get()和put()的原理。

java集合–HashMap（四）

java集合--HashMap（三）java集合–HashMap（三）

java集合–HashMap（三）

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method