LinkedHashMap

LinkedHashMap

这是一个继承自HashMap的类,在类说明中，这是一个非同步的，不能在多线程环境下使用，否则要自己实现同步.有两种模式，一种是元素访问的次数排序，一种是插入的时间排序
Linked内部含有一个private transient Entry header;来记录元素插入的顺序或者是元素被访问的顺序。
正如 LinkedHashMap的文档所说，LinkedHashMap简直就是为了实现LRU Cache(Least Recently Used)而编写的。正因为如此，在oscache或者是ehcache都使用到了LinkedHashMap。（oscache中是否使用LRU是可以配置的）
那么，这是如何实现的呢，见源码如下:

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;
}

这是取值的代码，请看得到实体的代码:

final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
 }

完全是从hashMap中得到实体对象，根据key.
这里调用了recordAccess方法，然后再返回value.请看:

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

如果accessOrder实true,那是是访问排序，如果为false则为插入排序。
transient volatile int modCount;
这个参数可以用来标识修改次数，也可以用来标识访问次数

private void remove() {
            before.after = after;
            after.before = before;
}

从列表上移除该对象.

 private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
}

把这个对象添加到第一个.

评论

5 楼 a123159521 2011-04-26  

兄弟，你写了很多,其实linked hashMap和hashMap的存储是一致的，只是多了一个排序的过程，关于hashMap(可以查看我历史文章).排序就利于做缓存了，因为排在前面的优先级高，比如有10000个数据，我查找第一个就找到了，其实就循环了一次。

4 楼 zxy861114 2011-04-06  

下面来看看，取整个map元素的过程.
看之前，了解一下LinkedHashMap的构造过程。
private LinkedHash\Iterator()
{
     this$0 = LinkedHashMap.this;
     super();
     nextEntry = header.after;
     lastReturned = null;
     expectedModCount = modCount;
}
请注意nextEntry的初始化过程.
取的过程肯定是由迭代器完成。由于KeyIterator与EntrySet的next方法都与EntryIterator的next方法类似，以EntryIterator说明。
public Map.Entry next()
{
    return nextEntry();
}

LinkedHashMap.Entry nextEntry()
{
     if(modCount != expectedModCount)
         throw new ConcurrentModificationException();
     if(nextEntry == header)
     {
         throw new NoSuchElementException();
     } else
     {
         LinkedHashMap.Entry entry = lastReturned = nextEntry;
         nextEntry = entry.after;
         return entry;
     }
}
从nextEntry我们可以看出，它是将heaeder的后续元素一个个取出来的过程。
至于accessOrder，当为true时。对于方法
void recordAccess(HashMap hashmap)
{
    LinkedHashMap linkedhashmap = (LinkedHashMap)hashmap;
    if(linkedhashmap.accessOrder)
    {
        linkedhashmap.modCount++;
        remove();
        addBefore(linkedhashmap.header);
    }
}
它会将访问到的元素，删除掉，然后到加header的前面。由前面分析就可知，排序就会将访问过程计算在内。

3 楼 zxy861114 2011-04-06  

它主要是一般的HashMap存放数据的过程。不过请注意addEntry方法。
void addEntry(int i, Object obj, Object obj1, int j)
{
    createEntry(i, obj, obj1, j);
    Entry entry = header.after;
    if(removeEldestEntry(entry))
        removeEntryForKey(entry.key);
    else
    if(size >= threshold)
        resize(2 * table.length);
}
createEntry方法会调用entry1.addBefore(header)方法，它会在header前面插入一个元素.这是我要谈的重点.
void createEntry(int i, Object obj, Object obj1, int j)
{
    HashMap.Entry entry = table[j];
    Entry entry1 = new Entry(i, obj, obj1, entry);
    table[j] = entry1;
    entry1.addBefore(header);
    size++;
}
此处为addBeofre的指针处理过程。
private void addBefore(Entry entry)
{
     after = entry;
     before = entry.before;
     before.after = this;
     after.before = this;
}

我以图解来看看这段代码贴不上来，晕。（就是addBefore,从只有header到有两个Entry的过程，addBefore时，after指针指向的是按插入顺序的）

2 楼 zxy861114 2011-04-06  

"如果accessOrder实true,那是是访问排序，如果为false则为插入排序。 "
你的这里的访问排序，包括插入。差点说你错啦，哈哈！

我来接着你的讲讲，排序的过程.

首先实例化LinkedHashMap时，会首先初始化父类HashMap
public HashMap()
  {
      entrySet = null;
      loadFactor = 0.75F;
      threshold = 12;
      table = new Entry[16];
      init();
  }
它会调用LinkedHashMap中的init方法对header进行初始化.
void init()
{
     header = new Entry(-1, null, null, null);
     header.before = header.after = header;
}

接着，再来看看元素放进去的过程.这个put方法为父类hashMap的方法。
public Object put(Object obj, Object obj1)
{
    if(obj == null)
        return putForNullKey(obj1);
    int i = hash(obj.hashCode());
    int j = indexFor(i, table.length);
    for(Entry entry = table[j]; entry != null; entry = entry.next)
    {
        Object obj2;
        if(entry.hash == i && ((obj2 = entry.key) == obj || obj.equals(obj2)))
        {
            Object obj3 = entry.value;
            entry.value = obj1;
            entry.recordAccess(this);
            return obj3;
        }
    }

    modCount++;
    addEntry(i, obj, obj1, j);
    return null;
}

1 楼 zxy861114 2011-04-06  

晕，我写了这么多竟然评论，我公司代理过滤。汗！