1 HashMap、HashTable、ConcurrentHashMap
a.线程安全问题
HashMap是线程不安全的，多线程环境下可能会导致死循环（HashMap扩容时），key可以为null；
在jdk1.7中，HashMap底层是通过“数组 + 链表”的实现方式，当put数据出现冲突时，链表使用头部插入的方式；
在jdk1.8中，HashMap底层是通过“数组+链表+红黑树”的方式，当链表节点较少时（<=8），使用链表，当链表节点较多时（>8）转为红黑树（当长度为8时，平均查找长度为8/2=4，而将8个节点转换成红黑树的平均查找长度为log8 =3，这样才有转换的价值），当put数据出现冲突时，使用尾部插入的方式，一定程度上解决扩容时形成链表环的问题。
若链表中元素小于等于6时，红黑树会被还原成链表形式 （避免链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低）。
1） 多线程导致数据不一致：
当多个线程同时向hashMap中put数据时，当出现一个以上的线程put的数据的坐标一致时，可能会导致一个线程的数据修改被覆盖，导致数据不一致。原理如同数据库的事务，数据被覆盖。
2） 多线程导致死循环：
在HasMap扩容时，多线程的扩容会导致在rehash链表的时候，有可能会导致死循环。
HasMap死循环问题.png
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线程需要自旋，到下次循环才有可能机会执行。
扩容问题
HashMap扩容长度都是2的m次幂，主要原因是HashMap根据key计算存储下标时使用的不是取模，而是逻辑“与”，这样计算效率高，而使用与就要求计算（n-1）& HashCode(key)
时（n-1）对应的二进制位都是1，只有2的m次幂才满足。
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节点，此时读线程会参与到扩容中；
如果当前节点有数据，还没有迁移走，当前链表的头结点会被锁住，写或者删除操作会被阻塞，知道扩容完成。
size的计算问题：
jdk1.7
1.首先使用不加锁的方式，进行多次计算，比较前后两次的计算结果，如果相同直接返回，否则尝试再次计算，最多不超过3次；
2.如果超过3次，计算结果仍然不一致，那么对每个segment进行加锁，然后计算size，返回结果。
jdk1.8
通过对 baseCount 和 counterCell 进行 CAS 计算，最终通过 baseCount 和 遍历 CounterCell 数组得出 size
总结如下：
| 序号 | 特征 | jdk1.7 ConcurrentHashMap | jdk1.8 ConcurrentHashMap |
|---|---|---|---|
| 1 | 数据结构 | Segment 方式 | 数组+链表+红黑树的结构 |
| 2 | 线程安全机制 | 采用segment的分段锁机制 | CAS+Synchronized保证线程安全 |
| 3 | 锁的粒度 | Segment加锁 | 每个数组元素加锁（Node） |
| 4 | Hash冲突处理 | 链表 | 链表 + 红黑树（节点数大于8时） |
| 5 | 查询时间复杂度 | 遍历链表O(n) | 遍历红黑树O(logN) |
TreeSet和TreeMap
底层使用红黑树来实现排序
网友评论