一、哈希表（Hash Table）

1、概念

• 哈希表也叫做散列表。
• 哈希表的原理：

image

• 利用哈希函數(shù)生成key對(duì)應(yīng)的index，時(shí)間復(fù)雜度O(1)。
• 根據(jù)index(索引)操作定位數(shù)組元素，時(shí)間復(fù)雜度O(1)。
• 哈希表的空間換時(shí)間的典型應(yīng)用。

2、哈希沖突

image

• 哈希沖突也叫做哈希碰撞。
  • 2個(gè)不同的key，經(jīng)過哈希函數(shù)計(jì)算出相同的結(jié)果。
  • key1 != key2，hash(key1) = hash(key2)
• 解決哈希沖突的常見方法
  • 按照一定規(guī)則（線性探測，平方探測）向其他地址探測，直到遇到空桶。（開放定址法）
  • 設(shè)計(jì)多個(gè)哈希函數(shù)。（再哈希法）
  • 通過鏈表將同一index的元素串起來。（鏈地址法）

image

3、JDK1.8的哈希沖突解決方案

image

• 默認(rèn)使用單向鏈表將元素串起來。
• 當(dāng)單向鏈表的節(jié)點(diǎn)數(shù)量大于8時(shí)，將轉(zhuǎn)為紅黑樹來存儲(chǔ)元素。在調(diào)整容量時(shí)，如果樹節(jié)點(diǎn)數(shù)量小于6，又會(huì)轉(zhuǎn)為單向鏈表。
• 為什么不使用雙向鏈表，而是單向鏈表？
  • 每次查找都要從單向鏈表頭節(jié)點(diǎn)開始遍歷，首先確認(rèn)鏈表中是否已有該元素，若沒有則插入。
  • 單向鏈表比雙向鏈表少一個(gè)指針，可以節(jié)省內(nèi)存空間。

4、哈希函數(shù)

• 哈希表中哈希函數(shù)的實(shí)現(xiàn)步驟：
  • 生成key的哈希值（必須是整數(shù)）。
  • 再讓key的哈希值跟數(shù)組的大小進(jìn)行相關(guān)運(yùn)算，生成一個(gè)索引值。

image

• 為了提高效率，可以使用&與運(yùn)算取代%運(yùn)算（前提將數(shù)組的長度設(shè)計(jì)為2^n）。

image

• 因?yàn)閿?shù)組長度為為2^n，轉(zhuǎn)換為二進(jìn)制是10000或100之類的值，table.length - 1的結(jié)果轉(zhuǎn)換成二進(jìn)制即為01111或011之類的值。
• 將hash_code(key)和01111做與運(yùn)算，比如10100&00111，結(jié)果為00101，值肯定小于00111，且最小為00000，最大為00111。
• 結(jié)論就是無論hash_code(key)有多大，當(dāng)它與上table.length - 1，它的值都是在0到table.length - 1之間。
• 良好的哈希函數(shù)是讓哈希值更加均勻的分布，減少哈希沖突次數(shù)，提升哈希表的性能。

5、如何生成hash_code(key)

• key的常見種類可能是有整數(shù)，浮點(diǎn)數(shù)，字符串，自定義對(duì)象。
• 不同種類的key，哈希值的生成方式不一樣，但目標(biāo)是一致的：
  • 盡量讓每個(gè)key的哈希值是唯一的。
  • 盡量讓key的所有信息參與運(yùn)算。

5.1、整數(shù)的哈希值

• 整數(shù)的哈希值則直接為它的值，比如10的哈希值就是10。

5.2、浮點(diǎn)數(shù)的哈希值

• 浮點(diǎn)數(shù)的哈希值是將存儲(chǔ)的二進(jìn)制格式轉(zhuǎn)為整數(shù)值。
• 比如10.6在內(nèi)存中是01010010101，那么將01010010101轉(zhuǎn)為整數(shù)即為1093245338。

5.2、Long和Double的哈希值

• java中的hash值必須是整數(shù)，即是32位。
• Long和Double都是64位，可以將value的高32位和低32位混合計(jì)算出32位的值，然后再用value的值與這個(gè)32位值做亦或運(yùn)算（相同為0，不同為1）。
• 亦或運(yùn)算之后再將64位的結(jié)果強(qiáng)制轉(zhuǎn)換為32位。

image

image

• 最終獲取的值是橙色部分。
• 這樣即充分利用所有信息計(jì)算出了哈希值。

5.3、字符串的哈希值

