https://blog.csdn.net/tuke_tuke/article/details/51588156
HashMap实现原理：
代码语言：java复制HashMap是基于哈希算法实现的，我们通过put(key,value)存储，get(key)来获取数据。
当传入key时，HashMap会根据 key.hashCode()计算出key的hash值，根据hash值将value保存在bucket里。
当计算出的hash值相同时，我们称之为hash冲突，HashMap的做法是用"链表和红黑树"存储相同hash值得value。
当hash冲突的个数较少时，就使用链表，否则使用红黑树。
HashMap是由数组 链表组成
对于hash值冲突，会调用equals()来检查它们之间的关系，会有相应有以下两种处理方法：
1. 如果相等，系统就不再存入第二个对象;
2. 如果不等，系统视它们为纯粹的下标冲突，将它们放在同一条链上;什么是哈希（hash）？
代码语言：java复制最简单形式的 hash，是一种在对任何变量/对象的属性应用任何公式/算法后， 为其分配唯一代码的方法。
Java 中所有的对象都有 Hash 方法，Java中的所有对象都继承 Object 类中定义的 hashCode() 函数的默认实现。
此函数通常通过将对象的内部地址转换为整数来生成哈希码，从而为所有不同的对象生成不同的哈希码。为什么链长度为8时，链表转成树；长度为6时，树转成链表？
代码语言：java复制还是不太明白
因为红黑树的平均查找长度是long(n)，长度为8时，平均查找长度为3; log8=long2(3)=3
而链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4。
所以当长度大于等于8的时候，树的查找效率更高。
clipboard.png
clipboard.pngHashMap存取代码：
0、HashMap源码基本属性：
代码语言：java复制static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; "默认初始容量为16 (2^4)"
static final float DEFAULT_LOAD_FACTOR = 0.75f; "默认负载因子为0.75 (12/16=0.75),当元素数量大于12时，则就发生扩容"
transient Node<K,V>[] table; "Hash数组table中存放指向链表的引用，table 它在resize()方法中初始化，并不是在构造方法里面初始化的"
transient int size; "HashMap数组中的元素个数"
int threshold; "容量阈值(元素个数超过该值会自动扩容)，初始时默认为0"
"threshold = 数组长度 * loadFactor(负载因子)，当元素个数超过threshold(容量阈值)时，HashMap 会进行扩容操作"1、Node 静态内部类：存储键值对
代码语言：java复制//table 数组里面存放的是 Node 对象，Node 是 HashMap 的一个内部类
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 记录hash值， 以便重hash时不需要再重新计算
final K key; //Key-value结构的key
V value; //存储值
Node<K,V> next; //指向下一个链表节点
...// 其余的代码
}2、数组下标计算：通过哈希码计算数组下标，在该下标中存储键值对
代码语言：java复制1、通过名为 tableSizeFor() 方法来确保 HashMap 数组长度永远为2的幂次方:
"该算法让最高位的 1 后面的位全变为 1。最后再让结果 n 1，即得到了 2 的整数次幂的值了"
static final int tableSizeFor(int cap) { // table数组长度永远为2的次幂
int n = cap - 1; "// tableSizeFor 的功能（不考虑大于最大容量的情况）是返回大于等于输入参数且最近的 2 的整数次幂的数"
n |= n >>> 1; "// 比如 10，即 2^4 则返回 16"
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}
为什么要保证数组长度为2的次幂？
因为键(key)所计算出的哈希码有可能大于数组容量，老办法是通过简单的求余运算来获得数组下标，但此方法效率太低。
2、HashMap通过以下方法保证哈希值计算后都小于数组容量："与操作"
(n - 1) & hash;
"n 是 2的次幂，为数组容量；(n-1) 类似于一个低位掩码,通过与操作，高位的hash值全部归零，保证低位才有效,从而保证获得的值都小于n"
// 在下一次 resize() 操作时(重新调整大小时)， 重新计算每个 Node 的数组下标将会因此变得很简单。
例：以默认的初始值16为例
01010011 00100101 01010100 00100101
& 00000000 00000000 00000000 00001111
-----------------------------------------
00000000 00000000 00000000 00000101 "高位全部归零，只保留末四位。保证了计算出的值小于数组的长度 n=5 < 16"
3、解决hash碰撞(冲突)严重的问题："扰动函数"
// 因为使用了步骤2功能之后， 由于只取了低位， 因此 hash 碰撞会也会相应的变得很严重。这时候就需要使用 「扰动函数」
"该函数通过将key的哈希码的高 16 位右移后与原哈希码进行异或而得到数组下标"
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
例：以以上例子为例进行异或运算：
01010011 00100101 01010100 00100101 //原哈希码
^ 00000000 00000000 01010011 00100101 //哈希码右移16位
-----------------------------------------
01010011 00100101 00000111 00000000 "此方法保证了高16位不变，低16位根据异或后的结果改变。计算后的数组下标将会从原先的 5 变为 0"
使用了 「扰动函数」 之后，hash 碰撞的概率将会下降。
有人专门做过类似的测试，虽然使用该 「扰动函数」 并没有获得最大概率的避免 hash 碰撞，
但考虑其计算性能和碰撞的概率，JDK 中使用了该方法，且只 hash 一次。3、数组动态扩容：
代码语言：java复制HashMap 每次扩容都是建立一个新的 table 数组，长度和容量阈值都变为原来的两倍，然后把原数组元素重新映射到新数组上，具体步骤如下：
1. 首先会判断 table 数组长度，如果大于 0 说明已被初始化过，那么按当前 table 数组长度的 2 倍进行扩容，阈值也变为原来的 2 倍。
2. 若 table 数组未被初始化过，且 threshold(阈值)大于 0 说明调用了 HashMap(initialCapacity, loadFactor) 构造方法，那么就把数组大小设为 threshold。
3. 若 table 数组未被初始化过，且 threshold 为 0 说明调用 HashMap() 构造方法，那么就把数组大小设为 16，threshold 设为 16*0.75。
4. 接着需要判断如果不是第一次初始化，那么扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去，如果节点是红黑树类型的话则需要进行红黑树的拆分。
1、先判断是初始化还是扩容， 两者在计算 newCap和newThr 时会不一样
2、计算扩容后的容量，临界值。
3、将hashMap的临界值修改为扩容后的临界值
4、根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组。
5、将旧数组的元素复制到table中。在该过程中， 涉及到几种情况， 需要分开进行处理（只存有一个元素， 一般链表， 红黑树）
JDK1.8 HashMap 扩容阶段重新映射元素时不需要像 1.7 版本那样重新去一个个计算元素的 hash 值，
而是通过 hash & oldCap 的值来判断，若为 0 则索引位置不变，不为 0 则新索引=原索引 旧数组长度，为什么呢？具体原因如下：
因为我们使用的是 2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。
因此，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成 "原索引 oldCap(原容量)"
(n - 1) & hash;
A.hashCode: 01010011 00100101 01010100 0010'0101' A.hashCode： 01010011 00100101 01010100 001'00101'
n-1: & 00000000 00000000 00000000 0000'1111' new (n-1) ：& 00000000 00000000 00000000 000'11111' "新容量-1=32-1"
------------------------------------------------------扩容 ==> ------------------------------------------------------
A.hash： 00000000 00000000 00000000 0000'0101' A.new hash： 00000000 00000000 00000000 000'00101'
只需要看倒数第5位即可：因此等价于：
A.hashCode: 01010011 00100101 01010100 001'0'0101
原容量： & 00000000 00000000 00000000 000'1'0000' "原容量16"
------------------------------------------------------
A.new hash: 00000000 00000000 00000000 000'0'0000
"得出结果：通过hash与原容量的与运算，只要倒数第5位等于0，则元素索引还存在，否则：元素索引=原索引 原容量"4、哈希冲突及其处理：
clipboard.png在 Java 的 HashMap 中，采用"数组 链表 红黑树"来解决冲突。
链表树化：指的就是把链表转换成红黑树，树化需要满足以下两个条件：
1、链表长度大于等于 8
2、table 数组长度大于等于 64
为什么 table 数组容量大于等于 64 才树化？
因为当 table 数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。
红黑树拆分：拆分就是指扩容后对元素重新映射时，红黑树可能会被拆分成两条链表。
