HashMap會(huì)分四篇博客介紹，分別是基本思想、優(yōu)化、線程安全和拓展。本文介紹基本思想。

HashMap 基本數(shù)據(jù)結(jié)構(gòu)

Java HashMap解決哈希沖突，使用了成鏈法，故采用了數(shù)組Node[]加鏈表Node.next的數(shù)據(jù)結(jié)構(gòu)。
Java8為降低鏈表查詢的時(shí)間復(fù)雜度，引入了紅黑樹TreeNode。

class HashMap<Key, Value> {

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private static final int DEFAULT_TABLE_SIZE = 16;
    private static final int TREEIFY_THRESHOLD = 8;

    private int size; // HashMap 大小，即存儲(chǔ)鍵值對(duì)的個(gè)數(shù)
    private float loadFactor; // 負(fù)載因子
    private int threshold; // 當(dāng)前 table 長(zhǎng)度和 loadFactor 負(fù)載因子下，能容下的最大鍵值對(duì)數(shù)
    private Node[] table; // 存儲(chǔ)鍵值對(duì)的數(shù)組

    public HashMap() {
        this(DEFAULT_TABLE_SIZE, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initSize, float initLoadFactor) {
        this.loadFactor = initLoadFactor;
        // table 的長(zhǎng)度必須是 2^n，后面解釋為什么這樣設(shè)計(jì)
        int tableSize = tableSizeFor(initSize);
        // JDK 源碼中 table 數(shù)組不在在構(gòu)造函數(shù)中初始化，是 resize 時(shí)初始化
        this.table = new Node[tableSize];
        // 初始化閾值
        this.threshold = (int) (this.table.length * this.loadFactor);
    }

    /**
     * 節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ) Key 和 Value
     */
    private static class Node<K, V> implements Map.Entry<K, V> {
        int hash;
        K key;
        V value;
        Node next;
    }

    /**
     * 紅黑樹數(shù)據(jù)結(jié)構(gòu)
     */
    private static class TreeNode<K, V> extends Node<K, V> {
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;

        /**
         * 將一個(gè)節(jié)點(diǎn)插入當(dāng)前的紅黑樹
         */
        TreeNode<K, V> putTreeVal(Node<K, V> node) { }
    }

    /**
     * 求大于等于 cap 且為 2^n 的數(shù)
     */
    static final int tableSizeFor(int cap) { }
}

如何存儲(chǔ) - 第一步：找桶

public void put(Key key, Value value) {
    int hashCode = key.hashCode();
    int hash = hash(hashCode);
    // 等價(jià)于 index = hash % table.length
    int index = hash & (table.length - 1);
}

/**
 * 擾動(dòng)函數(shù)：目的是增大 hashCode 的隨機(jī)性，使其更散列。
 */
private int hash(int hashCode) { }

• 問(wèn)題一：數(shù)組長(zhǎng)度為什么設(shè)計(jì)成2^n？

  用位運(yùn)算代替乘除和求余運(yùn)算，提高效率。
  擴(kuò)容是 2 倍擴(kuò)容，可以直接使用左移運(yùn)算；與運(yùn)算可代替求余運(yùn)算。

• 問(wèn)題二：為什么與運(yùn)算等價(jià)于求余運(yùn)算？

  首先明確，與運(yùn)算不等價(jià)求余運(yùn)算；m % n = m & (n-1) 當(dāng)且僅當(dāng) n 是 2 的次冪。
  例如：
  131101% 81000= (81000 + 50101) % 8 = 5（保留了 8 的后三位）
  151111% 40100= (121100 + 30011) % 4 = 3（保留了 15 的后兩位）
  上面觀察出，保留的位數(shù)正好是求模數(shù)1后面0的個(gè)數(shù)。從位運(yùn)算看，就是和這么多個(gè)1做按位與。
  即：131101% 81000= 131101 & 70111；151111% 40100= 151111 & 30011
  
