hashMap

专题一：hashMap

hashMap是基于哈希表的map接口实现的，以key-value形式存储的； jdk1.8以后hashmap底层是数组+链表+红黑树，而jdk1.8之前是数组+链表结构。链表主要是为了解决哈希冲突。（拉链法解决冲突）
为了提升hash冲突时链表过长的查找性能，使用链表时为O（n），使用红黑树时为O(logn）。

对于插入，默认是使用链表结构节点。当同一个索引位置超过阈值（8）后，如果数组此时的长度大于等于64，就会触发链表节点转红黑树节点；如果此时数组长度小于64则不会触发，而是进行扩容。红黑树的结点是链表节点的两倍，节点少时红黑树的查找优势不明显，理想情况下，使用随机的哈希码，hash桶中的频率循序泊松分布，因此，链表中的节点个数为8时红黑树的性能也会展示出来，因此8是个比较合理的数字。
对于移除，当同一个索引位置的结点在移除后达到6个，索引位置的节点为红黑树时就会触发红黑树节点转索引节点。但是如果少于8就马上由红黑树结点转为链表节点，就会出现频繁进行红黑树和链表的转换的情况，造成性能损耗。所以选择在阈值小于6的时候才会触发红黑树转数组。

HashMap是在并发下存在数据覆盖、遍历的同时进行修改，会抛出异常等问题，Hashmap在多线程情况下put的时候，插入元素超过容量就会触发扩容，因为多线程环境下可能其他元素也在进行put操作，若果hash值相同可能出现同一数组下用链表表示造成闭环，导致在get的时候出现死循环。所以hashmap是线程不安全的。

特点：
存储无序；
键和值都可以为null，但是键只能一个为null；
键的位置是唯一的，底层的数据结构控制键；

属性：
size:HashMap已经存储的节点个数。
threshold：扩容阈值，当HashMap的个数达到该值时触发扩容。
loadFactor:负载因子，默认值是0.75，扩容阈值=容量*负载因子。

新建HashMap时threshold会被用来存储初始化时的容量，传入容量计算出大概的最小的2的n次方。Jdk1.8之前构造方法中创建一个长度为16的Entry[] table map。用这个数组存放键值对数据；jdk1.8之后是在第一次调用put方法时创建数组 Node[] table来存放键值对数据。

Hash底层采用的是key的hashCode的值结合数组长度进行无符号右移、按位异或、按位与计算出索引；也可以采用平方取中法、取余数、伪随机数法，这些方法取余效率低，位运算效率高。

为了在table的长度较小时不会有太大的开销，让hashCode的高16位参与运算，如果不加入高位运算，在有一些运算中因为结果只取决于hash值的低三位，无论高位怎么变化结果都是一样的。如果将高位加入运算，索引计算的结果就不会只取决于低位了。
红黑树和链表都是通过e.hash＆oldCap==0来定位在新表中的索引位置的。

当两个对象的hashCode相等会发生碰撞，key值相等就会替换掉不然就连接到链表后面，发生碰撞后jdk1.8之前使用链表解决，1.8之后使用链表+红黑树；通过equals比较内容是否相同，相同则覆盖就得value，不相同则添加新的键值到哈希表中。

Map选择：
Hashtable：理论上不会使用。
Cocurrent HashMap： 线程安全Map，需要保证线程安全时使用。
LinkedHashMap：能记录访问顺序或插入顺序的Map，需要记录访问顺序或插入顺序时使用。
TreeMap：没通过实现Comparator实现自定义顺序，没有指定则会安key的升序排序。
HasMap：最通用的，非线程安全、无序。

JDK1.8的优化：
1）由（数组+链表）改成（数组+链表+红黑树），优化了hash冲突问题。
2）改变计算table初始容量的方式，由（不断左至右移位运算）变成（5个移位+或等于）来计算。
3）扩容是由（头插法）变成（尾插法），避免了并发下的死循环。
4）扩容时计算节点在新表中的位置由（h＆（length-1））改成（hash＆oldCap），设计更加巧妙，更加优雅。