hashmap简单记录
- 容量设计
- 扩容
容量设计
hashmap 默认大小是2^4，扩容是成倍的
key进行取模之后，会放到对应的index。
容量是2的n次幂，也是对取模运算的优化。比如容量为8，取模公式是 h % 8，8的2进制是1000，hashmap中的计算，优化为 h & (8-1) 即 h & 7 = h & 0111
就是说取h二进制的后三位。二进制运算速度快，正是容量的考虑才能做这种优化。
扩容
扩容时候，容量为变为两倍。此时会进行位置的移动，原来的key的hashcode，假设是100011110，容量是8 1000
那么原来的index 为 100011110 & 0111 = 110 = 6
扩容后的位置怎么确定，可以直接看100011110后四位 1110，高位为1，那就是移动到6+8的位置 = 14
同样的，假设原来的index 为 100010110 & 0111 = 110 = 6
扩容后看100011110后四位 0110，高位为0，那就保持当前的位置6不变
减少了移动，e.hash & oldCap ，这里是hash & 8 = h & 1000取最高位。if(e.hash & oldCap)==0，放到原始index，if(e.hash & oldCap)==1，放到原始index+oldCap的位置。
jdk1.8中超过了hash冲突导致链表长度>=(8-1)，时候，会把链表转化成红黑树存储，提高了查询效率。
hashMap线程不安全的原因：
https://www.zeroheart.xyz/wordpress/?p=1057
后续文章参考：https://mp.weixin.qq.com/s/AixdbEiXf3KfE724kg2YIw
根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。
hashTable 是安全的，但是都是用synchronized加锁的，所以效率底下，Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。这是因为Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据。
如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。
实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
Dictionary 是 JDK 1.0 添加的，没用过。
初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
所以，当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。
cuncurrentHashMap
1.7里面还是数组加链表，增加了segment的概念
Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
// 记得快速失败（fail—fast）么？
transient int modCount;
// 大小
transient int threshold;
// 负载因子
final float loadFactor;
}HashEntry跟HashMap差不多的，但是不同点是，他使用volatile去修饰了他的数据Value，还有下一个节点next。
原理上来说，ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。
不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。
每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。
get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
1.8里面抛弃了原有的 Segment 分段锁，而采用了CAS + synchronized（优化过的，有锁升级的步骤）来保证并发安全性。
跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）。
ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：
1.根据 key 计算出 hashcode 。
2.判断是否需要进行初始化。
3.即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
4.如果当前位置的hashcode == MOVED == -1,则需要进行扩容。
5.如果都不满足，则利用 synchronized 锁写入数据。
6.如果数量大于TREEIFY_THRESHOLD则要转换为红黑树。
get操作，要看当前的数据结构，采用不同的方式取值
- 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
- 如果是红黑树那就按照树的方式获取值。
- 就不满足那就按照链表的方式遍历获取值。