在常规的
HasMap或者ArrayList容器中一个线程再遍历中，其他线程插入或者删除会引起迭代器错误异常。ConcurrentHashMap可以支持并发情况下遍历元素 且可以感知到元素更新。
例子
我们看以下例子
import java.util.Enumeration;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.TimeUnit;
public class Main {
public static void main(String[] args) throws InterruptedException {
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("1", "");
map.put("2", "");
map.put("3", "");
map.put("4", "");
new Thread() {
@Override
public void run() {
int i = 0;
while (true) {
i++;
map.put(i+"","");
try {
TimeUnit.MILLISECONDS.sleep(300);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}.start();
Enumeration<String> keys = map.keys();
while (keys.hasMoreElements()) {
TimeUnit.MILLISECONDS.sleep(1000);
System.out.println("" + keys.nextElement());
}
System.out.printf("结束");
}
}
输出：
1
2
3
4
5
17
6
18
7
19
8
9
40
30
41
31
20
42
10
54
32
21
65
43
结束
从结果可知：
- 子线程更新并没有给其他遍历线程带来异常.
- 遍历线程可以感知元素的插入
源码分析
//ConcurrentHashMap.java
public Enumeration<K> keys() {
Node<K,V>[] t;
int f = (t = table) == null ? 0 : t.length;
return new KeyIterator<K,V>(t, f, 0, f, this);
}
KeyIterator相关类
static final class KeyIterator<K,V> extends BaseIterator<K,V>
implements Iterator<K>, Enumeration<K> {
KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
ConcurrentHashMap<K,V> map) {
super(tab, index, size, limit, map);
}
public final K next() {
Node<K,V> p;
if ((p = next) == null)
throw new NoSuchElementException();
K k = p.key;
lastReturned = p;
advance();
return k;
}
public final K nextElement() {
return next(); }
}
static class BaseIterator<K,V> extends Traverser<K,V> {
final ConcurrentHashMap<K,V> map;
Node<K,V> lastReturned;
BaseIterator(Node<K,V>[] tab, int size, int index, int limit,
ConcurrentHashMap<K,V> map) {
super(tab, size, index, limit);
this.map = map;
advance();
}
public final boolean hasNext() {
return next != null; }
public final boolean hasMoreElements() {
return next != null; }
public final void remove() {
Node<K,V> p;
if ((p = lastReturned) == null)
throw new IllegalStateException();
lastReturned = null;
map.replaceNode(p.key, null, null);
}
}
static class Traverser<K,V> {
Node<K,V>[] tab; // current table; updated if resized
Node<K,V> next; // the next entry to use
TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
int index; // index of bin to use next
int baseIndex; // current index of initial table
int baseLimit; // index bound for initial table
final int baseSize; // initial table size
Traverser(Node<K,V>[] tab, int size, int index, int limit) {
this.tab = tab;
this.baseSize = size;
this.baseIndex = this.index = index;
this.baseLimit = limit;
this.next = null;
}
}
在分析调用流程的
时候我们先看下构造函数.
static class Traverser<K,V> {
Node<K,V>[] tab; // current table; updated if resized
Node<K,V> next; // the next entry to use
TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
int index; // index of bin to use next
int baseIndex; // current index of initial table
int baseLimit; // index bound for initial table
final int baseSize; // initial table size
Traverser(Node<K,V>[] tab, int size, int index, int limit) {
//ConcurrentHashMap 哈希表
this.tab = tab;
//表的大小
this.baseSize = size;
//初始化构造时传入0
this.baseIndex = this.index = index;
//表的大小
this.baseLimit = limit;
//下一个节点
this.next = null;
}
}
根据迭代流程我们可以得到如下函数的调用流程:
//BaseIterator.java
//如果next属性不为空那么就存在下一个元素
public final boolean hasMoreElements() {
return next != null; }
//KeyIterator.java
public final K next() {
Node<K,V> p;
//如果next 元素为空那么抛出异常
if ((p = next) == null)
throw new NoSuchElementException();
K k = p.key;
//记录最新的返回的元素
lastReturned = p;
advance();
//返回advance调用之前next元素的拷贝
return k;
}
public final K nextElement() {
return next(); }
上面的代码比较简单 可以看出核心逻辑都在advance中
//Traverser.java
final Node<K,V> advance() {
Node<K,V> e;
//如果next节点所在的哈希桶存在下一个元素就直接返回
//因为这里是volatile修饰的 所以不存在内存可见性
if ((e = next) != null)
e = e.next;
//如果元素不存在下一个哈希桶元素那么也有可能是红黑树
for (;;) {
Node<K,V>[] t; int i, n; // must use locals in checks
//寻找到节点就返回
if (e != null)
return next = e;
//baseIndex表示当前便利哈希表的下表
//baseLimit表示哈希表的长度
//下面的判断用于判断索引是否合法 不合法就返回空即可
if (baseIndex >= baseLimit || (t = tab) == null ||
(n = t.length) <= (i = index) || i < 0)
return next = null;
//n 指向哈希表长度
//i 指向当前便利哈希表索引
//(e = tabAt(t, i)) != null 获取哈希表上的元素
//e.hash < 0 表示当前节点有可能是红黑树或者正在扩容,如果为扩容那么哈希值为-1,且当前节点被ForwardingNode所站位
if ((e = tabAt(t, i)) != null && e.hash < 0) {
//当前正在扩容,那么在当前for里面输出新哈希表的i和 i+旧哈希表长度 的元素(旧哈希表的i位置的会拷贝到新哈希表的i和i+旧哈希表长度处)
if (e instanceof ForwardingNode) {
//ForwardingNode的nextTable 是指向最新的扩容哈希表
//更新哈希表
tab = ((ForwardingNode<K,V>)e).nextTable;
e = null;
//次函数构造一个 TableStack类放入自身的stack属性中.
// TableStack存储旧哈希表信息
//注入传入的t是旧的哈希表
//调用tab变为新的哈希表
pushState(t, i, n);
//用新的哈希表重新循环 输出新哈希表 下标为i的元素
continue;
}
//当前是红黑树
else if (e instanceof TreeBin)
e = ((TreeBin<K,V>)e).first;
else
e = null;
}
//运行到此if 判断证明哈希表上的index位置为空
//stack != null 如果stack不为空,证明当前触发哈希表了扩容
//stack 存储旧哈希表的信息
//stack 不等于空证明新的哈希表index位置不存在元素,
if (stack != null)
//调用后有两种情况:
//(1):
// 档期正在遍历新哈希表的i位置,所以把index 变为 i+旧哈希表数组长度.然后重新循环
//(2):
// 当前正在遍历哈希表的i+旧哈希表长度 位置,那么证明任务完成,继续遍历旧还息表的i+1 位置
recoverState(n);
else if ((index = i + baseSize) >= n)
//更新哈希表索引
index = ++baseIndex; // visit upper slots if present
}
}
//Traverser.java
private void pushState(Node<K,V>[] t, int i, int n) {
//spare用于备份旧的哈希表数据,但是如果一次调用那么spare为null
TableStack<K,V> s = spare; // reuse if possible
if (s != null)
spare = s.next;
else
//如果为空构造一个备份对象,
s = new TableStack<K,V>();
//注意传入的t为旧的哈希表
s.tab = t;
//存储旧的哈希表长度
s.length = n;
//存储当前索引
s.index = i;
//stack 此时为空
s.next = stack;
//存储备份数据到stack属性，主要是复用类减少类的反复创建 降低内存抖动
stack = s;
}
//传入的n为哈希表长度
//recoverState 作用有二：
//（1） 让其 index 变为 i+ 旧哈希表长度。
//（2） 如果 已经变过 （1） ，那么恢复旧的哈希表继续遍历i+1的位置
private void recoverState(int n) {
TableStack<K,V> s;
int len;
// (s = stack) != null 如果备份不为空才进行状态迁移到新哈希表操作
// (index += (len = s.length)) >= n 这里涉及一点逻辑计算:
// n 新哈希表的长度
// len 指向旧表的长度
// index 计算后得到当前位置加上旧哈希表长度. 这里需要读者知道一个前置知识:扩容后的元素会要么放在当前哈希表下表不动,或者放在当前 位置+旧哈希表长度位置
while ((s = stack) != null && (index += (len = s.length)) >= n) {
n = len;
//旧哈希表遍历正在遍历的哈希表下标
index = s.index;
//拷贝旧的哈希表到当前属性
tab = s.tab;
//置空
s.tab = null;
//第一次时 s.next必然为空
TableStack<K,V> next = s.next;
//spare 第一次也为空
s.next = spare; // save for reuse
//第一次由于next为空所以stack 为空
stack = next;
//讲备份旧表对象赋值给spare 注意的是 备份对象的tab属性被置空
spare = s;
//下一次遍历stack 为空结束循环
}
//s为空
//index 当前指向 位置为旧下标+旧哈希表长度
if (s == null && (index += baseSize) >= n)
//索引改为 baseIndex自增后的数值
//baseIndex构造时为0
//那么index当前为1
index = ++baseIndex;
}
总结：
ConcurrentHashMap 迭代时其他线程可以修改元素，而再在迭代的线程可以读取旧哈希表数组范围内的一些新元素，也有可能读取不到。（弱一致性。假设当前正在遍历哈希表位置为i,那么在i之前的哈希桶新元素都不会读取到。）
其大致迭代器扩容处理思想：
如果判断出正在扩容，那么保存当前旧哈希表和相关信息(pushState函数)，而后遍历新哈希表的当前位置和当前位置+旧哈希表长度的元素。最后恢复旧哈希表上下文（recoverState恢复旧哈希表上下文和），继续往下遍历。
转载：https://blog.csdn.net/qfanmingyiq/article/details/109010810
查看评论