• 比如字符串jack，由j、a、c、k四個(gè)字符組成（字符的本質(zhì)就是一個(gè)整數(shù)，因?yàn)榭梢赞D(zhuǎn)換成ascII碼）
• 因此jack的哈希值可以表示為j*n^3 + a*n^2 + c*n^1 + k*n^0。

5.4、自定義對(duì)象的哈希值

• 默認(rèn)情況下，自定義對(duì)象的哈希值是跟內(nèi)存地址有關(guān)系的。
• 所以兩個(gè)對(duì)象即使各個(gè)屬性值都相同，但他們的哈希值是不同的，如果用一個(gè)字典保存這兩個(gè)對(duì)象，字典內(nèi)會(huì)有兩個(gè)對(duì)象。
• 如何能讓字典中只保存相同對(duì)象中的一個(gè)呢？這就需要我們重寫hashCode函數(shù)。

image

• 重寫的hashCode函數(shù)，我們將對(duì)象所有屬性都計(jì)算進(jìn)來，這樣即充分利用所有信息計(jì)算出了哈希值。
• 當(dāng)哈希沖突的時(shí)候，我們會(huì)調(diào)用對(duì)象的equals函數(shù)進(jìn)行對(duì)象間的比較。如果兩個(gè)對(duì)象相同，則覆蓋，如果不同，則加入到value鏈表中。所以我們也需要重寫equals函數(shù)。
• 哈希值相同的兩個(gè)對(duì)象，不一定相等，只能說兩個(gè)對(duì)象通過hashCode算出的索引值相同。

5.5、自定義對(duì)象存儲(chǔ)舉例

• 假設(shè)我們創(chuàng)建三個(gè)對(duì)象存入map中，并且p1和test的哈希值相同：

image

• 當(dāng)存入p1和test時(shí)，map中的結(jié)構(gòu)如下：

image

• 當(dāng)存入p2時(shí)，會(huì)調(diào)用equals函數(shù)比較p1和p2

，因?yàn)橹貙懥?code>equals函數(shù)，所以會(huì)返回true，在map中，當(dāng)確認(rèn)兩個(gè)對(duì)象相等時(shí)，則會(huì)執(zhí)行替換：

image

二、哈希表的接口設(shè)計(jì)（HashMap）

• 用Map實(shí)現(xiàn)一個(gè)哈希表（HashMap）
• 通過一個(gè)數(shù)組保存key（索引）。
• key對(duì)應(yīng)的value（數(shù)據(jù)）則直接保存紅黑樹的根節(jié)點(diǎn)。

public class HashMap<K, V> implements Map<K, V> {
    private Node<K, V>[] table;
    protected static class Node<K, V> //聲明一個(gè)節(jié)點(diǎn)類
    private static final int DEFAULT_CAPACITY = 1 << 4; //數(shù)組默認(rèn)長度，16

    public HashMap() {
        table = new Node[DEFAULT_CAPACITY]; //建議長度為2^n
    }
}
復(fù)制代碼

三、哈希表的實(shí)現(xiàn)（HashMap）

1、聲明節(jié)點(diǎn)

protected static class Node<K, V> {
    int hash;
    K key;
    V value;
    boolean color = RED;
    Node<K, V> left;
    Node<K, V> right;
    Node<K, V> parent;
    public Node(K key, V value, Node<K, V> parent) {
        this.key = key;
        int hash = key == null ? 0 : key.hashCode();
        this.hash = hash ^ (hash >>> 16);
        this.value = value;
        this.parent = parent;
    }

    public boolean hasTwoChildren() {
        return left != null && right != null;
    }

    public boolean isLeftChild() {
        return parent != null && this == parent.left;
    }

    public boolean isRightChild() {
        return parent != null && this == parent.right;
    }

    public Node<K, V> sibling() {
        if (isLeftChild()) { return parent.right; }
        if (isRightChild()) { return parent.left; }
        return null;
    }

    @Override
    public String toString() {
        return "Node_" + key + "_" + value;
    }
}
復(fù)制代碼

2、clean實(shí)現(xiàn)

• 遍歷數(shù)組，清空數(shù)組的每一個(gè)節(jié)點(diǎn)。

@Override
public void clear() {
    if (size == 0) return;
    size = 0;
    for (int i = 0; i < table.length; i++) {
        table[i] = null;
    }
}
復(fù)制代碼

3、put實(shí)現(xiàn)

