背景

map是所有编程语言都通用并且常用的数据结构，而HashMap更是java中使用的最广泛的map

写这篇博客的初衷：① 学到优秀设计 ② 用好HashMap ③ 跟面试官/同事吹水

Problem before Read：

1. HashMap中有哪些优秀的设计？
2. HashMap是如何扩容的？
3. HashMap1.7和1.8有什么区别？
4. HashMap和ArrayList区别？

场景驱动看源码：

1. HashMap创建（构造函数）
2. HashMap读写
3. HashMap扩容

一、HashMap创建

HashMap提供了4个构造方法

// 1. 设置默认阈值（为啥不像第2个构造方法调用第3个？因为其无输入值，无需要做校验以及调整输入的初始值）
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 2. 调用第3个构造方法来做校验并且调整初始值为最小2次幂（方便通过位运算来定位目标元素）
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 3. 校验入参及调整初始值为最小2次幂
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

// 4. 通过传入的map进行初始化
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

// ① 如果当前map还未初始化，则将入参map的大小除以阈值，这样该新创建的map的元素刚好处于阈值的边缘避免空间浪费
// ② 如果当前map已经初始化则判断入参map的大小是否超过当前map的阈值，如超过则先进行扩容
// ③ evict在初次初始化map时为false，否则为true
// ④ 循环赋值
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

通过分析可得，前三个构造函数仅设置map大小以及阈值，仅有第四个构造函数会进行初始化

二、HashMap读写

相比写操作，读操作非常简单。因此咱们先看看读操作
读操作

//1. 逻辑比较简单，就是调用getNode方法
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

// 1. 如果数组目标下标有元素并且第一个元素的key为需要查找的，则直接返回
// 2. 如果发现数组目标下标的元素有后续节点。为树节点则遍历树检索数据；为链表则通过遍历链表来检查即可
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

写操作

// 1. 操作也很简单，就是调用putVal
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 1. 如果table数组为初始化，则此时才进行初始化
// 2. 如果计算出数组目标下标上无元素，则直接将写的内容封装成Node写上去
// 3. 如果目标下标已经有元素。若该元素为TreeNode，则以写树的操作往红黑树追加元素；
     是链表则遍历链表，若是链表中不存在该值则再尾节点追加，若是链表中存在该值则根据onlyIfAbsent 来决定是否更新value值
// 4. 在链表中添加完节点后会判断链表的节点是否达到8个，到达则进行树化（先追加元素再进行树化）
      树化的前提会判断table数组是否已达到64，否则扩容数组，不树化
// 5. 判断是否到达阈值，若到达也进行table数组扩容
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;
}

HashMap扩容

HashMap的扩容是比较核心的设计，设计得不好很容易影响性能

// 方法相对复杂，一点点来啃
// 1. 如果扩容前table的大小处于合理值，则左移进行双倍扩容
// 2. 循环进行数据迁移
      ① 旧table 下标只有一个元素则直接赋值给新table
      ② 下标为TreeNode节点(红黑树)则进行树迁移
      ③ 下标为Node(链表) 则进行链表迁移
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

问题

一、HashMap中有哪些优秀的设计

1. 延迟初始化内部数组
   有可能创建完Map但不立即使用，如果初始化太早了会造成内存资源浪费
2. 将HashMap内部数组的大小控制为2的幂
   当数组大小为2的幂时，通过&运算的值与取余的效果是一样的且性能更高
   因此数组大小控制为2的幂可以提高HashMap定位元素的速度
3. 阈值默认为0.75
   阈值0.75是时间和空间的一个折中选择，值小了空间利用率低，值大了查询性能低
   由于链表的树化长度为8(因为长度为8之前链表性能优于红黑树)，通过配合泊松分布推导出当阈值为0.75时发生树化的概率为千万分之一
4. 高性能的哈希算法
   通过高低位进行异或运算来保留每个key的独有特征，从而实现哈希算法

二、HashMap是如何扩容的
参考前面

三、HashMap1.7和1.8有什么区别

1. 1.8引进红黑树，对性能进行优化
2. 1.8往链表插入数据时采用尾插入法代替1.7的头插入法，头插入法在并发场景下会出现环

四、HashMap和ArrayList区别

1. HashMap底层采用Entry数组来保存数据
   ArrayList底层采用Object数组来保存数据
2. HashMap是2倍扩容，ArrayList是1.5倍扩容（相比HashMap，ArrayList扩容成本低，因此可不进行过多的扩容）
3. HashMap查询数据时，先对key进行哈希运算然后对table数组取余得到目标下标；而ArrayList是直接通过传入目标下标