程序员之Map

HashMap、HashTable、ConcurrentHashMap

a.线程安全问题
HashMap是线程不安全的，多线程环境下可能会导致死循环（HashMap扩容时），key可以为null；
在jdk1.7中，HashMap底层是通过“数组 + 链表”的实现方式，put使用头插法（多线程情况下扩容时可能会出现链表环）；
在jdk1.8中，HashMap底层是通过“数组+链表+红黑树”的方式，当链表节点较少时（<=8），使用链表，当链表节点较多时（>8）转为红黑树，put使用尾插法。
数据不一致：
当多个线程同时想hashMap中put数据时，当出现一个以上的线程put的数据的坐标一致时，可能会导致一个线程的数据修改被覆盖，导致数据不一致。原理如同数据库的事务，数据被覆盖。
死循环：
在HasMap扩容时，多线程的扩容会导致在rehash链表的时候，有可能会导致死循环。

b.实现原理
HashTable与HashMap实现原理是一样的，但是HashTable的get和put方法都是synchronized操作，不允许key和value为null，因此HashTable的性能是比较差的。
总结：

名称	默认大小	负载因子	存储方式	扩容大小	扩容条件	线程安全	key可否为null
HashMap	16	0.75	数组+链表（红黑树）	原来的2倍	负载数>=负载因子 * 当前大小	否	可以
HashTable	11	0.75	数组+链表（红黑树）	原来的2倍+1	负载数>=负载因子 * 当前大小	是	不可以

c.ConcurrentHashMap
ConcurrentHashMap避免了HashTable对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度。
在jdk1.7中，ConcurrentHashMap采用了“数组 + Segment + 分段锁”的方式实现，其中每个Segment内部是一个Entry数组，数组中的每个元素又是一个链表，ConcurrentHashMap在每个Segment上加锁，这样当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问，实现了粗粒度的分段锁。

ConcurrentHashMap内部结构图.jpg

ConcurrentHashMap访问一个数据时，需要两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在链表的头部。因此这也是Segment方案的查询性能比较慢的原因。
在jdk1.8中，ConcurrentHashMap参考了JDK8 HashMap的实现，采用了“数组+链表+红黑树“”来实现。同时抛弃了Segment转而采用的是Node，每个node保存有key、value和key的Hash值，其中value和next都是用volatile修饰，保证并发可见。
ConcurrentHashMap内部大量采用CAS(compare and swap)操作，CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的，若果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。
put加锁位置
put的过程如下：
1.当存放数据的Node<K,V>[] table数组为null或者length=0的时候初始化table数组；
2.当key的hash值对应的Node<K,V>[] table数组的坐标值为null的时候，使用CAS进行赋值；
3.当Node<K,V>[] table数组正在扩容，那么当前线程参与扩容，使用helpTransfer方法；
4.否则对key的hash值对应的Node<K,V>[] table数组的坐标对象进行synchronized加锁，如果是链表，那么使用尾插法进行插入；如果是红黑树，则插入红黑树；

加锁的位置是在Node<K,V>[] table数组中的节点，即不会加锁到链表的非head节点，也不会加锁的红黑树的非根节点。

扩容问题
jdk1.7的HashMap扩容
jdk1.8的HashMap扩容
jdk1.7的ConcurrentHashMap扩容
jdk1.8的ConcurrentHashMap扩容
ConcurrentHashMap扩容时，按照正常的逻辑所有的读写都要阻塞，但是大牛就是神一样的存在，Doug lea（膜拜一下）对ConcurrentHashMap扩容做了优化，具体思路是：在ConcurrentHashMap扩容时，如果有读写线程进来，那么可以让这些读写线程参与到扩容中，这样加快了扩容，而且读写线程也不需要始终等待。

ConcurrentHashMap引入了ForwardingNode类，当线程发起扩容时，就会更改sizeCtl的值

    /**
     * Table initialization and resizing control.  When negative, the
     * table is being initialized or resized: -1 for initialization,
     * else -(1 + the number of active resizing threads).  Otherwise,
     * when table is null, holds the initial table size to use upon
     * creation, or 0 for default. After initialization, holds the
     * next element count value upon which to resize the table.
     */
    private transient volatile int sizeCtl;

对于扩容时的读操作
如果当前节点有数据，还没有迁移走，则可以直接读，不影响；
如果当前节点已经迁移走，那么都节点会设置成fwd节点，此时读线程会参与到扩容中。

对于扩容时的写或者删除操作
如果当前节点已经迁移走，那么都节点会设置成fwd节点，此时读线程会参与到扩容中；
如果当前节点有数据，还没有迁移走，当前链表的头结点会被锁住，写或者删除操作会被阻塞，直到扩容完成。

总结如下：

序号	特征	jdk1.7 ConcurrentHashMap	jdk1.8 ConcurrentHashMap
1	数据结构	Segment 方式	数组+链表+红黑树的结构
2	线程安全机制	采用segment的分段锁机制	CAS+Synchronized保证线程安全
3	锁的粒度	Segment加锁	每个数组元素加锁（Node）
4	Hash冲突处理	链表	链表 + 红黑树（节点数大于8时）
5	查询时间复杂度	遍历链表O(n)	遍历红黑树O(logN)