HashMap 原理

就面试总问到 HashMap，蚊子就总说的一知半解，就研究了一下（其实也没有面几家，基本都简历杀了，呜呜呜呜呜~）

~<待完成>~

继承关系

先来看一下 HashMap 的类图，如下图所示， HashMap 继承于 AbstractMap，实现了 Serialzable、Cloneable 和 Map 这三个接口。

底层参数

/**
* 默认初始容量 - 必须是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

/**
* 最大容量，如果具有参数的任一构造函数隐式指定
* 则使用最大容量。 
* 必须是2的幂，且 <= 1 << 30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 负载因子，默认为 0.75f
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 树形化阈值，默认为 8
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 解除树形化阈值，默认为 6
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 最小的树形化容量，默认为 64
*/
static final int MIN_TREEIFY_CAPACITY = 64;

DEFAULT_LOAD_FACTOR：负载因子，默认值为 0.75f，所谓的负载因子就是HashMap的容量达到0.75时的时候会试试扩容resize(), (例：假设有一个 HashMap 的初始容量为 16 ，那么扩容的阀值就是 0.75 * 16 = 12 。也就是说，在你打算存入第 13 个值的时候，HashMap 会先执行扩容)。负载因子也能通过构造方法中指定，如果指定大于1，则数组不会扩容，牺牲了性能不过提升了内存。

