HashMap
jdk1.7实现版本
数组+链表
-
引入
数组+链表。很简单，初始化一个数组，解决冲突的办法就是开链法：将hashCode相同的元素放入链表中。
image.png
- 非线程安全
hashmap是非线程安全的，即hashmap的实现中不涉及同步锁的概念。所以多个线程put或一个线程put一个线程get都会引起同步问题。 - resize操作
- 装载因子：hashmap总元素个数/数组长度
- 在put方法中，如果发现新增元素后，hashmap的装载因子过高（默认是0.75），就会自动触发resize操作。
- resize操作的步骤：申请两倍大小的数组，将原数组中的链表一次转移到新的数组中。具体操作是修改对象引用，并不是完全new每个链表的每个结点。
- 上述的转移操作可能会引发死循环问题：多个线程同时put，同时触发resize操作，在转移链表的过程中，引起了引用的回路，造成死循环。可能会把CPU打到100%。
jdk1.8实现版本
数组+链表+红黑树
- 并不解决线程安全问题，而是提升了get方法的效率。
- 当一个链表的个数打到某个阈值（默认8）时，就会使用红黑树来代替链表。显然get效率从之前的O(n)->O(logn)。
ConcurrentHashMap
上面说hashmap并不是线程安全的，ConcurrentHashMap就是用来解决线程安全的。
jdk1.7实现版本
数组+segment+链表
同步：segment+ReentrantLock
-
数据结构
image.png
如图所示，map由1.7中的两级被分为了三级。首先hashmap中存的是segment数组。每个segment数组中存放一个实体数组，每个数组中是一个链表结构。
- 如何解决线程安全问题？
- 每个segment对象继承了ReentrantLock，即对分段进行加锁管理。
- put操作
先获取锁：自旋的retryLock，一段时间后再进行阻塞的lock。
然后再进行写入操作 - get操作
并不加锁。get操作使用的共享变量都被声明为valotile，保证了线程可见性，所以可以直接读取。除了需要链表顺序查找，这个设计还是很棒的。
- 缺点
- size()得到的结果可能不是特别准
jdk7对于ConcurrentHashMap size的内部实现：依次对每个segment进行size操作，然后将每个segment的size相加。整个map连续进行两次这样的操作，如果两次的结果相同则返回。否则锁住整张表。 - 我们发现其实锁的粒度为segment，这个粒度还是有点粗，即修改同一个segment下的两个不同的元素也会被阻塞。如果可以是每个数组元素就很好了。
- size()得到的结果可能不是特别准
jdk1.8实现版本
数组+链表+红黑树
同步：CAS+synchronized
目的就是为了提高了1.7效率。
如何提高？
- 数据结构
和jdk1.8中的hashmap一样，使用红黑树代替链表。
取消了segment三层结构，使用和hashmap一样的两层结构。 - 锁的粒度
上面我们知道1.7中锁的粒度为segment，而在1.8中取消了segment。锁的粒度变成了每个数组的元素（使用synchronized）。这样引发了一个问题，那么跨数组元素的操作怎么办？比如size操作。- 解决办法：将map的size变量设为原子性变量，比如AtomicInteger变量。每次put或remove维护这个变量即可。
- 具体操作
- put操作。先使用CAS进行put，如果失败则使用synchronized加锁。
- get操作。和1.7一样，使用valotile保证效率。
- size操作。每次put或remove维护一个原子变量即可。
网友评论