Java SE | 集合架構 | HashMap 面試必備

1. 概述

HashMap

檢視HashSet的源碼會發現Set的底層建構便用到了HashMap，由此可見學習HashMap對于集合的學習幫助莫大。

/**
  * HashSet部分源碼
 */
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

2. HashMap 類關系圖

Java SE | 集合架構 | HashMap 面試必備

3. HashMap 的屬性

Java SE | 集合架構 | HashMap 面試必備

初始容量預設大小為 16 ，當負載因子為 0.75 時 HashMap 容量達到 12 就會自動擴容為原來的 2 倍，初始容量小了會增加擴容次數導緻性能損耗，初始容量大了會影響周遊速度。
負載因子預設值為 0.75 ，負載因子大了可以減少擴容次數但是會導緻哈希沖突的可能性增加，負載因子小了可以減小哈希沖突的可能性，但是會增加擴容次數。
注意： HashMap 不是直接将 key 的 hash
值直接使用，而是将他的高16位做異或操作，由此增加離散度，進而大大降低哈希沖突的可能性。

見以下源碼：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

4. 資料結構

HashMap 在JDK1.7到1.8它的資料結構發生了改變。
JDK1.7版本中 HashMap 采用數組+連結清單（散清單）
JDK1.8版本後 HashMap 使用數組+連結清單（散清單）+紅黑樹的資料結構。單連結清單長度大于等于 8 并且哈希桶大于等于 64 的時候，會将單連結清單轉化為紅黑樹儲存。紅黑樹的節點數量小于等于 6 的時候，會将紅黑樹再轉化為一個單連結清單的形式存儲。
注意：

5.擴容機制

擴容時首先會檢測數組中的元素個數，根據哈希桶容量（預設16）和負載因子（預設0.75），這倆乘起來相當于一個門檻值（預設12），如果元素占用大于這個門檻值時就會觸發一個擴容，将之前的哈希桶（預設容量）擴容成原來的二倍，并且會把之前桶中的元素重新進行一個哈希運算，将新值重新賦給各個元素，然後按照連結清單或者紅黑樹的方法排列起來。

5. 核心方法

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)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
    }

resize() 方法

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            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;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        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;
                                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;
    }

get() 方法

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * Implements Map.get and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    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) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

6. 線程安全

多線程put時會有資料覆寫的可能
1.7的時候它put的時候會有一個resize的過程，這個過程因為它的頭插會有可能使它形成一個環形連結清單，導緻它的一個死循環。
注意：1.7和1.8版本的 HashMap 都不能保證線程安全，用ConcurrentHashMap作為替代品最佳，畢竟要兼顧效率和安全問題很難做到完美，是以我們大可在不需要考慮安全問題時使用HashMap，反之使用ConcurrentHashMap就好。

7. HashMap與HashTable

HashMap ：線程不安全，效率高，KV允許為null
HashTable ：線程安全，效率低下，KV不允許為null

HashMap與HashTable實作原理基本相同且1.7之前的資料結構也是相同的，當下不考慮線程安全問題時完全可以使用HashMap，如果有線程安全問題，一般也會直接使用ConcurrentHashMap來保證一個安全問題，是以HashTable僅作為了解就好，後面的ConcurrentHashMap是重點！

8. LinkedHashMap

9. ConcurrentHashMap 解決線程安全

1.7底層使用分片數組，為保證線程安全使用了一個分段鎖Segment。
1.8改用和HashMap相同的資料結構，并且不再使用Segment而使用Synchronized加CAS鎖來操作，CAS（Compare And Swap 比較并替換）是一個輕量級的鎖，它是一個樂觀鎖，低并發的情況下性能較好，缺點：并發量大時會有忙循環的過程，對性能損耗很大，另外它可能産生一個ABA的問題，就是說第一次讀和過段時間再讀，這中間可能被第三人修改過，但是他又給改回來了，可能通過加版本号或标志來解決ABA問題。

Java SE | 集合架構 | HashMap 面試必備

1. 概述

2. HashMap 類關系圖

3. HashMap 的屬性

4. 資料結構

5.擴容機制

5. 核心方法

6. 線程安全

7. HashMap與HashTable

8. LinkedHashMap

9. ConcurrentHashMap 解決線程安全

繼續閱讀

關于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