摘要：哈希碰撞的概率取决于计算方式和空间容量的大小。超过后执行扩容操作。当一个哈希桶存储的链表长度大于会将链表转换成红黑树，小于时则从红黑树转换成链表。换句话来说，就是为了减少哈希碰撞。红黑树相关的操作虽然代码不同，但是实际上要干的事情是一样的。
前言
学习情况记录
学习情况记录
时间：week 3
SMART子目标 ：Java 容器
记录在学习Java容器 知识点中，关于HashMap的需要重点记录的知识点。
知识点概览：
一、hashCode()
二、HashMap 底层实现
简介
存储结构
重要属性
增加元素操作
Q: HashMap 的长度为什么默认初始长度是16，并且每次resize()的时候，长度必须是2的幂次方？
HashMap 扩容
Q: HashMap 死链问题
Java 8 与 Java 7对比
为什么要使用红黑树？
三、结语
一、hashCode()在Object 类中，hashCode()方法是一个被native修饰的类，JavaDoc中描述的是返回该对象的哈希值。
那么哈希值这个返回值是有什么作用呢？
主要是保证基于散列的集合，如HashSet、HashMap以及HashTable等，在插入元素时保证元素不可重复，同时为了提高元素的插入删除便利效率而设计；主要是为了查找的便捷性而存在。
拿Set进行举例，
众所周知，Set集合是不能重复，如果每次添加数据都拿新元素去和集合内部元素进行逐一地equal()比较，那么插入十万条数据的效率可以说是非常低的。
所以在添加数据的时候就出现了哈希表的应用，哈希算法也称之为散列算法，当添加一个值的时候，先去计算出它的哈希值，根据算出的哈希值将数据插入指定位置。这样的话就避免了一直去使用equal()比较的效率问题。
具体表现在：
如果指定位置为空，则直接添加
如果指定位置不为空，调用equal() 判断两个元素是否相同，如果相同则不存储
上述第二种情况中，如果两个元素不相同，但是hashCode()相同，那就是发生了我们所谓的哈希碰撞。
哈希碰撞的概率取决于hashCode()计算方式和空间容量的大小。
这种情况下，会在相同的位置，创建一个链表，把key值相同的元素存放到链表中。
在HashMap中就是使用拉链法来解决hashCode冲突。
总结hashCode是一个对象的标识，Java中对象的hashCode是一个int类型值。通过hashCode来指定数组的索引可以快速定位到要找的对象在数组中的位置，之后再遍历链表找到对应值，理想情况下时间复杂度为O(1)，并且不同对象可以拥有相同的hashCode。
二、HashMap 底层实现 0. 简介HashMap 基于哈希表的Map接口实现的，是以Key-Value存储形式存在；
非线程安全；
key value都可以为null；
HashMap中的映射不是有序的；
在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层数据结构；
当一个哈希桶存储的链表长度大于8 会将链表转换成红黑树，小于6时则从红黑树转换成链表；
1.8之前和1.8及以后的源码，差别较大
1. 存储结构在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层数据结构。
通过哈希来确认到数组的位置，如果发生哈希碰撞就以链表的形式存储 ，但是这样如果链表过长来的话，HashMap会把这个链表转换成红黑树来存储，阈值为8。
下面是HashMap的结构图：
2. 重要属性 2.1 table /**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node[] table;
在JDK1.8中我们了解到HashMap是由数组加链表加红黑树来组成的结构其中table就是HashMap中的数组。
2.2 size /**
* The number of key-value mappings contained in this map.
*/
transient int size;
HashMap中 键值对存储数量。
2.3 loadFactor /**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
负载因子。负载因子是权衡资源利用率与分配空间的系数。当元素总量 > 数组长度 * 负载因子 时会进行扩容操作。
2.4 threshold /**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
扩容阈值。threshold = 数组长度 * 负载因子。超过后执行扩容操作。
2.5 TREEIFY_THRESHOLD/UNTREEIFY_THRESHOLD /**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
树形化阈值。当一个哈希桶存储的链表长度大于8 会将链表转换成红黑树，小于6时则从红黑树转换成链表。
3. 增加元素 public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
3.1 hash()
可以看到实际执行添加元素的是putVal()操作，在执行putVal()之前，先是对key执行了hash()方法，让我们看下里面做了什么
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key==null说明，HashMap中是支持key为null的情况的。
同样的方法在Hashstable中是直接用key来获取hashCode，没有key==null的判断，所以Hashstable是不支持key为null的。
再回来说这个hash()方法。这个方法用专业术语来称呼就叫做扰动函数。
使用hash()也就是扰动函数，是为了防止一些实现比较差的hashCode()方法。换句话来说，就是为了减少哈希碰撞。
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。我们再看下JDK1.7中是怎么做的。
// code in JDK1.7
static int hash(int h) {
// 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);
}
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
3.2 putVal()再来看真正执行增加元素操作的putVal()方法，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 当数组为空或长度为0，初始化数组容量（resize() 方法是初始化或者扩容用的）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算数组下标 i = (n-1) & hash
// 如果这个位置没有元素，则直接创建Node并存值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 这个位置已有元素
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// hash值、key值相等，用e变量获取到当前位置这个元素的引用，后面用于替换已有的值
e = p;
else if (p instanceof TreeNode)
// 当前是以红黑树方式存储，执行其特有的putVal方法 -- putTreeVal
e = ((TreeNode)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)
// onlyIfAbsent 如果为true - 不覆盖已存在的值
// 把新值赋值进去
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 记录修改次数
++modCount;
// 判断元素数量是否超过阈值 超过则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.3 HashMap 的长度为什么默认初始长度是16，并且每次resize()的时候，长度必须是2的幂次方？
这是一个常见的面试题。这个问题描述的设计，实际上为了服务于从Key映射到数组下标index的Hash算法。
前面提到了，我们为了让HashMap存储高效，应该尽量减少哈希碰撞，也就是说，应该让元素分配得尽可能均匀。
Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。
所以才需要一个映射的算法。这个计算方式就是3.2中有出现的(n - 1) & hash。
我们来进一步演示一下这个算法：
假设有一个key="book"
计算book的hashCode值，结果为十进制的3029737，二进制的101110001110101110 1001。
假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。
通过这种与运算的方式，能够和取模运算一样的效果hashCode % length，在上述例子中就是3029737 % 16=9。
并且通过位运算的方式大大提高了性能。
可能到这里，你还是不知道为什么长度必须是2的幂次方，也是因为这种位运算的方法。
长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。如果HashMap的长度不是2的幂次方，会出现某些index永远不会出现的情况，这个显然不符合均匀分布的原则和期望。所以在源码里面一直都在强调power-of-two expansion和size must be power of two。
另外，HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
4. HashMap 扩容
接下来我们来讲讲HashMap扩容相关的知识。
4.1 扩容HashMap的初始长度是16，假设HashMap中的键值对一直在增加，但是table数组容量一直不变，那么就会发生哈希碰撞，查找的效率肯定会越来越低。所以当键值对数量超过某个阈值的时候，HashMap就会执行扩容操作。
那么扩容的阈值是怎么计算的呢？
阈值 = 数组长度 * 负载因子threshold = capacity * loadFactor
每次扩容后，threshold 加倍
上述计算就出现在resize()方法中。下面会详细解析这个方法。我们先继续往下讲。
loadFactor这个参数，我们之前提到过，负载因子是权衡资源利用率与分配空间的系数。至于为什么是0.75呢？这个实际上就是一个作者认为比较好的权衡，当然你也可以通过构造方法手动设置负载因子 。public HashMap(int initialCapacity, float loadFactor) {...)。
接下去再来到这里的主角resize()方法
