总述
HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。
最重要的就是利用散列桶的空间，最好每一个位置都刚好有一个节点。且几乎不产生链表。那么这样就必须有一个好的计算位置的方法，也就是常说的散列函数（哈希函数）。那么回到刚才的问题，要让每个节点都刚好有节点，那么首先想到的就是对Key计算出的hashcode取桶大小的模，但是取模的消耗是比较大的，所以没有采用这种方法。（主要是因为扩容时，会重新计算Key对应的位置，如果用取模，效率会低到不忍直视）
第二个重要的点就是解决哈希冲突的问题，因为比如像"abc"和"cba"这样的字符串，计算出的hashcode是一样的，那么就会存在在存值时产生哈希冲突。产生哈希冲突影响的就是查找的效率。在JDK1.7之前，有冲突就直接在对应冲突的位置建立链表，但一旦同样的位置冲突多了，那么链表就会很长，那么查找的效率就会非常低，所以在JDK1.8就采用了链表长度大于等于8时，就开始采用红黑树的结构。
散列函数
为了完成刚才我们所说的充分利用桶空间，最好每个位置都存在节点，取模确实是一个好想法，差就差在效率最低。位运算的效率远远高出取模的效率，所以用位运算来代替模运算。
在length = 2的指数次幂的时候，hash%length = h & (length-1)。
加载因子0.75
主要是平衡空间和时间。如果太大，会导致哈希碰撞增大。例如设置为1，那么要填满才会扩容，会大幅增大碰撞概率，比如说剩15的位置为空，这时第十六个元素填充进来，经过取模填上15这个位置的概率是十六分之一，那被碰撞的概率就是十六分之十五，如果前面就是非常完美的分布（即一空一个），这时候就会大概率增加一个链表节点。如果前面不是完美的分布，如果发生碰撞，情况就会更加糟糕。
到8转换为红黑树
这是一个概率学的问题，这个问题具体是属于泊松分布，根据官方的计算，在装填因子为0.75时（别忘了扩容时会重新计算位置更改分布），碰撞产生的链表长度大于8的概率为0.00000006，几乎为一个不可能事件。
1.7形成环的原因
出错原因：多线程情况下，线程一将链表反转后，使得原来的节点2的next不为空了。
然后因为线程二执行同样的代码
第二轮的末尾，也就是e=next那一步，因为原来节点2的next是null，所以完成反转后就停止循环了，但是现在因为线程1将节点反转了，导致节点二的next有值了，所以线程2会死循环下去。
1.8解决方案
4个指针将链表分为分为高位和低位，与原来的HashMap长度做与运算，分成两部分，得到的结果为0的元素就原地不动，得到结果为1的元素就直接原地址+原长度到新的位置（比如原来是 1，原来的长度为16，现在就将高位的部分移动到17的位置）
ConcurrentHashMap
是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。
- Segment是ConcurrentHashMap中的内部类，它就是ConcurrentHashMap中的锁分段对应的存储结构。ConcurrentHashMap与Segment是组合关系，一个ConcurrentHashMap对象包含若干个Segment对象。在代码中表现为ConcurrentHashMap类中存在Segment数组成员。
- Segment类继承于ReentrantLock类，所以Segment本质上是一个可重入的互斥锁。
ConcurrentHashMap采用的是分段锁策略，其主干就是Segment 数组，Segment继承自ReentrantLock类，是一种可重入的互斥锁，一个Segment就是一个子哈希表，Segement里默认维护了一个hashentry数组（hashentry数组中的hashentry的具体数量，是由ConcurrentHashMap中的构造函数中传参initialCapacity和concurrencyLevel相除得到，默认两个都是16，所以默认维护一个hashentry），所以在并发的环境下，只有当访问相同的hashentry数组时，才会上锁，其余的时候就不会有上锁的情况出现。
1.8的改进
上面是1.7的大概思路。1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。那就是查询遍历链表效率太低。1.8抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
并且也采用了数组加链表加红黑树的实现，并且在链表长度大于等于8时，就开始采用红黑树的结构。
CAS详解：https://www.cnblogs.com/barrywxx/p/10700311.html
CAS的ABA问题：加版本号控制
