在 Java 7 中 HashMap 实现有1000 多行，到了 Java 8 中增长为 2000 多行，虽然代码行数不多，但代码中有比较多的位运算，以及其他的一些细枝末节，导致这部分代码看起来很复杂，理解起来比较困难。但是如果我们跳出来看，HashMap 这个数据结构是非常基础的，我们大脑中首先要有这样一幅图：

整体来看，整个 HashMap 中最重要的点有四个：

初始化
数据寻址-hash方法
数据存储-put方法
扩容-resize方法

只要理解了这四个点的原理和调用时机，也就理解了整个 HashMap 的设计。

一、概要

HashMap 不是线程安全的；
JDK8 的 HashMap 底层实现是数组+链表+红黑树，JDK 7 的 HashMap 底层是数组+链表；
key 不允许重复，如果 put(key) 操作前，HashMap 中 key 已存在，则 put(key) 操作会覆盖此 key 的 value；
HashMap 是 Map 接口使用频率最高的实现类；
HashMap 底层使用内部类 Node 存储 k-v，并且这个内部类 Node 实现了 Map.Entry 接口；
HashMap 是 JDK 1.2 引入的

HashMap 是基于哈希表的实现的 Map 接口。此实现提供了所有可选的 Map 操作，并允许 null key 和 null value 。
HashMap 类除了不是线程安全以外，大致相当于 Hashtable 。
HashMap 不能保证 Map 的顺序，特别是，它不能保证顺序在一段时间内保持不变。
如果对遍历性能有要求，就不要将初始容量设置得太高（或负载因子太低）。

HashMap 有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。负载因子是在容量自动增加之前允许哈希表得到满足的度量。当在散列表中的条目的数量超过了负载因数和容量的乘积，哈希表被重新散列（即，内部数据结构被重建），使得哈希表具有桶的大约两倍。

一般地，默认负载因子（0.75）提供了时间和空间成本之间的良好折中。更高的值会降低空间开销，但会增加查找成本（反映在 HashMap 类的大部分操作中，包括 get 和 put ）。在设置其初始容量时，应考虑 Map 中预期的条目数及其负载因子，以便最小化重新组播操作的数量。如果初始容量大于最大条目数除以负载因子，则不会发生重新排列操作。

二、示例代码

import java.util.HashMap;
public class HashMapTests {
    public static void main(String[] args) {
        HashMap<Object, Object> hashMap = new HashMap<>();
        hashMap.put("abc", "efg");
        hashMap.put(123, "number");
        hashMap.put(456, "number");
        hashMap.put(789, 56);
        hashMap.put(null, "empty");
        // 获取指定 key 映射的 value, 如果 key 不存在, 则返回 null
        // null 返回值不一定表示映射不包含键的映射；映射也可能将键显式映射为空。 containsKey 操作可用于区分这两种情况
        hashMap.get(456);
        // 如果此映射包含指定键的映射，则返回 true。
        hashMap.containsKey(446);
        // 返回此映射中键值映射的数量
        hashMap.size();
        // 从 Map 中删除指定 key 的映射
        hashMap.remove(456);
        // 清空 HashMap
        hashMap.clear();
        // 如果此映射不包含键值映射，则返回 true。
        hashMap.isEmpty();
        // 无论 key 是否存在，都会执行后面方法。若后面方法返回 newValue 为 NULL, 则会从 Map 中 remove(key), 若返回 newValue 不为 NULL, 则 put(key,newValue)
        // 简单一句话：newValue 有值则插入更新，newValue 为 null 就删除该 key
        hashMap.compute(789, (key, value) -> (Integer) value - (Integer) value * 10 / 100);
        // 因为是 Absent, 因此等价于是新增了 key/value 对。
        hashMap.computeIfAbsent(789, key -> 280);
        // 如果指定 key 的映射存在，则返回通过 remappingFunction 重新计算后的值。
        hashMap.computeIfPresent(789, (key, value) -> (Integer) value - (Integer) value * 10 / 100);
        // 若指定 key 的映射不存在，则返回 defaultValue
        hashMap.getOrDefault(56, 0);
        // 若指定 key 的映射不存在, 则向 hashMap 内写入指定映射
        hashMap.putIfAbsent(5, 6);
    }
}

三、源码分析

3.1、类签名

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

3.2、构造器