• 在進(jìn)行插入操作時(shí)，通過比較key和key.parent的哈希值大小，來決定插入位置。
• 如果哈希值相同，則比較equals。
• 如果equals相同，則比較類名。
• 如果類名相同（同一種類型），則查看是否實(shí)現(xiàn)comparable，如果實(shí)現(xiàn)，則直接通過該函數(shù)比較。
• 如果相同類型，不具有可比較性，或其中一個(gè)數(shù)據(jù)為空，則比較內(nèi)存地址。
• 直接比較內(nèi)存地址會(huì)導(dǎo)致結(jié)果不穩(wěn)定，應(yīng)該先掃碼樹中是否有該值，如果沒有，再比較內(nèi)存地址。

@Override
public V put(K key, V value) {
    resize();

    int index = index(key); // 獲取key對(duì)應(yīng)的索引
    Node<K, V> root = table[index]; // 取出index位置的紅黑樹根節(jié)點(diǎn)
    if (root == null) { // 如果根節(jié)點(diǎn)為空
        root = createNode(key, value, null);
        table[index] = root;
        size++;
        fixAfterPut(root);
        return null;
    }

    //  如果根節(jié)點(diǎn)不為空，添加新的節(jié)點(diǎn)到紅黑樹上面
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = key;
    int h1 = hash(k1);
    Node<K, V> result = null;
    boolean searched = false; // 是否已經(jīng)搜索過這個(gè)key
    do {
        parent = node;
        K k2 = node.key;
        int h2 = node.hash;
        // 根據(jù)哈希值來進(jìn)行比較，大的放右邊，小的放左邊。
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1;
        } else if (Objects.equals(k1, k2)) {
            cmp = 0;
        } else if (k1 != null && k2 != null 
            && k1 instanceof Comparable
            && k1.getClass() == k2.getClass()
            && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
        } else if (searched) { // 已經(jīng)掃描了
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        } else { // searched == false; 還沒有掃描，然后再根據(jù)內(nèi)存地址大小決定左右
        if ((node.left != null && (result = node(node.left, k1)) != null)
        || (node.right != null && (result = node(node.right, k1)) != null)) {
            // 已經(jīng)存在這個(gè)key
            node = result;
            cmp = 0;
        } else { // 不存在這個(gè)key
            searched = true;
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2); //根據(jù)內(nèi)存地址計(jì)算出的hashcode
        }
    }

    if (cmp > 0) { // 大于
        node = node.right;
    } else if (cmp < 0) { //小于
        node = node.left;
    } else { // 相等
        V oldValue = node.value;
        node.key = key;
        node.value = value;
        node.hash = h1;
        return oldValue;
    }
} while (node != null);

// 看看插入到父節(jié)點(diǎn)的哪個(gè)位置
Node<K, V> newNode = createNode(key, value, parent);
if (cmp > 0) {
    parent.right = newNode;
} else {
    parent.left = newNode;
}
size++;

// 新添加節(jié)點(diǎn)之后的處理
fixAfterPut(newNode);
return null;
}

/**
* 根據(jù)key生成對(duì)應(yīng)的索引（在桶數(shù)組中的位置）
*/
private int index(K key) {
    return hash(key) & (table.length - 1); //先求哈希值，再做位運(yùn)算
}

private int hash(K key) {
    if (key == null) return 0;
    int hash = key.hashCode();
    return hash ^ (hash >>> 16); //高16位與低16位做一次運(yùn)算
}
復(fù)制代碼

3、get實(shí)現(xiàn)

• 首先確定key的索，然后再尋找索引下的樹。

@Override
public V get(K key) {
    Node<K, V> node = node(key);
    return node != null ? node.value : null;
}

private Node<K, V> node(K key) {
    //根據(jù)key生成對(duì)應(yīng)的索引
    //根據(jù)索引在數(shù)組中找到根節(jié)點(diǎn)。
    Node<K, V> root = table[index(key)];
    return root == null ? null : node(root, key); 
}

private Node<K, V> node(Node<K, V> node, K k1) {
    int h1 = hash(k1);
    // 存儲(chǔ)查找結(jié)果
    Node<K, V> result = null;
    int cmp = 0;
    while (node != null) {
        K k2 = node.key;
        int h2 = node.hash;
        // 先比較哈希值
        if (h1 > h2) {
            node = node.right;
        } else if (h1 < h2) {
            node = node.left;
        } else if (Objects.equals(k1, k2)) { //可比較性
            return node;
        } else if (k1 != null && k2 != null 
                && k1 instanceof Comparable
                && k1.getClass() == k2.getClass()
                && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
                node = cmp > 0 ? node.right : node.left;
        } 
        // 走到這里，表示哈希值相等，不具備可比較性，也不 equals
        else if (node.right != null && (result = node(node.right, k1)) != null) { //先找右子樹
            return result;
        } else { // 再去左邊掃碼
            node = node.left;
        }
    }
    return null;
}
復(fù)制代碼