  圖解

如何存儲(chǔ) - 第二步：找坑

public void put(Key key, Value value) {
    Node head = table[index];
    // 如果當(dāng)前位置還沒(méi)有存儲(chǔ)，則直接創(chuàng)建節(jié)點(diǎn)
    if (head == null) {
        table[index] = new Node<>(hashCode, key, value);
    }
    // 紅黑樹則插入
    else if (head instanceof TreeNode) {
        ((TreeNode<Key, Value>) head).putTreeVal(new Node<>(hash, key, value));
    }
    // 否則要遍歷當(dāng)前鏈表，為其找到合適位置
    else {
        int nodeCount = 0;
        Node tail = null;
        while (head != null) {
            nodeCount++;
            // 如果 key 已經(jīng)存在，則直接替換 value，直接 return，不會(huì) size++
            if (head.hash == hashCode && head.key.equals(key)) {
                head.value = value;
                return;
            }
            // 找到尾結(jié)點(diǎn)
            if (head.next == null) {
                tail = head;
            }
            head = head.next;
        }
        // 循環(huán)結(jié)束，表示遍歷到尾，未找到 key 存在，則新建一個(gè)節(jié)點(diǎn)
        tail.next = new Node<>(hashCode, key, value);
        // 鏈表長(zhǎng)度超過(guò)閾值，轉(zhuǎn)為紅黑樹
        if (nodeCount > TREEIFY_THRESHOLD) {
            treeifyBin(index);
        }
    }
    // 最后記錄鍵值對(duì)個(gè)數(shù)增加
    size++;
}

/**
 * 將 index 所在的鏈表轉(zhuǎn)換為紅黑樹
 */
private void treeifyBin(int index) { }

擴(kuò)容

private void resize() {
    if (size <= threshold) {
        return;
    }
    Node<Key, Value>[] oldTable = table;
    int oldCap = oldTable.length;
    // 計(jì)算新數(shù)組長(zhǎng)度，并初始化新數(shù)組
    int newCap = oldCap << 1;
    table = new Node[newCap];
    threshold = (int) (newCap * loadFactor);
    // 遍歷每個(gè)桶
    for (int i = 0; i < oldCap; i++) {
        Node<Key, Value> head = oldTable[i];
        if (head == null) {
            continue;
        }
        // 紅黑樹
        if (head instanceof TreeNode) {
            reassignTreeNode(head);
        }
        // 遍歷鏈表，重新分配
        else {
            reassignNodeChain(head, i, oldCap);
        }
    }
}

/**
 * 將鏈表上的節(jié)點(diǎn)重新分配
 */
private void reassignNodeChain(Node<Key, Value> head, int currentIndex, int oldCap) {
    // 將一條鏈表拆成兩條鏈表
    Node<Key, Value> lowHead = null, lowTail = null;
    Node<Key, Value> highHead = null, highTail = null;
    do {
        // 低位鏈，后面解釋為什么這樣判斷
        if ((head.hash & oldCap) == 0) {
            if (lowHead == null) {
                lowHead = head;
            }
            if (lowTail != null) {
                lowTail.next = head;
            }
            lowTail = head;
        }
        // 高位鏈
        else {
            if (highHead == null) {
                highHead = head;
            }
            if (highTail != null) {
                highTail.next = head;
            }
            highTail = head;
        }
    } while ((head = head.next) != null);
    // 將兩條鏈表放入新 table，后面解釋為什么這樣放
    table[currentIndex] = lowHead;
    table[currentIndex + oldCap] = highHead;
}

/**
 * 將紅黑樹上的節(jié)點(diǎn)重新分配
 */
private void reassignTreeNode(Node<Key, Value> head) { }

• 問(wèn)題一：為什么一條鏈表上的節(jié)點(diǎn)一定會(huì)分為兩條鏈？

  設(shè)擾動(dòng)后15，新數(shù)組長(zhǎng)度8，原索引3。
  根據(jù)上面解釋的與運(yùn)算原理，則新索引只會(huì)等于0011或0111。所以一定會(huì)分布在兩條確定的鏈上。

• 問(wèn)題二：新兩條鏈在 table 中位置如何確定？

  由問(wèn)題一觀察，0011 = 0011 | 0000或0111 = 0011 | 0100，即新索引等于原索引+0或+原數(shù)組長(zhǎng)度。
  
  圖解

• 感謝

博客中使用了如下兩篇博客中的圖片，謝謝。同時(shí)這兩篇博客也是非常好的學(xué)習(xí)HashMap的博客。
感謝 @前利 老師
感謝 @Carson_Ho 老師