HashMap&CurrentHashMap
2018-08-21 本文已影响1210人
小绵羊你毛不多
java7中的hashMap和currentHashMap
hashMap
数据结构
数组加链表
寻址方式
将key的哈希值对数组长度进行取模，结果作为该Entry在数组中的index
扩容
- 为什么要扩容
- 会存在多个Entry对应一个数组的情况（哈希冲突），当都一个数组后面的链表特别长的时候，进行遍历链表顺序查找效率很低。所以为了提高性能，就会尽量缩小每个链表的长度。
- 扩容时机
- 当map中包含的Entry的数量大于等于 threshold = loadFactor * capacity
- 且 新建的Entry刚好落在一个非空的数组上
- 扩容机制
- 创建一个新表
- 重新生成hash值
- 头插法插入新表中
线程不安全？
- ==resize死循环==
上面知道了扩容机制，扩容时有个transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
// 1
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 2
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
- 假如有两个线程同时执行transfer
-
线程A获取到e=3，e.next=7,暂停了
-
线程B执行完了，即7->3->null，此时的状态
image
-
这时候A执行，获取到7的next是3,造成死循环
image
-
最后的结果
image
- ==fail-fast==
在使用迭代器的过程中如果hashMap被修改，则会抛出ConcurrentModificationException异常，也就是fast-fail策略。
HashIterator() {
// 在iterator的next方法访问下一个Entry事，会做这个检查，如果不相等，说明被修改，抛出异常
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
- fail-safe
fail-safe任何对集合结构的修改都会在一个复制的集合上进行修改，因此不会抛出ConcurrentModificationException
fail-safe机制有两个问题
1需要复制集合，产生大量的无效对象，开销大
2 无法保证读取的数据是目前原始数据结构中的数据
currentHashMap
-
采用分段锁的结构
image
- Segment默认是16，理论上，最多同时支持16个线程并发读写，但是是操作不同的Segment
- 初始化时可以指定Segment数量
- Segment继承自ReentrantLock,每一个Segment都会有一把锁，保证线程安全
不同之处
ConcurrentHashMap与HashMap相比，有以下不同点
- ConcurrentHashMap线程安全，而HashMap非线程安全
- HashMap允许Key和Value为null，而ConcurrentHashMap不允许
- HashMap不允许通过Iterator遍历的同时通过HashMap修改，而ConcurrentHashMap允许该行为，并且该更新对后续的遍历可见
java8中的hashMap和currentHashMap
hashMap
与1.7不同的是，链表的元素超过8个以后，会讲链表转换成红黑树，时间复杂度由o(n)变为o(logN)
currentHashMap
-
结构
- 和hashMap基本一直,数组+链表+红黑树，通过CAS+Synchronized保证线程安全。
-
初始化
-
扩容
-
数据迁移
下面分开说 -
sizeCtl
- 是一个控制标识符，取值不同，含义不同
- -1代表正在初始化
- -N表示有N-1个线程正在进行扩容操作(允许多线程扩容)
- 正数或0代表还没有被初始化
private transient volatile int sizeC；
- 初始化数组
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 上面说过<0代表被其他线程正在初始化
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// CAS 一下，将 sizeCtl 设置为 -1，代表抢到了锁
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
……
break;
}
}
return tab;
}
- 扩容
// 首先要说明的是，方法参数 size 传进来的时候就已经翻了倍了
private final void tryPresize(int size) {
***
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// 这个 if 分支和之前说的初始化数组的代码基本上是一样的，在这里，我们可以不用管这块代码
if (tab == null || (n = tab.length) == 0) {
****
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
// 我没看懂 rs 的真正含义是什么，不过也关系不大
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 2. 用 CAS 将 sizeCtl 加 1，然后执行 transfer 方法
// 此时 nextTab 不为 null
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 1. 将 sizeCtl 设置为 (rs << RESIZE_STAMP_SHIFT) + 2)
// 我是没看懂这个值真正的意义是什么？不过可以计算出来的是，结果是一个比较大的负数
// 调用 transfer 方法，此时 nextTab 参数为 null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
-
数据迁移
允许多线程
原理：
假设数组长度为n，让每个线程负责一个小人物，做完一个再去做另一个，使用了一个stride作为步长（每次迁移的任务长度），然后还需要一个全局的调度者安排哪个线程执行哪一段，这就是transferIndex属性的作用 -
第一个线程会将ransferIndex执行原数组最后的位置，然后从后往前stride个任务属于它- 然后ransferIndex指向新位置，分给第二个线程
什么是红黑树
- 每个节点要么是红要么是黑
- 根节点是黑
- 每个叶节点都是黑（叶节点指树尾端NIL或null节点）
- 如果一个节点是红的，子节点就是黑的
- 对于任意节点，其到叶节点尾端的每条路径都包含相同数目的黑节点。(所以是接近平衡的二叉树)