4、remove實(shí)現(xiàn)

@Override
public V remove(K key) {
    return remove(node(key));
}

protected V remove(Node<K, V> node) {
    if (node == null) return null;

    Node<K, V> willNode = node;

    size--;

    V oldValue = node.value;

    if (node.hasTwoChildren()) { // 度為2的節(jié)點(diǎn)
        // 找到后繼節(jié)點(diǎn)
        Node<K, V> s = successor(node);
        // 用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值
        node.key = s.key;
        node.value = s.value;
        node.hash = s.hash;
        // 刪除后繼節(jié)點(diǎn)
        node = s;
    }

    // 刪除node節(jié)點(diǎn)（node的度必然是1或者0）
    Node<K, V> replacement = node.left != null ? node.left : node.right;
    int index = index(node);

    if (replacement != null) { // node是度為1的節(jié)點(diǎn)
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度為1的節(jié)點(diǎn)并且是根節(jié)點(diǎn)
            table[index] = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
        // 刪除節(jié)點(diǎn)之后的處理
        fixAfterRemove(replacement);
    } else if (node.parent == null) { // node是葉子節(jié)點(diǎn)并且是根節(jié)點(diǎn)
        table[index] = null;
    } else { // node是葉子節(jié)點(diǎn)，但不是根節(jié)點(diǎn)
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
        // 刪除節(jié)點(diǎn)之后的處理
        fixAfterRemove(node);
    }

    // 交給子類去處理
    afterRemove(willNode, node);
    return oldValue;
}
復(fù)制代碼

5、containsValue實(shí)現(xiàn)

• 檢測哈希表中是否存在某值，只有遍歷每一個(gè)樹，使用層序遍歷實(shí)現(xiàn)。

@Override
public boolean containsValue(V value) {
    if (size == 0) return false;
    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < table.length; i++) {
        if (table[i] == null) continue;

        queue.offer(table[I]);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (Objects.equals(value, node.value)) return true;

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return false;
}
復(fù)制代碼

6、擴(kuò)容

• 當(dāng)哈希表的table數(shù)組中添加元素過多后，哈希沖突概率增大，效率變低。所以要根據(jù)裝填因子判斷是否需要擴(kuò)容。
• 裝填因子：節(jié)點(diǎn)總數(shù)量 / 哈希表桶數(shù)組長度，也叫做負(fù)載因子。
• 在JDK1.8的HashMap中，如果裝填因子超過0.75，就擴(kuò)容為原來的2倍。
• 如果裝填因子超過0.75，就將數(shù)組長度擴(kuò)大為原來的兩倍，并將原來的數(shù)據(jù)遷移進(jìn)新數(shù)組。
• 擴(kuò)容之后，原來數(shù)據(jù)算出的節(jié)點(diǎn)值就有可能不一樣了（保持不變或index = index + 舊容量），因?yàn)楣?jié)點(diǎn)的計(jì)算需要涉及到table.length。

private void resize() {
    // 裝填因子 <= 0.75
    if (size / table.length <= DEFAULT_LOAD_FACTOR) return;

    Node<K, V>[] oldTable = table;//保留舊的數(shù)組
    table = new Node[oldTable.length << 1];//將數(shù)組長度變?yōu)樵瓉淼?倍

    //層序遍歷
    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < oldTable.length; i++) {
        if (oldTable[i] == null) continue;

        queue.offer(oldTable[I]);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

            // 挪動(dòng)代碼得放到最后面
            moveNode(node);
        }
    }
}

private void moveNode(Node<K, V> newNode) {
    // 重置節(jié)點(diǎn)屬性
    newNode.parent = null;
    newNode.left = null;
    newNode.right = null;
    newNode.color = RED;

    int index = index(newNode);
    // 取出index位置的紅黑樹根節(jié)點(diǎn)
    Node<K, V> root = table[index];
    if (root == null) {
        root = newNode;
        table[index] = root;
        fixAfterPut(root);
        return;
    }

    // 添加新的節(jié)點(diǎn)到紅黑樹上面
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = newNode.key;
    int h1 = newNode.hash;
    do {
        parent = node;
        K k2 = node.key;
        int h2 = node.hash;
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1; // 不用再比較equals，因?yàn)椴粫?huì)存在重復(fù)數(shù)據(jù)。
        } else if (k1 != null && k2 != null 
                && k1 instanceof Comparable
                && k1.getClass() == k2.getClass()
                && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
        } else { // 搜索也不需要，原因同上。
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        }

        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        }
    } while (node != null);

    // 看看插入到父節(jié)點(diǎn)的哪個(gè)位置
    newNode.parent = parent;
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }

    // 新添加節(jié)點(diǎn)之后的處理
    fixAfterPut(newNode);
}
復(fù)制代碼