TREEIFY_THRESHOLD：树形化阈值，默认为 8，当链表的节点个数大于等于这个值时，会将链表转化为红黑树，该值必须大于等于2 且小于等于8。(为什么默认为 8，是因为红黑树中节点的频率遵循泊松分布，概率为0.5，默认大小调整阈值为0.75，虽然由于调整粒度而具有很大的差异。忽略方差，列表大小k的预期出现是 $exp(-0.5) * \frac{0.5^k}{k!}$。第一个值为：0.60653066，期望还是很大的，但是到了第八个值就为0.00000006，不到千万分之一。所以默认值为8）

UNTREEIFY_THRESHOLD：解除树形化阈值，默认为 6，要小于TREEIFY_THRESHOLD，并且在最多6个与去除时的收缩检测啮合。

MIN_TREEIFY_CAPACITY：最小的树形化容量，默认为 64，至少为 4 * TREEIFY_THRESHOLD，以避免调整数组容量大小和树化阈值之间的冲突。所以在检查链表长度转换成红黑树之前，还会先检测当前数组数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。

数据结构

// Node是单向链表节点，Entry是双向链表节点
static class Node<K,V> implements Map.Entry<K,V> {    
    final int hash;    // 经过hash()方法处理过的hashCode
    final K key;    
    V value;    
    Node<K,V> next;    // 下一个节点
    // 省略...
}

构造方法

/**
 * 使用默认的初始容量（16）和默认负载因子（0.75）构造一个空的 HashMap。
 */
public HashMap() {    
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

/**
 * 使用指定的初始容量和默认负载因子（0.75）构造一个空的 HashMap。
 *
 * @param  initialCapacity ：初始容量
 * @throws 如果初始容量为负，则抛出 IllegalArgumentException 异常。
 */
public HashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 使用指定的初始容量和负载因子构造一个空的 HashMap。
 *
 * @param  initialCapacity ：初始容量
 * @param  loadFactor ：负载因子
 * @throws 如果初始容量为负或负载因子为非正数，则抛出 IllegalArgumentException 异常
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    // NaN：Not a Number。例如给-1开方就会得到NaN。
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    
    // 这个方法可以将任意一个整数转换成2的次方。
    // 例如输入 10，则会返回 16。
    // 另外，有人可能疑惑，不是说 threshold 是 数组容量 * loadFactor得到的吗？
    // 是的，在第一次 put 操作，扩充数组时，会将这个threshold作为数组容量，然后再重新计算这个值。
    this.threshold = tableSizeFor(initialCapacity);
}

方法解析

tableSizeFor 方法

可以看到上面的构造函数中有一个 threshold，在第一次 put 操作时，它表示为数组的初始容量。之后都会根据传入的参数 initialCapacity 重新计算这个 threshold，而计算的方法就是这个 tableSizeFor 方法。

/**
* 将任意一个整数转换成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;
}

hash 方法

HashMap 采用 hash 算法来决定集合中元素的存储位置，每当系统初始化 HashMap 时，会创建一个为 capacity 的数组，这个数组里面可以存储元素的位置被成为 桶(bucket), 每个 bucket 都有其指定索引。可以根据该索引快速访问存储的元素。

/**
* 特殊处理的hashCode（扰动函数处理）
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
    // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
}

在Java中每个对象都会拥有一个hashCode()方法，这个就是散列函数，通过这个方法会返回一个 32 位的整数，使用这么大的值作为哈希值其实是为了尽量避免发生碰撞(相同)，例如两个不同对象的 hashCode 一样的话那就是发生了碰撞。但是如果用这么长的数字来当做索引肯定是不行的，那需要数组有多大才行？所以我们需要把这个 hashCode 缩小到规定数组的长度范围内。

上面的代码只是用hashCode的 高 16 位与低 16 位进行异或运算。hash() 方法就是将 hashCode 进一步的混淆，增加其“随机度”，试图减少插入 HashMap 时的 hash 冲突。

在 putVal 方法中，有一行这样的代码

if ((p = tab[i = (n - 1) & hash]) == null)

i = (n - 1) & hash，n 是数组长度，hash 就是通过 hash() 方法进行 高低位异或运算 得出来的 hash 值。 这个表达式就是 hash 值的取模运算，上面已经说过当除数为 2 的次方时，可以用与运算提高性能。

那么为什么要这样计算，即主要解答以下3个问题：

1. 为什么不直接采用经过hashCode（）处理的哈希码 作为 存储数组table的下标位置？

• 结论：容易出现 哈希码 与 数组大小范围不匹配的情况，即 计算出来的哈希码可能 不在数组大小范围内，从而导致无法匹配存储位置
• 为了解决 “哈希码与数组大小范围不匹配” 的问题，HashMap给出了解决方案：哈希码 与运算（&） （数组长度-1），即问题3

2. 为什么采用 哈希码 与运算(&) （数组长度-1） 计算数组下标？

• 结论：根据 HashMap 的容量大小（数组长度），按需取 哈希码一定数量的低位 作为存储的数组下标位置，从而 解决 “哈希码与数组大小范围不匹配” 的问题。

3. 为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？

• 结论：加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突。

put 方法

整个 put 过程，其实就是：

1.检查数组是否为空，是则执行 resize() 扩充；

2.通过 hash 值计算数组索引，获取该索引位的首节点。

3.如果首节点为null（没发生碰撞），直接添加节点到该索引位(bucket)。

4.如果首节点不为null（发生碰撞），那么有3种情况：

​ ① key和首节点的key相同，覆盖old value（保证key的唯一性）；否则执行②或③

​ ② 如果首节点是红黑树节点（TreeNode），将键值对添加到红黑树。

​ ③ 如果首节点是链表，将键值对添加到链表。添加之后会判断链表长度是否到达 TREEIFY_THRESHOLD - 1 这个阈值，达到则 “尝试” 将链表转换成红黑树。

5.最后判断当前元素个数是否大于 threshold，是则扩充数组。

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
/**
* 实现 put 和相关方法
*
* onlyIfAbsent ：当存入键值对时，如果该key已存在，是否覆盖它的value。false为覆盖，true为不覆盖 参考putIfAbsent()方法。
* evict ：用于子类LinkedHashMap。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;    //  tab：内部数组
    Node<K,V> p;        // p：hash对应的索引位中的首节点
    int n, i;           // n：内部数组的长度    i：hash对应的索引位
    
    // 首次put时，内部数组为空，扩充数组。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算数组索引，获取该索引位置的首节点，如果为null，添加一个新的节点。
    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)))) // 如果首节点的key和要存入的key相同，那么直接覆盖value的值。
            e = p;
        else if (p instanceof TreeNode)  // 如果首节点是红黑树的，将键值对插添加到红黑树
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        // 此时首节点为链表，如果链表中存在该键值对，直接覆盖value。
        // 如果不存在，则在末端插入键值对。然后判断链表是否大于等于7，尝试转换成红黑树。
        // 注意此处使用“尝试”，因为在treeifyBin方法中还会判断当前数组容量是否到达64，
        // 否则会放弃次此转换，优先扩充数组容量。
            
            for (int binCount = 0; ; ++binCount) { // 走到这里，hash碰撞了。检查链表中是否包含key，或将键值对添加到链表末尾。
                
                if ((e = p.next) == null) {  // 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))))  // 检查链表中是否已经包含key
                    break;
                p = e;
            }
        }
        if (e != null) { // 覆盖value的方法。
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // fail-fast机制
    
    if (++size > threshold)  // 如果元素个数大于阈值，扩充数组。
        resize();
    afterNodeInsertion(evict);
    return null;
}

上面的注释有说到，当链表达到 7 的时候，开始 “尝试” 将链表转化为红黑树，是因为红黑树的平均查找长度是 log(n)，长度为 8，查找长度为 log(8) = 3，链表的平均查找长度为 n/2，当长度为 8 时，平均查找长度为 8/2 = 4，这才有转换成树的必要；链表长度如果是小于等于 6，6/2 = 3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

以 6 和 8 来作为平衡点是因为，中间有个差值 7 可以防止链表和树之间频繁的转换。假设，如果设计成链表个数超过8则链表转换成树结构，链表个数小于 8 则树结构转换成链表，如果一个 HashMap 不停的插入、删除元素，链表个数在 8 左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

概括起来就是：链表：如果元素小于8个，查询成本高，新增成本低，红黑树：如果元素大于8个，查询成本低，新增成本高。

resize 方法

对于 resize 的过程，分为几步：

1.根据原本的表，来判断数组是否被初始化，是则根据所调用的构造函数进行初始化。

2.计算新阈值（为旧阈值的两倍），生成新数组，将旧数组的所有元素移到新数组上去。

3.计算索引，这里分为三种情况：

​ ① 如果链表只有一个节点，那么直接重新计算索引存入新数组。

​ ② 如果是红黑树，则进行单独处理。

​ ③ 如果是链表，则根据原来的 hash 值新增的那个 bit 是 1 还是 0 来建立两个链表，是 0 的话就存入原本的链表（索引没变），是 1 的话就存入新建立的链表上面（索引变成“原索引+oldCap”）。

/**
* 初始化或加倍链表大小。如果为null，则分配符合字段阈值中保存的初始容量目标。 
* 否则，因为我们使用的是2次幂扩展，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的偏移量移动。
*/
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; // 新阈值扩大为两倍的旧阈值。
    }
    else if (oldThr > 0)      // 如果数组还没创建，但是已经指定了threshold（这种情况是带参构造创建的对象），threshold 的值为数组长度，初始容量被置于阈值。
        newCap = oldThr;
    else {               // 这种情况是通过无参构造创建的对象，零初始阈值表示使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {  // 由于上面的 newThr = oldThr << 1 时，最高位被移除了，变为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;
    
    // 下面代码是将原来数组的元素转移到新数组中。问题在于，数组长度发生变化。 
    // 那么通过 hash%数组长度 计算的索引也将和原来的不同。
    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)    // 如果该节点是红黑树，执行split方法，和链表类似的处理。
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 维持秩序，此时节点是链表
                    Node<K,V> loHead = null, loTail = null;   // loHead，loTail为原链表的节点，索引不变。
                    Node<K,V> hiHead = null, hiTail = null;   // hiHead, hiTail为新链表节点，原索引 + 原数组长度。
                    Node<K,V> next;
                    
                    // 遍历链表
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {    // 新增bit为0的节点，存入原链表。
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {    // 新增bit为1的节点，存入新链表。
                            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;
}

get 方法

对于 get 方法，分为以下几个步骤：

1.检查数组是否为 null 和 索引位首节点(bucket的第一个节点)是否为 null。

2.如果索引节点的 hash == key 的 hash 或者 key 和索引节点的 k 相同则直接返回(bucket的第一个节点)。

3.如果是红黑色则到红黑树查找。

4.如果有冲突，则通过 key.equals(k) 查找。

5.都没找到就返回null。

public V get(Object key) {
    Node<K,V> e;
    // 在获取节点时也会调用了hash()方法
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;     // tab：内部数组
    Node<K,V> first, e;     // first: 索引位首节点
    int n;    // n: 数组长度
    K k;    // k: 索引位首节点的key
    
    // 数组不为null 数组长度大于0 索引位首节点不为null。
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 如果索引位首节点的hash==key的hash 或者 key和索引位首节点的k相同。
        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 {
                // 发送碰撞 key.equals(k)。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

并发问题

HashMap 在多线程 put 后可能导致 get 无限循环

JDK8 之前，是插入数据的方式是采用的头插法来进行数据的插入，在并发put下可能造成死循环。原因是多线程下单链表的数据结构被破环，指向混乱，造成了链表成环。JDK8 中插入数据的方式是采用的尾插法，避免了这一问题的发生。

多线程 put 的时候可能导致元素丢失

如果两个线程同时读取到当前 node，在链表尾部插入，先插入的线程是无效的，会被后面的线程覆盖掉。

1.7 和 1.8 的区别

引入红黑树

在 jdk 1.8 中，优化了 HashMap 的数据结构：引入了红黑树，即 HashMap 的数据结构 = 数组 + 链表 + 红黑树，而 jdk 1.7 中 HashMap 的数据结构 = 数组 + 链表

引入原因：

提高了 HashMap 的性能，即解决了发生过 哈希碰撞后，链表过长从而导致索引效率慢的问题。

应用场景：

当链表长度 > 8 时，将该链表转换为红黑树，即红黑树作为存储结构 & 解决 Hash 冲突的第 3 方案

（ps：1.无冲突时：存放在数组里；2.冲突 & 链表长度 < 8 时：存放在单链表里；3.冲突 & 链表长度 > 8 时：存放在红黑树里）

hash 方法的实现

对于 jdk 1.8 和 jdk 1.7 两者来说，hash() 方法都使用了扰动函数来计算传入数据的 hashcode，不过它们两者的实现略有不同：

jdk 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算

jdk 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算

// JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
static final int hash(int h) {
    h ^= k.hashCode(); 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
   // 1. 取hashCode值： h = key.hashCode() 
   // 2. 高位参与低位的运算：h ^ (h >>> 16)  
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
    // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
    // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
}

/**
 * 计算存储位置的函数分析：indexFor(hash, table.length)
 * 注：该函数仅存在于JDK 1.7 ，JDK 1.8中实际上无该函数（直接用1条语句判断写出），但原理相同
 * 为了方便讲解，故提前到此讲解
 */
static int indexFor(int h, int length) {  
    return h & (length-1); 
    // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
}

resize 扩容

1.异常情况判断：jdk 1.8 有对扩容异常情况判断，即是否需初始化、当前容量是否 > 最大值；jdk 1.7 则没有

2.重新计算每个数据在新数组中的存储位置：jdk 1.8 是通过新增的bit判断索引位；jdk 1.7 是通过重新计算每个元素的索引，重新存入新的数组，称为rehash操作。

3.转移数据方式：jdk 1.8 是采用尾插法，直接插入链表尾部 / 红黑树，不会出现逆序 & 环形链表死循环问题；jdk 1.7 是采用头插法，先将原位置的数据移到后 1 位，再插入数据到该位置，会出现逆序 & 环形链表死循环问题。