`
zhangyi0618
  • 浏览: 62032 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

编码最佳实践--小心LinkedHashMap的get()方法

 
阅读更多
http://www.blogjava.net/aoxj/archive/2012/06/18/381001.html
编码最佳实践(4)--小心LinkedHashMap的get()方法

   这是一个来自实际项目的例子,在这个案例中,有同事基于jdk中的LinkedHashMap设计了一个LRUCache,为了提高性能,使用了 ReentrantReadWriteLock 读写锁:写锁对应put()方法,而读锁对应get()方法,期望通过读写锁来实现并发get()。
   代码实现如下:
private ReentrantReadWriteLock  lock = new ReentrantReadWriteLock ();
lruMap = new LinkedHashMap<K, V>(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<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
                return null;
        e.recordAccess(this);
        return e.value;
}

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

void transfer(HashMap.Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
                int index = indexFor(e.hash, newCapacity);
                e.next = newTable[index];
                newTable[index] = e;
        }
}   
    前面LRUCache的代码中,是这样初始化LinkedHashMap的:
lruMap = new LinkedHashMap<K, V>(initialCapacity, loadFactor, true)
    LinkedHashMap构造函数中的参数true表明LinkedHashMap按照访问的次序来排序。这里所谓的按照访问的次序来排序的含义是:当调用LinkedHashMap 的get(key)或者put(key, value)时,如果key在map中被包含,那么LinkedHashMap会将key对象的entry放在线性结构的最后。正是因为LinkedHashMap提 供按照访问的次序来排序的功能,所以它才需要改写HashMap的get(key)方法(HashMap不需要排序)和HashMap.Entry的recordAccess(HashMap)方法。注 意addBefore(lm.header)是将该entry放在header线性表的最后。(参考LinkedHashMap.Entry extends HashMap.Entry 比起HashMap.Entry多了before,  after两个域,是双向的)
    在上面的LRUCache中,为了提供性能,通过使用ReentrantReadWriteLock读写锁实现了并发get(),结果导致了并发问题。解决问题的方式很简单, 去掉读写锁,让put()/get()都使用普通互斥锁就可以了。当然,这样get()方法就无法实现并发读了,对性能有所影响。
   总结,在使用LinkedHashMap时,请小心LinkedHashMap的get()方法。
分享到:
评论

相关推荐

    RiteLinked - Rust 中的 LinkedHashMap 和 LinkedHashSet

    RiteLinked——类似HashMap的容器,以用户可控的顺序保存它们的键值对RiteLinked提供了LinkedHashMap和LinkedHashSet更多最新版本。您可以在std或no_std环境中轻松使用它。一些实用的功能组合,支持,帮助您更好地将...

    Java集合框架源码分析之LinkedHashMap详解

    LinkedHashMap的init方法是覆写了HashMap中的init方法,该方法在父类的构造方法和Clone、readObject中在插入元素前被调用,用于初始化一个空的双向循环链表,头结点中不保存数据,头结点的下一个节点才开始保存数据...

    LinkedHashmap的使用

    LinkedHashMap提供多种构造方法,其中两个重要的选项是`accessOrder`参数。如果设为`true`,则表示按照访问顺序排序;若设为`false`(默认),则按照插入顺序排序。 1. `public LinkedHashMap(int initialCapacity,...

    java中HashMap,LinkedHashMap,TreeMap,HashTable的区别

    ### Java中HashMap, LinkedHashMap, TreeMap,HashTable的区别 ...如果需要保持插入顺序,则`LinkedHashMap`是最佳选择;而对于多线程环境,应优先考虑使用`ConcurrentHashMap`而不是`HashTable`。

    JavaLinkedHashMap源码解析Java开发Ja

    Java LinkedHashMap 是一个根据插入顺序或者访问顺序来维护元素顺序的哈希表与链表相结合的数据结构。在 Java 集合框架中,它继承自 HashMap 类,并实现了 Map 接口。LinkedHashMap 的特点在于,它不仅仅是一个哈希...

    java集合-LinkedHashMap的使用

    LinkedHashMap是Java中的一种特殊类型的HashMap,它保留了插入顺序,即按照元素插入的先后顺序进行排序

    LinkedHashMap

    LinkedHashMap源代码,Java中Map的一种实现子类。

    HashMap,HashTable,LinkedHashMap,TreeMap的区别

    如果需要同步,可以选择 HashTable 或者使用 Collections 的 synchronizedMap 方法使 HashMap 或者 LinkedHashMap 具有同步的能力。 * 是否需要保持顺序?如果需要保持顺序,可以选择 LinkedHashMap。 * 是否需要...

    java软件技术文档-深入java8的集合4:LinkedHashMap的实现原理.pdf

    K,V&gt; p) { } 这些方法是 HashMap 为 LinkedHashMap 提供的回调接口,用于在插入、访问和删除节点后执行特定的操作。LinkedHashMap 利用这些回调方法来维护其内部链表的顺序。 1. **afterNodeAccess(Node,V&gt; p)**: ...

    LonelyInteger-LinkedHashMap

    这个项目的源代码“LonelyInteger-LinkedHashMap-master”可能包含以下部分: - `LonelyInteger`类:包含了实现上述逻辑的方法,如`findLonelyInteger`。 - 测试用例:使用JUnit或其他测试框架,验证`LonelyInteger`...

    一文搞懂Java的LinkedHashMap.docx

    System.out.println(key + " : " + linkedHashMap.get(key)); } ``` 输出将是: ``` 沉 : 沉默王二 默 : 沉默王二 王 : 沉默王二 二 : 沉默王二 ``` 与HashMap不同,LinkedHashMap在遍历时会按照元素的插入顺序依次...

    Java实现LRU缓存机制:深入解析与高效编码实践

    本文将详细介绍如何在Java中实现LRU缓存机制,包括其原理、实现方式以及编码实践。 LRU缓存机制是一种非常实用的缓存淘汰策略,它在很多应用场景中都有广泛的应用。在Java中实现LRU缓存,可以通过使用LinkedHashMap...

    Java使用LinkedHashMap进行分数排序

    使用LinkedHashMap进行分数排序是Java中的一种非常实用的方法,特别是在学生成绩统计的问题中。它可以提高排序效率,避免传统排序方法的浪费,並且可以保持插入时的顺序。 知识点: 1. Java中使用LinkedHashMap...

    LinkedHashMap-java

    LinkedHashMap的主要方法 - `put(K key, V value)`:将指定的键值对插入到映射中。如果映射中已经存在该键,则旧值将被替换。 - `get(Object key)`:返回指定键关联的值。如果映射不包含此键,将返回`null`。 - `...

Global site tag (gtag.js) - Google Analytics