7、equals的優(yōu)化

• 我們?cè)谔砑釉貢r(shí)，要謹(jǐn)防因equals的函數(shù)實(shí)現(xiàn)有問題，導(dǎo)致a.equals(b)和b.equals(a)的結(jié)果不一致。
• 所以在實(shí)現(xiàn)equals函數(shù)時(shí)，要遵循以下條件：

image

四、TreeMap VS HashMap

• TreeMap增刪改查都是O(logn)級(jí)別，而哈希表是O(1)級(jí)別。
• 當(dāng)元素具備可比較性且要求升序遍歷時(shí)，使用TreeMap。當(dāng)對(duì)遍歷沒有要求時(shí)，選擇HashMap。

五、LinkedHashMap

• 在HashMap的基礎(chǔ)上維護(hù)元素的添加順序，使得遍歷的結(jié)果是遵循添加順序的。
• 假設(shè)添加順序是37，21，31，41，97，95，52，42，83

image

六、LinkedHashMap的接口實(shí)現(xiàn)

• 新增first和last兩個(gè)屬性。

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private LinkedNode<K, V> first;
    private LinkedNode<K, V> last;
}
復(fù)制代碼

• 給Node增加前驅(qū)和后繼兩個(gè)指針。

private static class LinkedNode<K, V> extends Node<K, V> {
    LinkedNode<K, V> prev;
    LinkedNode<K, V> next;
    public LinkedNode(K key, V value, Node<K, V> parent) {
        super(key, value, parent);
    }
}
復(fù)制代碼

• 添加一個(gè)構(gòu)造節(jié)點(diǎn)的函數(shù)。

@Override
protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
    LinkedNode node = new LinkedNode(key, value, parent);
    if (first == null) { //沒有頭節(jié)點(diǎn)
        first = last = node;
    } else { //有頭節(jié)點(diǎn)
        last.next = node;
        node.prev = last;
        last = node;
    }
    return node;
}
復(fù)制代碼

• clear函數(shù)需要清空first和last指針。

@Override
public void clear() {
    super.clear();
    first = null;
    last = null;
}
復(fù)制代碼

• 遍歷函數(shù)

@Override
public void traversal(Visitor<K, V> visitor) {
    if (visitor == null) return;
    LinkedNode<K, V> node = first;
    while (node != null) {
        if (visitor.visit(node.key, node.value)) return;
        node = node.next;
    }
}
復(fù)制代碼

• 刪除函數(shù)，不僅僅需要?jiǎng)h除數(shù)據(jù)，還需要修改指針指向。
• 刪除度為2的節(jié)點(diǎn)時(shí)，需要注意更換node與前驅(qū)/后繼節(jié)點(diǎn)的鏈接位置。
• 例如，刪除31

image

@Override
protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) {
    LinkedNode<K, V> node1 = (LinkedNode<K, V>) willNode;
    LinkedNode<K, V> node2 = (LinkedNode<K, V>) removedNode;

    if (node1 != node2) {
        // 交換linkedWillNode和linkedRemovedNode在鏈表中的位置
        // 交換prev
        LinkedNode<K, V> tmp = node1.prev;
        node1.prev = node2.prev;
        node2.prev = tmp;
        if (node1.prev == null) {
            first = node1;
        } else {
            node1.prev.next = node1;
        }
        if (node2.prev == null) {
            first = node2;
        } else {
            node2.prev.next = node2;
        }

        // 交換next
        tmp = node1.next;
        node1.next = node2.next;
        node2.next = tmp;
        if (node1.next == null) {
            last = node1;
        } else {
            node1.next.prev = node1;
        }
        if (node2.next == null) {
            last = node2;
        } else {
            node2.next.prev = node2;
        }
    }

    LinkedNode<K, V> prev = node2.prev;
    LinkedNode<K, V> next = node2.next;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
    }
}
復(fù)制代碼

• 核心就是交換。

image

• 遍歷節(jié)點(diǎn)

@Override
public boolean containsValue(V value) {
    LinkedNode<K, V> node = first;
    while (node != null) {
        if (Objects.equals(value, node.value)) return true;
        node = node.next;
    }
    return false;
}
復(fù)制代碼