并发编程陷阱系列(六)高并发环境下使用性能较低的Map

hashtable是线程安全的，但为了保障线程安全，get, put, contains等多个方法都被添加了synchronized，源码片段如下：

   public synchronized V get(Object key) {
	Entry tab[] = table;
	int hash = key.hashCode();
	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;
    }


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 = key.hashCode();
	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;
            index = (hash & 0x7FFFFFFF) % tab.length;
	}

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

 同理，SynchronizedMap也是通过synchronized实现线程安全，代码片段如下：

private static class SynchronizedMap<K,V>
	implements Map<K,V>, Serializable {
	// use serialVersionUID from JDK 1.2.2 for interoperability
	private static final long serialVersionUID = 1978198479659022715L;

	private final Map<K,V> m;     // Backing Map
        final Object      mutex;	// Object on which to synchronize

	SynchronizedMap(Map<K,V> m) {
            if (m==null)
                throw new NullPointerException();
            this.m = m;
            mutex = this;
        }

	SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }

	public int size() {
	    synchronized(mutex) {return m.size();}
        }
	public boolean isEmpty(){
	    synchronized(mutex) {return m.isEmpty();}
        }
	public boolean containsKey(Object key) {
	    synchronized(mutex) {return m.containsKey(key);}
        }
        ...
}

 

首先分析hashmap的数据结构，hashmap实际上就是一个Entry对象的数组

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

 数据结构如下：

 以上两种方式，相当于在整个map范围加了锁，这个锁保证了insert、delete或者get的完整性，这样一个锁不会出现多线程同时访问到的情况。

但是，只要这个锁被占有，就从根本上阻止了其他线程访问 Map，即使处理器有空闲也不能访问，这样大大地限制了并发性。

 

大神Brian Goetz给我们提供了解决此类问题的神器---ConcurrentHashMap，相比于上面的同步类，它具有

多个写入锁，hashtable和SynchronizedMap锁定了整个map(map-wide lock)，而ConcurrentHashMap使用多个锁锁定hash桶中的元素，32 个独立的锁意味着最多可以有 32 个线程可以同时修改 map。