HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并允许空值和空键。（HashMap与Hashtable大致等效，不同之处在于它是不同步的，并且允许为null。）此类不保证映射的顺序。特别是，它不能保证顺序会随着时间的推移保持恒定。

HashMap内部为数组+链表的结构，会根据key的hashCode值来确定数组的索引(确认放在哪个桶里)。设桶的大小是4，存在一个key的hashCode是7，一个key的hashCode是3，则它们将会被分配到一个桶中(hash冲突)，如果发生hash冲突，HashMap会将同一个桶中的数据以链表的形式存储。在某些条件下发生hash冲突的概率比较高，就会导致同一个桶中的链表长度过长，遍历效率降低，所以在JDK1.8中如果链表长度到达阀值(默认是8)，就会将链表转换成红黑二叉树。

假设哈希函数将元素正确分散在存储桶中，则此实现为基本操作（get和put）提供恒定时间的性能。集合视图上的迭代所需的时间与HashMap实例的“容量” （存储桶数）及其大小（键-值映射数）成正比 。因此，如果迭代性能很重要，则不要将初始容量设置得过高（或负载因子过低），这一点非常重要。

HashMap的实例具有两个影响其性能的参数：初始容量和负载因子。容量是在哈希表中桶的数量，初始容量是简单地在创建哈希表中的时间的能力。负载系数是的哈希表是如何充分允许获得之前它的容量自动增加的措施。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被重新哈希（即，内部数据结构将被重建），因此哈希表的存储桶数约为两倍。

通常，默认负载因子（.75）在时间和空间成本之间提供了很好的权衡。较高的值会减少空间开销，但会增加查找成本（在HashMap类的大多数操作中都得到体现，包括 get和put）。设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以最大程度地减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则将不会进行任何哈希操作。

HashMap数据结构

数组table[]

数组table[]在首次使用时初始化，并根据需要调整大小。分配长度后，长度始终是2的幂（在某些操作中，我们还允许长度为零，以允许使用当前不需要的引导机制）。

Node<K,V>[] table;

Node节点

Node实现了Map.Entry接口，本质上是一个映射(k-v)

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

扩容机制

// loadFactor默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// capacity默认值
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

threshold = loadFactor * length，也就是说数组长度固定以后，如果负载因子越大，所能容纳的元素个数越多，如果超过这个值就会进行扩容(默认是扩容为原来的2倍)。size就是HashMap中键值对的总个数。还有一个字段是modCount，记录是发生内部结构变化的次数，如果put值，但是put的值是覆盖原有的值，这样是不算内部结构变化的。

因为HashMap扩容每次都是扩容为原来的2倍，所以length总是2的次方，这是非常规的设置，常规设置是把桶的大小设置为素数，因为素数发生hash冲突的概率要小于合数，比如HashTable的默认值设置为11，就是桶的大小为素数的应用(HashTable扩容后不能保证是素数)。HashMap采用这种设置是为了在取模和扩容的时候做出优化。

hashMap是通过key的hashCode的高16位和低16位异或后和桶的数量取模得到索引位置，即key.hashcode()^(hashcode>>>16)%length,当length是2^n时，h&（length-1）运算等价于h%length，而&操作比%效率更高。而采用高16位和低16位进行异或，也可以让所有的位数都参与越算，使得在length比较小的时候也可以做到尽量的散列。

在扩容的时候，如果length每次是2^n，那么重新计算出来的索引只有两种情况，一种是 old索引+16，另一种是索引不变，所以就不需要每次都重新计算索引。

Hash索引实现

计算key.hashCode（）并将哈希的较高位扩展（XOR）到较低位。因为该表使用2的幂次掩码，所以仅在当前掩码上方的位发生变化的哈希集将始终发生冲突。（众所周知的示例是在小表中保存连续整数的Float键集。）因此，我们应用了一种变换，将向下传播较高位的影响。在速度，实用性和位扩展质量之间需要权衡。由于许多常见的哈希集已经合理分布（因此无法从扩展中受益），并且由于我们使用树来处理容器中的大量冲突集，因此我们仅以最便宜的方式对一些移位后的位进行XOR，以减少系统损失，以及合并最高位的影响，否则由于表范围的限制，这些位将永远不会在索引计算中使用。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap.put()实现分析

