重温数据结构：哈希 哈希函数 哈希表 equals和hasCode方法 我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过哈希计算，可以大大减少比较次数
HashMap是采用了哈希表实现的键值对集合，HashMap 的特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率贼高。
哈希表的底层是数组+链表实现的，数组是哈希表，链表用来解决哈希冲突，同一hash值的节点都存储在一个链表里，也就是所谓的拉链法
如果在一个链表中查找其中一个节点时，将会花费O（n）的查找时间，会有很大的性能损失；也就是说，当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8），并且数组的长度大于64时，将链表转换为红黑树，这样大大减少了查找时间
HashMap的几个难点
jdk在线手册
⚠️ ⚠️ 我们希望控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少
如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞如果哈希桶数组很大，虽然较差的Hash算法也会比较分散，但是浪费了空间所以我们要使用好的Hash算法和扩容机制（这些接下来再说具体实现）
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，也是存在transient Node<K,V>[] table中的一个链表节点
//实现了 Map.Entry 接口 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 相等的条件：键相等、值相等、个数相等、顺序相等 Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }其中调用了 tableSizeFor(int) 来根据指定的容量设置阈值
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; }第四种构造方法调用了 putMapEntries()，这个方法用于向哈希表中添加整个集合：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { //数组还是空，初始化参数 if (table == null) { 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(); //先经过 hash() 计算位置，然后复制指定 map 的内容 putVal(hash(key), key, value, false, evict); } } }把键值对添加到HashMap中的的大致思路是
1. 先调用 hash() 方法计算哈希值
hash(key)其中哈希值的计算是传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }2. 然后调用 putVal() 方法中根据哈希值进行相关操作
return putVal(hash(key), key, value, false, true);3. 如果当前 哈希表内容为空，新建一个哈希表
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果当前 哈希表内容为空，新建 //n 指向最后一个桶的位置，tab 为哈希表另一个引用 //resize() 后续介绍 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;4. 如果要插入的桶中没有元素，新建个节点并放进去
//如果要插入的位置没有元素，新建个节点并放进去 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);5. 否则从桶中第一个元素开始查找哈希值对应位置（找对应的键值对）
6. 如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找
7. 如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal() 进行插入
8. 否则还是从传统的链表数组中查找、替换，结束查找
上面步骤实际上就是先去找有没有和要加入的键相同的节点，有就要替换掉原先的值，因为一个键只能对应一个值，没有就在链表后面加入新的键值对
else { //如果要插入的桶已经有元素，替换 // e 指向被替换的元素 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //p 指向要插入的桶第一个 元素的位置，如果 p 的哈希值、键、值和要添加的一样，就停止找，e 指向 p e = p; else if (p instanceof TreeNode) //如果不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal 插入 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); //当这个桶内链表个数大于等于 8，就要树形化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果找到要替换的节点，就停止，此时 e 已经指向要被替换的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //存在要替换的节点 if (e != null) { V oldValue = e.value; //替换，返回 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果超出阈值，就得扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;9. 当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化
10. 最后检查是否需要扩容，如果扩容的话会重新计算hash值进行映射
注意这里当新来的Entry映射到冲突的数组位置时，插入到对应的链表使用的是头插法，把新节点插入到头部，这是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大
HashMap 中通过将传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }为什么要这样计算
按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不对hash进行处理，元素的 hashCode() 在很多时候下低位是相同的，相当于散列生效的只有几个低 bit 位，这将导致冲突（碰撞），为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能
由于 int 只有 32 位，无符号右移 16 位相当于把高位的一半移到低位：
所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。
每次添加时会比较当前元素个数和阈值：
//如果超出阈值，就得扩容 if (++size > threshold) resize();扩容： HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去
① 计算新桶数组的容量 newCap 和新阈值 newThr
② 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
③ 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。这是1.8以后的，我们现在为了简单先分析1.7的代码
void resize(int newCapacity) { //传入新的容量 Entry[] oldTable = table; //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了 return; } Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组 transfer(newTable); //！！将数据转移到新的Entry数组里 table = newTable; //HashMap的table属性引用新的Entry数组 threshold = (int)(newCapacity * loadFactor);//修改阈值 } void transfer(Entry[] newTable) { Entry[] src = table; //src引用了旧的Entry数组 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素 if (e != null) { src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象） do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置 e.next = newTable[i]; //标记[1] newTable[i] = e; //将元素放在数组上 e = next; //访问下一个Entry链上的元素 } while (e != null); } } }newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上 上面是JDK1.7的做法，对于JK1.8做了些优化 //TODO
线程安全问题 在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。在jdk1.7中使用的是头插法，所以多线程使用HashMap可能造成死循环
有如下代码
public class HashMapInfiniteLoop { private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f); public static void main(String[] args) { map.put(5， "C"); new Thread("Thread1") { public void run() { map.put(7, "B"); System.out.println(map); }; }.start(); new Thread("Thread2") { public void run() { map.put(3, "A); System.out.println(map); }; }.start(); } }map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize
假设现在线程1进行到了Entry next = e.next;后被挂起，线程2完成resize，这时Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3) e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了 使用头插会改变链表的上的顺序，但是jdk1.8使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证
这其中有一步
// index = (n - 1) & hash first = tab[(n - 1) & hash]是用来计算出桶在桶数组中的位置
这里通过(n - 1)& hash即可算出桶的在桶数组中的位置，可能有的朋友不太明白这里为什么这么做，这里简单解释一下。HashMap 中桶数组的大小 length 总是2的幂，此时，(n - 1) & hash 等价于对 length取余。但取余的计算效率没有位运算高，所以(n - 1) & hash也是一个小的优化。举个例子说明一下吧，假设 hash = 185，n =16。计算过程示意图如下：
这也就解释了为什么要用单独的hash()函数重新计算hash值吗，而不直接使用键的hash值
/** * 计算键的 hash 值 */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }我们再看一下上面求余的计算图，图中的 hash 是由键的 hashCode 产生。计算余数时，由于 n 比较小，hash 只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的 hash 高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：
JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
HashMap在JDK1.8新增了红黑树的数据结构来优化这个问题 Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表 为什么选用8这个数字呢
根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表
HashMap 中关于红黑树的三个关键参数
//一个桶的树化阈值 //当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点 //这个值必须为 8，要不然频繁转换效率也不高 static final int TREEIFY_THRESHOLD = 8; //一个树的链表还原阈值 //当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构 //这个值应该比上面那个小，至少为 6，避免频繁转换 static final int UNTREEIFY_THRESHOLD = 6; //哈希表的最小树形化容量 //当哈希表中的容量大于这个值时，表中的桶才能进行树形化 //否则桶内元素太多时会扩容，而不是树形化 //为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD static final int MIN_TREEIFY_CAPACITY = 64;链表树化 在扩容的过程中，当 ① 链表长度大于等于 TREEIFY_THRESHOLD ② 桶数组容量大于等于 MIN_TREEIFY_CAPACITY 时把链表转化为红黑树，之所以选择红黑树是为了解决二叉查找树的缺陷：二叉查找树在特殊情况下会变成一条线性结构
要满足第二个条件的原因是： 当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。
具体操作如下
根据哈希表中元素个数确定是扩容还是树形化
如果是树形化 ① 遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系 ② 然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容
static final int TREEIFY_THRESHOLD = 8; /** * 当桶数组容量小于该值时，优先进行扩容，而不是树化 */ static final int MIN_TREEIFY_CAPACITY = 64; static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } } /** * 将普通节点链表转换成树形节点链表 */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // hd 为头节点（head），tl 为尾节点（tail） TreeNode<K,V> hd = null, tl = null; do { // 将普通节点替换成树形节点 TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); // 将普通链表转成由树形节点链表 if ((tab[index] = hd) != null) // 将树形链表转换成红黑树 hd.treeify(tab); } } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }到这一步得到的仅仅是一个二叉树，还要调用树形节点 hd.treeify(tab) 方法进行塑造红黑树
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (root == null) { //头回进入循环，确定头结点，为黑色 x.parent = null; x.red = false; root = x; } else { //后面进入循环走的逻辑，x 指向树中的某个节点 K k = x.key; int h = x.hash; Class<?> kc = null; //又一个循环，从根节点开始，遍历所有节点跟当前节点 x 比较，调整位置，有点像冒泡排序 for (TreeNode<K,V> p = root;;) { int dir, ph; //这个 dir K pk = p.key; if ((ph = p.hash) > h) //当比较节点的哈希值比 x 大时， dir 为 -1 dir = -1; else if (ph < h) //哈希值比 x 小时 dir 为 1 dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) // 如果比较节点的哈希值、 x dir = tieBreakOrder(k, pk); //把 当前节点变成 x 的父亲 //如果当前比较节点的哈希值比 x 大，x 就是左孩子，否则 x 是右孩子 TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }