（一）Hashmap设计和问题

Java的 Hashmap以及相应的优化是面试的常见知识点，面试是为了选拔，涉及逻辑推理的地方往往有难度，有些点能拉开人和人之间的差距。 所以想和大家一起推理一遍其中的重点和难点，推理完之后希望hashmap这个老大难问题变得不再困难。

hashmap是怎么实现的

hashmap的实现基本原理很简单：

• 哈希数组单链桶
• table数组来放桶 如下经典的图：

put过程

• put方法先算key
• 如果存在则覆盖
• 不在就用addEntry
• 先判是否要扩容

判断扩容

• 负载因子判扩容
• 容量两倍扩充桶
• 现有数据重哈希

put命中桶

• 新的Entry桶头部
• 原有链表放next

null key 处理

put/get过程会特殊处理key为空的情况，认为null的hash值为0.

get过程

get先计算出key的哈希，定位到桶，然后在单链表上面遍历。直到找到相等的key,如果遍历完链表都没有找到，就是不存在这个key,返回null。

• get方法先算key
• 找到桶来遍历key
• 直到key等来返回

红黑树优化查找效率

• 1.8加入红黑树
• 链表长也效率高
• 查询效率LogN

有什么问题？死循环

如果是在单线程下使用hashmap,自然是没问题的。如果引入多线程并发，可能会发现CPU占用100%，居高不下。通过查看堆栈，你会惊讶的发现，线程都hang在hashmap的get方法上，服务重启之后，问题消失。

这是为什么？

其实就是要推理这个问题。

如上所述，hashmap使用一个Entry数组来保存key,value数组。存在hash冲突的时候，entry通过链表串起来。 扩容的时候会新建一个更大的数组，并通过transfer方法，移动元素。 移动的逻辑也很清晰，遍历原来table中每个桶的链表，并对每个元素进行重hash,在新的newTable找到归宿。

这是Java 1.7实现的一段代码：

   void resize(int newCapacity) { //传入新的容量
        Entry[] oldTable = table;  //引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到（2^30）了
            threshold = Integer.MAX_VALUE;  //修改阈值为 int 的最大值（2^31-1），这样以后都不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的 Entry 数组
        transfer(newTable); //用来将原先table的元素全部移到newTable里面
        table = newTable;  //再将newTable赋值给table
        threshold = (int)(newCapacity * loadFactor);//修改阈值
    } 

   void resize(int newCapacity) { //传入新的容量
        Entry[] oldTable = table;  //引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到（2^30）了
            threshold = Integer.MAX_VALUE;  //修改阈值为 int 的最大值（2^31-1），这样以后都不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的 Entry 数组
        transfer(newTable); //用来将原先table的元素全部移到newTable里面
        table = newTable;  //再将newTable赋值给table
        threshold = (int)(newCapacity * loadFactor);//修改阈值
    } 

那为什么这个实现会出现问题呢？

假设此时线程1和线程2 put的时候都发生扩容， 此时线程1的局部变量e和next的值如下.

如果CPU时间片切换到线程2，线程2完成搬移，假设a,b,c的哈希还是位于同一个桶，结果如下

a,b,c还是位于同一个桶，但是根据上面的代码逻辑，采用头插法，我们可以知道这几个Entry在链表中的顺序和原来相反。

此时继续切换到线程1运行，则线程1的newtable会形成环,如下

在线程1，e是a,next是b,而因为线程2的搬移，b的next是a,则根据以上逻辑，线程1的这个桶的链表里则会出现a,b互指的环。

假设最终线程1的扩容成功。线程1的newTable被重命名为table 此时再get数据，哈希命中这个桶，但如果查找的key上非a或b的,则会出现死循环。

总结来说， 出现死循环，导致CPU飙升，这是hashmap扩容实现的问题，总结来说是：

• 并发搬移有风险
• 新桶出现链中环
• 取key不现死循环

解决问题-1.8的实现

根本原因是，每次新插入的元素都放在链表头部，而依次搬移数据的时候也是从队头开始，所以可能出现死循环。 Java 1.8做了优化，每次新插入的元素都放在链表尾部。

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

p.next = newNode(hash, key, value, null);//尾插法