- Java中的数据结构散列表，结构为数组里面套一个链表（每一个数组元素的内容都为一个链表的头指针）
- 插入时采用头插法，因为HashMap的设计者认为后插入的数据被查询的可能性更大
- HashMap中hash函数的设计，不同于直接取模运算，而是采用位运算的方式，效果同样为取模，但是性能更好
- HashMap的默认长度为16，设置HashMap的长度时一般设置为2的幂次，因为如果设置为10的话有些index会高频亮相，但是有些index却取不到，违反了hash函数要均匀分布的设计初衷
- HashMap为保存键值对的数据结构，每一个键值对也叫做Entry，这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干
- HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点
- 设想中的index计算方法（取模运算）：index = HashCode（Key） % Length
- 实际中的index计算方法（位运算）：index = HashCode（Key） & （Length - 1） （Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。）
- HashMap是一个Entry对象的数组。数组中的每一个Entry元素，又是一个链表的头节点
- HashMap在插入元素过多的时候需要进行Resize，Resize的条件是HashMap.Size >= Capacity * LoadFactor。
- HashMap的Resize包含扩容和ReHash两个步骤，ReHash在并发的情况下可能会形成链表环。
- 扩容与否的衡量标准是主干（即Entry[]）的长度是否达到给定长度的0.75
- HashMap不是线程安全的。在高并发环境下做插入操作，有可能出现下面的环形链表
- 二级哈希表
- 主干为Segment[]，Segment本身就相当于一个HashMap对象，同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点
- 锁分段技术：每一个Segment就相当于一个高度自治的特区，能够高度自主的进行读写操作，Segment和Segment之间互不影响
- ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高
- 都需要二次定位
- hash一次定位到Segment[]当中的具体index对应的Segment，Segment对象中为HashEntry[]
- 再hash一次定位到HashEntry[]中具体的index对应的具体Entry对象
- size方法统计哈希表中的总元素数量是采用了先乐观锁后悲观锁的设计思想
- ConcurrentHashMap的Put方法和Get方法相比，多了两个步骤，获取重用锁和释放锁，具体的Put的方法的逻辑如下：
- 为输入的Key做Hash运算，得到hash值
- 通过hash值，定位到对应的Segment对象
- 获取可重入锁
- 再次通过hash值，定位到Segment当中数组的具体位置
- 插入或覆盖HashEntry对象。
- 释放锁
- size()方法中的大致逻辑如下：
- 遍历所有的Segment
- 把Segment的元素数量累加起来
- 把Segment的修改次数累加起来
- 判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束
- 如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计
- 再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等
- 释放锁，统计结束
注意：对于以上的哈希表，size方法是获取当中的元素个数，也就是键值对对象的个数
