小心LinkedHashMap的get()方法 - JAVA

这是一个来自实际项目的例子，在这个案例中，有同事基于jdk中的LinkedHashMap设计了一个LRUCache，为了提高性能，使用了 ReentrantReadWriteLock 读写锁：写锁对应put()方法，而读锁对应get()方法，期望通过读写锁来实现并发get()。
代码实现如下：www.2cto.com
private ReentrantReadWriteLock lock = new ReentrantReadWriteLock ();
lruMap = new LinkedHashMap(initialCapacity, loadFactor, true)

public V get(K key) {
lock.readLock().lock();
try {
return lruMap.get(key);
} finally {
lock.readLock().unlock();
}
}

public int entries() {
lock.readLock().lock();
try {
return lruMap.size();
} finally {
lock.readLock().unlock();
}
}

public void put(K key, V value) {
...
lock.writeLock().lock();
try {
...
lruMap.put(key, value);
...
} finally {
lock.writeLock().unlock();
}
}
在测试中发现问题，跑了几个小时系统就会hung up，无法接收http请求。在将把线程栈打印出来检查后，发现很多http的线程都在等读锁。有一个 runnable的线程hold了写锁，但一直停在LinkedHashMap.transfer方法里。线程栈信息如下:
"http-0.0.0.0-8081-178" daemon prio=3 tid=0x0000000004673000 nid=0x135 waiting on condition [0xfffffd7f5759c000]
java.lang.Thread.State: WAITING (parking)
at sun.misc.Unsafe.park(Native Method)
- parking to wait for <0xfffffd7f7cc86928> (a java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync)
at java.util.concurrent.locks.LockSupport.park(LockSupport.java:156)
at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:811)
at java.util.concurrent.locks.AbstractQueuedSynchronizer.doAcquireShared(AbstractQueuedSynchronizer.java:941)
at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireShared(AbstractQueuedSynchronizer.java:1261)
at java.util.concurrent.locks.ReentrantReadWriteLock$ReadLock.lock(ReentrantReadWriteLock.java:594)
......
"http-0.0.0.0-8081-210" daemon prio=3 tid=0x0000000001422800 nid=0x155 runnable [0xfffffd7f5557c000]
java.lang.Thread.State: RUNNABLE
at java.util.LinkedHashMap.transfer(LinkedHashMap.java:234)
at java.util.HashMap.resize(HashMap.java:463)
at java.util.LinkedHashMap.addEntry(LinkedHashMap.java:414)
at java.util.HashMap.put(HashMap.java:385)
......
大家都知道HashMap不是线程安全的，因此如果HashMap在多线程并发下，需要加互斥锁，如果put()不加锁，就很容易破坏内部链表，造成get()死循环，一直hung住。这里有一个来自淘宝的例子，有对此现象的详细分析：https://gist.github.com/1081908
但是在MSDP的这个例子中，由于ReentrantReadWriteLock 读写锁的存在，put()和get()方法是互斥，不会有上述读写竞争的问题。
Google后发现这是个普遍存在的问题，其根结在于LinkedHashMap的get()方法会改变数据链表。我们来看一下LinkedHashMap的实现代码：

public V get(Object key) {
Entry e = (Entry)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}

void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}

void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];

小心LinkedHashMap的get()方法 (一)