2015年3月9日

时间:2020-12-09 11:48:18

1,概述

java 里面的容器有list,set和map,如果其中线程安全的容器有vector,hashtable,也可以用Collections类里面的synchronizedList(List<T> list),synchronizedSet(Set<T> s)synchronizedMap(Map<K,V> m)来构造线程安全的容器,不过这些方法都是通过添加synchronized方法来实现线程安全的,即同一时间只能有同一个线程访问其方法。严重影响了程序的性能,java.util.concurrent包里面采用了不同的机制提供了一些线程安全的容器,比如说copyOnWriteArrayList,CopyOnWriteArraySet 和CurrentHashMap,ConcurrentSkipListMap,ConcurrentSkipListSet.等等,那么这些容器与synchrozied方法的实现有哪些不同呢?本文将通过对比hashTable和ConcurrentHashMap来讨论一下二者的区别。

2,HashTable和ConcurrentHashMap的对比。

HashTable中用来存储元素的变量:

private transient Entry<K,V>[] table;

Entry对象:

 private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
final K key;
V value;
Entry<K,V> next;

ConcurrentHashMap中用来存储元素的变量:

/**
* The segments, each of which is a specialized hash table.
*/
final Segment<K,V>[] segments;

Segment对象里面的变量:

 /**
* The per-segment table. Elements are accessed via
* entryAt/setEntryAt providing volatile semantics.
*/
transient volatile HashEntry<K,V>[] table;
HashEntry对象:

 static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;

从二者的变量上来看,二者在存储元素的方式上有这很大的不同,hashTable只是采用了一个Entry<> Table来存储元素,而ConcurrentHashMap里面是有一个Segment数组,每一个segement可以看做一个hashTable,这种方式就是“锁分段”或“锁分离”技术,也就是将数据分成几段,把每段分别进行加锁,只要操作的数据不在同一段上,就可以并发的执行,通过这种方式来提高并发性。


HashTable的put方法:

 public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}

modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();

tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}

CurrentHashMap里面的put方法:

 public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}

 final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}

HashTable的get操作:

public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}

CurrentHashMap的get 操作:

public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}

通过以上的对比可以看到,ConcurrentHashMap所采用的“锁分段”的技术,只要修改操作不是发生在同一个segment上面,就可以并发的进行,这样就可以大大的提高并发性。当然这样的副作用是hash的时间比较长,每次定位一个元素需要两次hash过程,第一次找到相应的段,第二次找到元素在段里面的位置。