面試題：你真的瞭解HashMap嗎？

HashMap可以說是Java中最常用的集合類框架之一,是Java語言中非常典型的數據結構，因此在面試中經常會被問到hashmap的問題。

1）hashmap的底層原理？

hashmap是通過數組+鏈表實現的。

調用put方法存儲數據的時候，通過hashCode方法處理key，計算出Entry在數組中存放的位置（bucket，桶）。

index = （length - 1） & HashCode（Key） （取模效率比位運算低，所以並沒有使用取模這種方式計算）

​

HashMap數組的每一個元素不止是一個Entry對象，也是一個鏈表的節點，每個Entry對象通過Next指針指向它的下一個Entry節點。當多個Entry被定位到一個數組的時候（碰撞），只需要插入到對應的鏈表即可。

調用get方法獲取數據的時候，同樣是通過hashCode方法處理key，計算出Entry在數組中存放的位置。然後通過equals()方法來尋找鍵值對。

2）hashmap的默認長度？為什麼這麼設置？

hashmap的默認長度是16。

之所為設置成16，是為了降低hash碰撞（兩個元素雖然不相同,但是hash函數的值相同）的幾率。

index = （length - 1） & HashCode（Key）

如果長度是16或者其他2的冪，length - 1的值是所有二進制位全為1（1111），index的結果等同於hashcode後幾位的值只要輸入的hashcode本身分佈均勻，hash算法的結果就是均勻的。如果是非2的冪，可能會導致分配不均勻，甚至有的bucket永遠分配不到。

所以HashMap給初始值、擴容的時候，容器大小都是2的冪次方。

3）高併發下，為什麼hashmap會出現死鎖？如何避免這種問題？

如果兩個線程同時put，發現HashMap需要重新調整大小，這時候會產生條件競爭。（java8版本以下才有該問題，頭部插入導致）

調整大小的條件：HashMap.Size >= index * LoadFactor（負載因子，默認值為0.75f，空間利用率和減少查詢成本的折中，0.75的話碰撞最小）

需要遍歷原Entry數組，然後把所有的Entry重新Hash到新數組（長度為原來的兩倍）。因為length變化了，根據index = （length - 1） & HashCode（Key），index必然也會發生改變。

在調整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap並不會將元素放在鏈表的尾部，而是放在頭部。轉移前鏈表順序是1->2，那麼轉移後就會變成2->1。

如果多個線程同時操作的時候，鏈表容易形成環形鏈表1->2、2->1。這種時候如果get方法獲取鏈表的話，就會陷入死循環。

高併發下可以使用CocurrentHashMap替代hashmap，CocurrentHashMap線程安全同時效率高。

4）java8中對hashmap做了什麼優化？

1）HashMap採用位桶+鏈表+紅黑樹實現，當鏈表長度超過閾值（8）時，將鏈表轉換為紅黑樹。提高了查詢效率，紅黑樹查詢時間是O（logn），鏈表是O(n)。

2）發生hash碰撞時，java 1.7 會在鏈表的頭部插入，而java 1.8會在鏈表的尾部插入。頭部插入效率高，不需要遍歷尾部，但是容易產生環形鏈表，引入紅黑樹後沒法頭部插入，但是紅黑樹減少了插入的成本。

5）手寫個hashmap

<code>public class Node {
    private K key;
    private V value;
    private Node next;

    public Node(K key, V value, Node next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() { 

        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}/<code>

<code>public class MyHashMap {

    Node[] table = null;

    // 默認初始大小
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 負載因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 實際大小
    static int size;

    public void put(K k, V v) {
        if (table == null) {
            table = new Node[DEFAULT_INITIAL_CAPACITY];
        }

        int index = k.hashCode() & (DEFAULT_INITIAL_CAPACITY - 1);

        Node node = table[index];

        if (node == null) { 

            table[index] = new Node<>(k, v, null);
            size++;
        } else {
            Node newNode = node;

            while (newNode != null) {
                if (k.equals(newNode.getKey()) || k == newNode.getKey()) {
                    newNode.setValue(v);
                    return;
                }

                newNode = node.getNext();
            }
            table[index] = new Node(k, v, table[index]);

            size++;
        }

    }

    public V get(K k) {
        int index = k.hashCode() & (DEFAULT_INITIAL_CAPACITY - 1);

        Node node = table[index];

        if (k.equals(node.getKey()) || k == node.getKey()) {
            return node.getValue();
        } else {
            Node nextNode = node.getNext();

            while (nextNode != null) {
                if (k.equals(nextNode.getKey()) || k == nextNode.getKey()) {
                    return nextNode.getValue();
                }
            }

        }

        return null;
    }

} 
/<code>

閱讀更多 加班狗的微博 的文章

關鍵字: 數據結構 面試題 算法