5.1Hashtable、HashMap和ConcurrentHashMap
https://mp.weixin.qq.com/s/AixdbEiXf3KfE724kg2YIw
Hashtable和HashMap区别：
常用：
- 1.Hashtable是线程安全的，HashMap则不是。Hashtable可以在多线程情况下使用。
- 2.Hashtable效率低于Hashmap（因为Hashtable会对数据操作的时候都会上锁）
- 3.Hashtable不允许键或值为null，HashMap允许键或值都可以为null
不常用：
- 1.实现方式不同。
- 2.初始化容量不同，Hashtable为11，HashMap为16，负载因子默认为0.75（当达到当前容量的75%开始扩容）
- 3.扩容机制不同：Hashtable为n2+1（重新用hash值取模），HashMap为2n（因为HashMap使用的是位操作&，所以扩容效率更高）
- 4.迭代器不同。
HashMap和ConcurrentHashMap区别：
JDK7中
ConcurrentHashMap用了Segment数组和HashEntry链表组成散列表。
HashEntry用volatile修饰Value和next（和HashMap的区别）
volatile的特性：
- 1.可见性：不同线程对这个变量进行操作的可见性，即一个线程修改了某个变量的值，新值对其他线程来说是立即可见的
- 2.有序性：禁止进行指令重排序。
- 3.只能保证对单次读/写的原子性，不能保证i++这种操作
ConcurrentHashMap采用分段锁技术，不会像HashTable那样不管是put还是get都需要同步。
ConcurrentHashMap的put和get过程
put
- 1.尝试自旋获取锁
- 2.如果重试次数达到设定的最大值，改为阻塞锁获取
get（非常高效，整个过程不需要加锁）
- 由于用volatile修饰，保证了内存可见性，所以每次都是最新值。
HashMap是数组+链表组成的散列表（JDK8中当链表长度超过8时改为红黑树）
JDK8中
ConcurrentHashMap抛弃原有的Segment分段锁，采用CAS+synchronied保证并发安全
ConcurrentHashMap将HashEntry改成了Node，把值和next采用volatile修饰，保证可见性，和HashMap一样引用了红黑树
ConcurrentHashMap的put操作
- 1.根据key计算出hash值
- 2.根据key定位Node，如果为空则用CAS写入，失败则自旋（不加锁，读取时记录原值，写回时再获取一次，与原值比较，如果一致则写入，如果不一致则重新读取）
- 3.判断是否需要扩容
- 4.如果都不满足，用synchronized锁写入数据
- 5.判断是否转换为红黑树