在 JDK 8 中，在调用 new HashMap() 的时候并没有分配数组堆内存，只是做了一些参数校验，初始化了一些常量。


    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }


    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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);
    }

    /**
     * Returns a power of two size for the given target capacity.
     * 找到大于 cap 的最小的 2 的整数幂
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

3.3、方法一览

3.4、内部类一览

https://www.yuque.com/jaded/fz8wr7/kimncw

3.5、存储结构

HashMap 保存的是 key - value 形式的双列数据，其中，key 具有唯一性，不会重复。

如下图所示，一对 key-value 是放在一个 Node 中的（ Node 是 HashMap 的一个内部类 https://www.yuque.com/jaded/fz8wr7/dgehbd#Ecthe ）。

因为 Node 实现了 Map.Entry 接口，有些书上也说一对 key-value 就是一个 Entry 。
为了方便你阅读，我把 Node 内部类的源码附在下面了：


    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

HashMap 内部有一个成员变量：transient Node[] table，是一个 Node 数组，每一个 Node 就是一个 hash 桶。HashMap 中的所有数据实际上都存储在这个数组中。（PS：由于 TreeNode 也是 Node 的子类，所以 TreeNode 也是可以存入 Table 的）

有一个问题就是，table 数组明明是用于保存 HashMap 所有的数据的，为什么被声明为 transient 的（声明为 transient 类型的变量在对象序列化时不会参与）？

因为 HashMap 在确定一个 key 被存储在 table 的哪个元素中时，是通过 Object.hashCode() 方法获取到对象的哈希值，并将哈希值与桶个数（就是 table 数组的长度）取模来确定的。Object.hashCode() 方法是一个 native 方法，其实现依赖于 JVM 虚拟机的实现。所以在不同平台，同一个对象的哈希值可能是不同的，这就导致了其保存在 table 中的位置可能是不同的，直接将一个 HashMap 传输过去可能会出错。

所以现有的 HashMap 的序列化做法，是将其中的所有 key 都直接保存，在反序列化时再重新生成一个 HashMap，并将 key 逐个插入。

另一个不太重要的原因是，table 数组中的很多成员可能根本就没有被使用，对没有被用到的空间进行序列化会导致结果较大且没有意义，所以序列化时不会保存 table 数组，而是只保存 key。

3.6、hash

hash 函数承担着寻址定址的作用，其性能对整个 HashMap 的性能影响巨大，那什么才是一个好的 hash 函数呢？

计算出来的哈希值足够散列，能够有效减少哈希碰撞
本身能够快速计算得出，因为 HashMap 每次调用 get 和 put 的时候都会调用 hash 方法

下面是 Java 8 的实现：

    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这里比较重要的是 (h = key.hashCode()) ^ (h >>> 16) ，这个位运算其实是将 key.hashCode() 计算出来的 hash 值的高 16 位与低 16 位继续异或，为什么要这么做呢？

我们知道 hash 函数的作用是用来确定 key 在桶数组中的位置的，在 JDK 中为了更好的性能，通常会这样写：

index = (table.length - 1) & key.hash();

回忆前文中的内容，table.length 是一个 2 的正整数次幂，类似于 000100000 ，这样的值减 1 就成了 000011111 ，通过位运算可以高效寻址，这也回答了前文中提到的一个问题，HashMap 内部的bucket 数组长度为什么一直都是 2 的整数次幂？好处之一就是可以通过构造位运算快速寻址定址。

回到本小节的议题，既然计算出来的哈希值都要与 table.length - 1 做与运算，那就意味着计算出来的 hash 值只有低位有效，这样会加大碰撞几率，因此让高 16 位与低 16 位做异或，让低位保留部分高位信息，减少哈希碰撞。

我们再看 Java 7 中对 hash 的实现：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Java 7 中为了避免 hash 值的高位信息丢失，做了更加复杂的异或运算，但是基本出发点都是一样的，都是让哈希值的低位保留部分高位信息，减少哈希碰撞。

3.7、put

在 Java 8 中，put 这个方法的思路分为以下几步：

调用 key 的 hashCode 方法计算哈希值，并据此计算出数组下标 index；
如果发现当前的桶数组为 null，则调用 resize() 方法进行初始化；
如果没有发生哈希碰撞，则直接放到对应的桶中；
如果发生哈希碰撞，且节点已经存在，就替换掉相应的 value；
如果发生哈希碰撞，且桶中存放的是树状结构，则挂载到树上；
如果碰撞后为链表，添加到链表尾，如果链表超度超过 TREEIFY_THRESHOLD 默认是 8 ，则将链表转换为树结构；
数据 put 完成后，如果 HashMap 的总数超过 threshold 就要 resize； ```java /**
- Associates the specified value with the specified key in this map.
- If the map previously contained a mapping for the key, the old
- value is replaced. *
- @param key key with which the specified value is to be associated
- @param value value to be associated with the specified key
- @return the previous value associated with key, or
- null if there was no mapping for key.
- (A null return can also indicate that the map
- previously associated null with key.) */ public V put(K key, V value) { // 调用上文我们已经分析过的 hash 方法, 求 key 的哈希值, 再调用 putVal 方法 return putVal(hash(key), key, value, false, true); }

/**

Implements Map.put and related methods. *
@param hash hash for key
@param key the key
@param value the value to put
@param onlyIfAbsent if true, don’t change existing value
@param evict if false, the table is in creation mode.

@return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

        boolean evict) {

Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0)

 // 第一次 put 时, 会调用 resize 进行桶数组初始化
 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;
 // 此处有一个细节, 在判断 key 是否存在时, hashcode 和 equals 都要比一下, 直接用 equals 不行吗?
 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; } ```

相比之下 Java 7 中的 put 方法就简单不少

public V put(K key, V value) {
    // 如果 key 为 null，调用 putForNullKey 方法进行处理  
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;  
        if (e.hash == hash && ((k = e.key) == key
                || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K, V> e = table[bucketIndex];     // ①  
    table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);    // ②  
}

这里有一个小细节，HashMap 允许 put 时 key 为null 的键值对，但是这样的键值对都放到了桶数组的第 0 个桶中。

3.8、resize

resize 是整个 HashMap中最复杂的一个模块，如果在 put 数据之后超过了 threshold 的值，则需要扩容，扩容意味着桶数组大小变化，我们在前文中分析过，HashMap 寻址是通过 index =(table.length - 1) & key.hash(); 来计算的，现在 table.length 发生了变化，势必会导致部分 key 的位置也发生了变化， HashMap 是如何设计的呢？

这里就涉及到桶数组长度为 2 的正整数幂的第二个优势了：当桶数组长度为2的正整数幂时，如果桶发生扩容（长度翻倍），则桶中的元素大概只有一半需要切换到新的桶中，另一半留在原先的桶中就可以，并且这个概率可以看做是均等的。

通过这个分析可以看到如果在即将扩容的那个位上 key.hash() 的二进制值为0，则扩容后在桶中的地址不变，否则，扩容后的最高位变为了1，新的地址也可以快速计算出来newIndex = oldCap + oldIndex;

下面是 Java 8 的实现：

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) {
        // 如果 oldCap > 0 则对应的是扩容而不是初始化
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没有超过最大值，就扩大为原先的2倍
        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
        // 如果 oldCap 为 0, 但是 oldThr 不为 0, 则代表的是table还未进行过初始化
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 如果到这里 newThr 还未计算，比如初始化时，则根据容量计算出新的阈值
        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;
                    // hiHead 和 hiTail 代表元素在新的桶中和旧的桶中的位置不一致
                    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;
                        // loHead 和 loTail 代表元素在新的桶中和旧的桶中的位置一致
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 新的桶中的位置 = 旧的桶中的位置 + oldCap， 详细分析见前文
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Java 7 中的 resize 方法相对简单许多：

基本的校验之后 new 一个新的桶数组，大小为指定入参
桶内的元素根据新的桶数组长度确定新的位置，放置到新的桶数组中 ```java void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) {
```
 threshold = Integer.MAX_VALUE;
 return;
```
}

Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() &&
```
     (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
```
boolean rehash = oldAltHashing ^ useAltHashing; transfer(newTable, rehash); table = newTable; threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { // 链表跟 table[i] 断裂遍历，头部往后遍历插入到 newTable 中 while (null != e) { Entry 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 name="mEIUT"></a>
# 四、面试题
<a name="wuzv4"></a>
## HashMap 在 put 键值对的时比较键是否相等，为什么 hashcode 和 equals 都要比一下？直接用 equals 不行吗？
不行，因为 HashMa 是使用 key 的 hashcode 来寻址的。hashcode 用于比较两个 key 会不会被分配到同一个 bucket（如果两个 key 不同，但 hashcode 相同，就叫哈希碰撞），equals 才是比较两个 key 是否相同的保障。

对于相同的 key 来说，它们的 hash 值是相同的。但是 hash 值相同，它们的 key 却不一定是相同的。因此，在使用 equals 判断前，先判断 hash 是否相同，如果 hashcode 都不同的话就没必要继续调用 equals 比较了，key 肯定不同。某种意义上，这么做也能获得更高的执行效率。

<a name="Slttc"></a>
## HashMap 如何处理 key 为 null 的键值对？
放置在桶数组中下标为 0 的 bucket 中。

<a name="aHy91"></a>
## HashMap 默认的 bucket 数组是多大？
默认是 16 ，即使指定的大小不是 2 的整数次幂，HashMap 也会找到一个最近的 2 的整数次幂来初始化桶数组。

<a name="MaXkP"></a>
## HashMap 什么时候开辟 bucket 数组占用内存？
在第一次 put 的时候（调用 resize 方法），桶数组的大小都是 2 的正整数幂。

<a name="IQeZv"></a>
## HashMap 内部的 bucket 数组长度为什么一直都是 2 的整数次幂?
这样做有两个好处：

- 第一，可以通过 (table.length - 1) & key.hash() 这样的位运算快速寻址；
- 第二，在 HashMap 扩容的时候可以保证同一个桶中的元素均匀的散列到新的桶中。具体一点就是，同一个桶中的元素在扩容后，一半留在原先的桶中，一半放到了新的桶中。  

<a name="POTuI"></a>
## HashMap 何时扩容？
当 HashMap 中的元素数量超过阈值时触发扩容。阈值的计算方式是：capacity * loadFactor，在 HashMap 中 loadFactor 的默认值是 0.75。

<a name="ZIHHt"></a>
## HashMap 的扩容机制？
数组的初始容量为 16，而容量是以 2 的整数倍次方扩容的，一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模运算（据说性能提高了 5~8 倍）。

数组是否需要扩容是通过负载因子计算出的阈值判断的，如果当前元素个数为总容量的 75% 时，就会扩容数组，这个 0.75 就是默认的负载因子，可以由构造器传入，我们也可以设置大于 1 的负载因子，这样数组就不会扩容，牺牲性能，节省内存。

为了解决碰撞，数组中的元素都是单链表类型，当链表长度大等于 8 时，会将链表转换成红黑树提高性能，而当链表长度小等于 6 时，又会将红黑树转换为单向链表。

检查链表长度转换为红黑树之前，还会先检测当前数组是否达到阈值（64），如果没有达到这个阈值，则会放弃转换，先去扩容数组。

<a name="HeXdB"></a>
## HashMap 的扩容因子为什么是 0.75？
当负载因子为 1.0 时，意味着只有当 HashMap 装满之后才会进行扩容，虽然空间利用率有大的提升，但是这就会导致大量的 hash 冲突，使得查询效率变低。

当负载因子为 0.5 或者更低的时候，hash 冲突降低，查询效率提高，但是由于负载因子太低，导致原来只需要 1M 的空间存储信息，现在用了 2M 的空间。最终结果就是空间利用率太低。

负载因子是 0.75 的时候，这是时间和空间的权衡，空间利用率比较高，而且避免了相当多的 Hash 冲突，使得底层的链表或者是红黑树的高度也比较低，提升了空间效率。

<a name="HNfmM"></a>
## HashMap 扩容后会重新计算 hash 值吗？
在 JDK7 中，HashMap 扩容后，所有的 key 需要重新计算 hash 值，然后再放入到新数组中相应的位置。

在 JDK8 中，HashMap 在扩容时，需要先创建一个新数组，然后再将旧数组中的数据转移到新数组上来。<br />此时，旧数组中的数据就会根据（e.hash & oldCap），数据的hash值与扩容前数组的长度进行与操作，根据结果是否等于 0，分为 2 类。

- 等于 0 时，该节点放在新数组时的位置等于其在旧数组中的位置；
- 不等于 0 时，该节点在新数组中的位置等于其在旧数组中的位置+旧数组的长度。

<a name="fHbDM"></a>
## 为什么 HashMap 在 JDK 7 中扩容时要采用头插法，JDK 8 又改为尾插法？
JDK7 的 HashMap 在实现 resize() 时，新 table[ ] 的列表队头插入。这样做的目的是：避免尾部遍历。

避免尾部遍历是为了避免在新列表插入数据时，遍历到队尾的位置。因为，直接插入的效率更高。

对resize()的设计来说，本来就是要创建一个新的table，列表的顺序不是很重要。但如果要确保插入队尾，还得遍历出链表的队尾位置，然后插入，是一种多余的损耗。直接采用队头插入，会使得链表数据倒序。

JDK8 采用尾插法是避免在多线程环境下扩容时采用头插法出现死循环的问题。

<a name="rbvk9"></a>
## HashMap 是如何解决哈希冲突的？
拉链法（链地址法）<br />为了解决碰撞，数组中的元素是单向链表类型。当链表长度大于等于8时，会将链表转换成红黑树提高性能。<br />而当链表长度小于等于6时，又会将红黑树转换回单向链表提高性能。

<a name="zg2C4"></a>
## bucket 中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？
当一个 bucket 中的元素数量大等于 8 的时候，bucket 中的链表将会转换为红黑树（树化）。反之，当桶中的元素数量小等于 6 的时候又会转为链表。这样做的原因是避免红黑树和链表之间频繁转换，引起性能损耗。

<a name="fkcu7"></a>
## Java 8 中为什么要引进红黑树，是为了解决什么场景的问题？
引入红黑树是为了避免 hash 性能急剧下降，引起 HashMap 的读写性能急剧下降的场景。正常情况下，一般是不会用到红黑树的，在一些极端场景下，假如客户端实现了一个性能拙劣的 hashCode 方法，可以保证 HashMap 的读写复杂度不会低于 O(lgN) 
```java
public int hashCode() {
    return 1;
}

HashMap 为什么使用红黑树而不是 B/B+ 树或平衡二叉树 AVL 或二叉查找树？

1）不使用二叉查找树

二叉排序树在极端情况下会出现线性结构。例如：二叉排序树左子树所有节点的值均小于根节点，如果我们添加的元素都比根节点小，会导致左子树线性增长，这样就失去了用树型结构替换链表的初衷，导致查询时间增长。所以这是不用二叉查找树的原因。

2）不使用平衡二叉树

平衡二叉树是严格的平衡树，红黑树是不严格平衡的树，平衡二叉树在插入或删除后维持平衡的开销要大于红黑树。
红黑树的虽然查询性能略低于平衡二叉树，但在插入和删除上性能要优于平衡二叉树。
选择红黑树是从功能、性能和开销上综合选择的结果。

3）不使用 B 树 / B+ 树

HashMap 本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。
如果用 B/B+ 树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面，这个时候遍历效率就退化成了链表。

比如我们设置的 Max.Degree=7，如果有 6 条数据，这个时候遍历效率就退化成链表了

你可以使用这个页面在线模拟操作 B+ 树 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

HashMap 和 Hashtable 的有什么区别？

1）线程安全问题

HashMap 是非线程安全的，Hashtable 是线程安全的。Hashtable 内部的方法基本都经过 synchronized 修饰。

2）执行效率

因为 HashMap 是非线程安全的，所以 HashMap 要比 Hashtable 效率⾼⼀点。

3）存储要求

HashMap 允许键和值是 null，而 Hashtable 不允许键或值是null。
HashMap中，null 可以作为键，这样的键只有⼀个，可以有⼀个或多个键所对应的值为 null。
HashTable 中 put 进的键值只要有⼀个 null，直接抛出 NullPointerException。

4）初始容量与扩容后容量

Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。
HashMap默认的初始大小为16，之后每次扩充，容量变为原来的2倍。

创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次⽅大小。

5）底层数据结构

JDK1.8 以后的 HashMap 在解决哈希冲突时当链表长度大于等于 8 时，将链表转化为红黑树，以减少搜索时间。
Hashtable 没有这样的机制。Hashtable 的底层是以数组+链表的形式来存储。

6）类签名

HashMap 的父类是 AbstractMap，Hashtable 的父类是 Dictionary。
相同点：都实现了 Map 接口，都存储 k-v 键值对。

HashMap 和 HashSet 有什么区别？

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet ⾃⼰不得不实现之外，其他方法都是直接调⽤ HashMap 中的方法）

HashMap 实现了 Map 接口，HashSet 实现了 Set 接口
HashMap 存储键值对，HashSet 存储对象
HashMap 调用 put() 向 map 中添加元素，HashSet 调用 add() 方法向 Set 中添加元素
HashMap 使用键 key 计算 hashCode 的值，HashSet 使用对象来计算 hashCode 的值，在 hashCode 相等的情况下，使用 equals() 方法来判断对象的相等性
HashSet 中的元素由 HashMap 的key 来保存，而 HashMap 的 value 则保存了一个静态的 Object 对象作为占位使用

HashMap 有哪几种遍历方式？

keySet

Map.Entry

Iterator

…

REF

https://www.nowcoder.com/discuss/203901
https://www.nowcoder.com/discuss/631983
https://www.nowcoder.com/discuss/597290
https://www.nowcoder.com/discuss/841130
https://www.nowcoder.com/discuss/820700
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html