HashMap知识点总结

HashMap是一种线程不安全的

jdk1.7

底层数据结构：数组+链表
在多线程环境下回出现死循环和数据丢失的问题，问题产生是在扩容的时候进行旧表与新表的拷贝过程中

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

死循环分析：

现在有A、B两个线程同时执行，当A线程在第一次进入while循环执行完代码第5行：Entry<K,V> next = e.next;后到第二次执行第5行代码前，B线程已扩容完成，由于采用的是头插法，所以结点2指向了结点1，然后A线程执行完成，造成了循环引用

图1 A线程第一次进入while循环执行完第5行代码

图2 假设A线程执行完第5行代码后挂起，直到B线程执行完成，此时A线程中的结构

图3 A线程第二次进入while循环

图4 A线程第三次进入while循环

图5 A线程第三次while循环结束

数据丢失分析：

假设A、B两个线程同时执行，A线程执行到进入while循环时挂起，B执行完成后，A再执行

图6 A线程进入while循环前

图7 B线程执行完成后，A的结构

jdk1.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)  //1.1 结点为空时，直接创建结点
        tab[i] = newNode(hash, key, value, null);
    else {  //1.2 结点不为空
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))  //1.2.1 结点已存在，会执行更新value
            e = p;
        else if (p instanceof TreeNode)  //1.2.2 结点是红黑树
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {  //1.2.3 结点是链表
            for (int binCount = 0; ; ++binCount) {
                //1.2.3.1 遍历链表，当结点已存在则更新value，如果遍历到最后一个结点，则创建新结点插入
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        //达到链表长度达到阈值8则转换为红黑树
                        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;
}