HashMap

1. HashMap介绍

1. HashMap是基于Map接口的非同步实现，线程不安全，是为了快速存取而设计的；它采用key-value键值对的形式存放元素（并封装成Node对象），允许使用null键和null值，但只允许存在一个键为null，并且存放在Node[0]的位置，不过允许存在多个value为null的情况。
2. 在JDK7及之前的版本，HashMap的数据结构可以看成"数组+链表"，在JDK8及之后的版本，数据结构可以看成"数组+链表+红黑树"，也就是说HashMap底层采用数组实现，数组的每个位置都存储一个单向链表，当链表的长度超过一定的阈值时，就会转换成红黑树。转换的目的是当链表中元素较多时，也能保证HashMap的存取效率(当链表长度超过阈值(默认为8)并且整个数组长度超过64时，会将链表转化为红黑树)。
3. HashMap有两个影响性能的关键参数："初始容量"和"加载因子":

• 容量capacity：就是哈希表中数组的数量，默认初始容量是16，容量必须是2的N次幂，这是为了提高计算机的执行效率。
• 加载因子loadfactor：在HashMap扩容之前，容量可以达到多满的程度，默认值为0.75
• 扩容阈值threshold=capacity*loadfactor

4. 采用Fail-Fast机制，底层通过一个modCount值记录修改的次数，对HashMap的修改操作都会增加这个值。迭代器在初始过程中会将这个值赋给exceptedModCount，在迭代的过程中，如果发现modCount和exceptedModCount的值不一致，代表有其他线程修改了Map，就立刻抛出异常。

2. put()过程

2.1 重新计算hash值

拿到key的hashcode值之后，调用hash()方法重新计算hash值，从而使hash值的分布尽量均匀。JDK8及之后的版本，对 hash()方法进行了优化，重新计算hash值时，让hashCode的高16位参与异或运算，目的是即使table数组的长度较小，在计算元素存储位置时，也能让高位也参与运算。 (key == null）? 0 : ( h = key.hashcode()) ^ (h >>> 16)

2.2 计算元素存放在数组位置

将重新计算出来的hash值与(tablel.length-1)进行位与&运算，得出元素应该放入数组的哪个位置。为什么HashMap的底层数组长度总是2的n次方幂？因为当length为2的n次方时，h&(length – 1)就相当于对length取模，而且速度比直接取模要快得多，二者等价不等效，这是HashMap在性能上的一个优化。

2.3 将key-value添加到数组中

1. 如果计算出的数组位置上为空，那么直接将这个元素插入放到该位置中。
2. 如果数组该位置上已经存在链表，则使用equals()比较链表上是否存在key相同的节点，如果为true，则替换原元素；如果不存在，则在链表的尾部插入新节点（Jdk1.7及以前的版本使用的头插法）
3. 如果插入元素后，如果链表的节点数是否超过8个，则调用treeifyBin()将链表节点转为红黑树节点。
4. 最后判断HashMap总容量是否超过阈值threshold，则调用resize()方法进行扩容，扩容后数组的长度变成原来的2倍。

解决hash冲突的方式

在 HashMap 中，当发生hash冲突时，解决方式是采用拉链法，也就是将所有哈希值相同的记录都放在同一个链表中，除此之外:

1. 开放地址法（线性探测再散列、二次探测再散列、伪随机探测再散列）：当冲突发生时，在散列表中形成一个探测序列，沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址为止（即该地址单元为空）。如果是插入的情况，在探查到开放的地址，则可将待插入的新结点存入该地址单元，如果是查找的情况，探查到开放的地址则表明表中无待查的关键字，即查找失败。
2. 再哈希法：产生冲突时，使用另外的哈希函数计算出一个新的哈希地址、直到冲突不再发生
3. 建立一个公共溢出区：把冲突的记录都放在另一个存储空间，不放在表里面。

3. HashMap扩容的过程

1. 重新建立一个新的数组，长度为原数组的两倍
2. 遍历旧数组的每个数据，重新计算每个元素在新数组中的存储位置。使用节点的hash值与旧数组长度进行位与运算，如果运算结果为0，表示元素在新数组中的位置不变；否则，则在新数组中的位置下标=原位置+原数组长度。
3. 将旧数组上的每个数据使用尾插法逐个转移到新数组中，并重新设置扩容阈值。

4. HashMap链表转换成红黑树

当数组中某个位置的节点达到8个时，会触发treeifyBin()方法将链表节点（Node）转红黑树节点（TreeNode，间接继承Node），转成红黑树节点后，其实链表的结构还存在，通过next属性维持，红黑树节点在进行操作时都会维护链表的结构，并不是转为红黑树节点后，链表结构就不存在了。当数组中某个位置的节点在移除后达到6个时，并且该索引位置的节点为红黑树节点，会触发untreeify()将红黑树节点转化成链表节点。
HashMap在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion方法）或删除平衡调整（balanceDeletion）方法，调整的方式主要有以下手段：左旋转（rotateLeft方法）、右旋转（rotateRight方法）、改变节点颜色（x.red=false、x.red=true），进行调整的原因是为了维持红黑树的数据结构。

当链表长过长时会转换成红黑树，那能不能使用AVL树替代呢？

AVL树是完全平衡二叉树，要求每个结点的左右子树的高度之差的绝对值最多为1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，虽然会导致红黑树的查询会比AVL稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。

5. HashMap线程不安全的体现

• 在JDK7及以前的版本，表现为在多线程环境下进行扩容，由于采用头插法，位于同一索引位置的节点顺序会反掉，导致可能出现死循环的情况
• 在JDK8及以后的版本，表现为在多线程环境下添加元素，可能会出现数据丢失的情况

如果想使用线程安全的Map容器，可以使用以下几种方式：

1. 使用线程安全的Hashtable，它底层的每个方法都使用了synchronized保证线程同步，所以每次都锁住整张表，在性能方面会相对比较低。
2. 使用Collections.synchronizedMap()方法来获取一个线程安全的集合，底层原理是使用synchronized来保证线程同步。
3. 使用ConcurrentHashMap集合