/**
* 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<K,V>[] tab; Node<K,V> p; int n, i;

    // 判断table是否为空或者未初始化，条件成立则调用resize()创建一个新的table，并取得table的长度
    if ((tab = table) == null || (n = tab.length) == 0)  
        n = (tab = resize()).length;
    
    // (n - 1)与hash进行按位与操作得到索引位置，当前节点下没有数据则直接置入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 当前节点下已经存在数据
    else {
        Node<K,V> e; K k;

        //判断put的数据和已经存在的数据是否重复，条件成立则将赋值给变量e
        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) {

                // 将put的数据放在链表的末端
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);

                    //判断链表长度是否大于8，如果大于就转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // 判断put的数据和已经存在的数据是否重复，条件成立则直接覆盖
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

         //如果e不是null，说明没有迭代到最后就跳出了循环，说明链表中有相同的key，
         //因此只需要将value覆盖，并将oldValue返回即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    //说明没有key相同，因此要插入一个key-value，并记录内部结构变化次数
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

小结

1. 根据key计算hash值；
2. 在put的时候判断数组是否存在，如果不存在则调用resize()创建默认大小为16的数组；
3. 确定node节点的位置，根据hash值与数组最大的索引值进行与运算得到索引位置；
4. 判断该位置是否有元素，如果没有元素则直接新建一个Node放到该位置；
5. 如果有元素则判断它们的key是否完全相等，如果相等则将原来的Node赋值给一个变量；
6. 此时再去判断该位置是否是红黑树节点；
7. 如果是红黑树节点，则以红黑树的方式将Node放到红黑树中；
8. 如果是链表，则遍历链表将Node放到最后一位（尾插法）。放完以后需要去判断链表的长度是否超过8,大于8时尝试将链表转换为红黑树（数组长度需要大于64）；
9. 返回旧值。

HashMap.get()实现分析

/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // table非空判断
    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;
}

调优 HashMap

我们有可能手动调优HashMap以提高其在特定应用程序中的性能。为了理解调整HashMap时的性能问题，一些术语是必要的：

• 容量（Capacity）：表中存储的桶数量。
• 初始容量（Initial Capacity）：当表被创建时，桶的初始个数。 HashMap 和 HashSet 有可以让你指定初始容量的构造器。
• 个数（Size）：目前存储在表中的键值对的个数。
• 负载因子（Load factor）：通常表现为 $\frac{size}{capacity}$。当负载因子大小为 0 的时候表示为一个空表。当负载因子大小为 0.5 表示为一个半满表（half-full table），以此类推。轻负载的表几乎没有冲突，因此是插入和查找的最佳选择（但会减慢使用迭代器进行遍历的过程）。 HashMap 和 HashSet 有可以让你指定负载因子的构造器。当表内容量达到了负载因子，集合就会自动扩充为原始容量（桶的数量）的两倍，并且会将原始的对象存储在新的桶集合中（也被称为 rehashing）

HashMap 中负载因子的大小为 0.75（当表内容量大小不足四分之三的时候，不会发生 rehashing 现象）。这看起来是一个非常好的同时考虑到时间和空间消耗的平衡策略。更高的负载因子会减少空间的消耗，但是会增加查询的耗时。重要的是，查询操作是你使用的最频繁的一个操作（包括 get() 和 put() 方法）。

如果你知道存储在 HashMap 中确切的条目个数，直接创建一个足够容量大小的 HashMap，以避免自动发生的 rehashing 操作。

事实证明，质数实际上并不是散列桶的理想容量。近来，（经过广泛的测试）Java的散列函数都使用2的整数次方。对现代的处理器来说，除法与求余数是最慢的操作。使用2的整数次方长度的散列表，可用掩码代替除法。

常见面试题

1. HashMap在扩容的时候为什么都是2的次幂？

• 能利用 & 操作代替 % 操作，提升性能
• 数组扩容时，仅仅关注‘特殊位’就可以重新定位元素
• 减少Hash碰撞

2. HashMap线程安全问题发生在那个阶段？

• 多线程下put Node节点时发生元素丢失
• put非null Node节点后get出来确是null

参考资料

1. 《HashMap JDK1.8实现原理》
2. 《On Java8》