并发集合 ConcurrentHash

Synchronized Collections

--同步集合 包括Vector 和 Hashtable，以及由 Collections.synchronizedXxx 工厂方法生成的同步包装类。

需要使用synchronized 关键字隐式加锁。iterator不支持并发修改。

 

Concurrent Collections

--并发集合

 

 

ConcurrentHashMap

 

并发HashMap内部的主角是segment数组，默认大小是16--并发级别，即支持16个并发。这是Lock Stripping锁分离理论的实践。

final Segment<K, V>[] segments;

final int segmentMask;
final int segmentShift;

 

构造并发HashMap时，创建segment数组。

while (ssize < concurrencyLevel) {
	++sshift;
	ssize <<= 1;
}
segmentShift = 32 - sshift;
segmentMask = ssize - 1;
this.segments = Segment.newArray(ssize);

 

数据结构: Map-Segment-HashEntry

 

Segement继承了可重入锁，extends ReentrantLock。

它只有一个含有两个参数的构造子：int initialCapacity, float loadFactor。

for (int i = 0; i < this.segments.length; ++i)
			this.segments[i] = new C_Segment<K, V>(cap, loadFactor);

if (initialCapacity > MAXIMUM_CAPACITY)
			initialCapacity = MAXIMUM_CAPACITY;
		int c = initialCapacity / ssize;
		if (c * ssize < initialCapacity)
			++c;
		int cap = 1;
		while (cap < c)
			cap <<= 1;

 

hash代表segment数组的指针。put的第一步是选择合适的segment。

public V putIfAbsent(K key, V value) {
	if (value == null)
		throw new NullPointerException();
	int hash = hash(key.hashCode());
	return segmentFor(hash).put(key, hash, value, true);
}

 

HashEntry是个单项链表中的一个节点，切next为final，不可修改。segment内部的table既是单项链表的数组。

put动作，需要对segment使用可重入锁。由此可以看出，put没有锁整个Map，锁粒度大大降低。

	V put(K key, int hash, V value, boolean onlyIfAbsent) {
		lock();
		try {
			int c = count;
			if (c++ > threshold) // ensure capacity
				rehash();
			HashEntry<K, V>[] tab = table;
			int index = hash & (tab.length - 1);
			HashEntry<K, V> first = tab[index];
			HashEntry<K, V> e = first;
			while (e != null && (e.hash != hash || !key.equals(e.key)))
				e = e.next;

			V oldValue;
			if (e != null) {
				oldValue = e.value;
				if (!onlyIfAbsent)
					e.value = value;
			} else {
				oldValue = null;
				++modCount;
				tab[index] = new HashEntry<K, V>(key, hash, first, value);
				count = c; // write-volatile
			}
			return oldValue;
		} finally {
			unlock();
		}
	}

 

读取数据，基本无需锁。

V get(Object key, int hash) {
	if (count != 0) { // read-volatile
		HashEntry<K, V> e = getFirst(hash);
		while (e != null) {
			if (e.hash == hash && key.equals(e.key)) {
				V v = e.value;
				if (v != null)
					return v;
				return readValueUnderLock(e); // recheck
			}
			e = e.next;
		}
	}
	return null;
}

删除动作需要对segment加锁。因为HashEntry的next是final的，因此，无法修改，只能新建一组单项列表，其中不含那个被删除的倒霉蛋。HashEntry<K, V> newFirst = e.next;

V remove(Object key, int hash, Object value) {
	lock();
	try {
		int c = count - 1;
		HashEntry<K, V>[] tab = table;
		int index = hash & (tab.length - 1);
		HashEntry<K, V> first = tab[index];
		HashEntry<K, V> e = first;
		while (e != null && (e.hash != hash || !key.equals(e.key)))
			e = e.next;

		V oldValue = null;
		if (e != null) {
			V v = e.value;
			if (value == null || value.equals(v)) {
				oldValue = v;
				// All entries following removed node can stay
				// in list, but all preceding ones need to be
				// cloned.
				++modCount;
				HashEntry<K, V> newFirst = e.next;
				for (HashEntry<K, V> p = first; p != e; p = p.next)
					newFirst = new HashEntry<K, V>(p.key, p.hash, newFirst, p.value);
				tab[index] = newFirst;
				count = c; // write-volatile
			}
		}
		return oldValue;
	} finally {
		unlock();
	}
}

 

 

 

ConcurrentSkipListMap,ConcurrentSkipListSet