散列表
散列表
概要
散列表也叫哈希表（hash table)，是存储Key-Value映射的集合。对于某一个Key，散列表可以在接近O(1)的时间内进行读写操作。
散列表通过哈希函数实现Key和数组下标的转换，每个键值对都会通过哈希函数计算出一个索引，然后存储在对应的位置上。通过开放寻址法和链表法来解决哈希冲突 。
散列表在本质上也是一个数组，可以根据下标，进行元素的随机访问。
一、Java中的hashMap
HashMap 是 Java 中的一种数据结构，用于存储键值对。它实际上是基于散列表（hash table）实现的。
HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。
HashMap数组每一个元素的初始值都是Null。
1. 写操作（Put）方法的原理
写操作就是在散列表中插入新的键值对（在JDK中叫做Entry）
1) 通过哈希函数来确定Entry的插入位置（index）
2）如果该位置没有元素，就把这个Entry填充进去，但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的key通过哈希函数获得的下标可能是相同的。这种情况就叫做哈希冲突。
解决哈希冲突的方法主要有两种：开放寻址法和链表法。在Java中，针对解决哈希冲突，ThreadLocal所使用的就是开放寻址法，HashMap中采用的链表法。
链表法：HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可，采用头插法（HashMap的发明者认为，后插入的Entry被查找的可能性更大。）
2. 读操作（Get）方法的原理
1) 通过哈希函数，把key转化为对应的index
2) 通过index找到对应的元素，由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。
3. 扩容（Resize）的原理
既然散列表是基于数组实现的，那么散列表也要涉及扩容的问题
当经过多次元素插入，散列表达到一定饱和度时，key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响。
1）影响扩容的两个因素
Capacity：HashMap的当前长度
LoadFactor：HashMap的负载因子，默认值为0.75f
2）衡量HashMap需要进行扩容条件
HashMap.size >= Capacity * LoadFactor
3）扩容步骤
扩容：创建一个新的Entry空数组，长度是原数组的2倍
重新Hash：遍历原Entry数组，把所有的Entry重新Hash到新数组中。
经过扩容，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配
4. HashMap默认的初始长度
1) 初始长度
HashMap的默认初始长度是16，并且每次自动扩展或者手动初始化时，长度必须是2的幂
原因：之所以选择16，是为了服务于从Key映射到index的hash算法。长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
说明：如果长度为其他情况，那么有些index结果的出现几率会更大，而有些index结果永远不会出现。不符合Hash算法均匀分布的原则。
2）哈希函数
从Key映射到HashMap数组的对应位置，会用到一个Hash函数：
index = HashCode（Key） & （Length - 1）
说明：取模运算的方式固然简单，但是效率很低。为了实现高效的Hash算法，HashMap的发明者采用了位运算的方式。
5. 高并发下，为什么HashMap可能会出现死锁
6. Java8中，HashMap的结构有什么样的优化？
JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
说明：链表长度大于8有两种情况
1）table长度足够，hash冲突过多
2）hash没有冲突，但是在计算table下标的时候，由于table长度太小，导致很多hash不一致的key计算的下标一致
第二种情况是可以用扩容的方式来避免的，扩容后链表长度变短，读写效率自然提高。另外，扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。由此可见并不是链表长度超过8就一定会转换成红黑树，而是先尝试扩容。