LinkedHashMap源码解读与实现LRU缓存

图片 12

一、概述

Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU算法。

 
Java中的LinkedHashMap
此实现与 HashMap
的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。
此链接列表定义了迭代顺序,该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。

LinkedHashMap继承HashMap
自定义全局变量header表示头节点

二、Java的LRU算法

Java的LRU算法的基础是LinkedHashMap,LinkedHashMap继承了HashMap,并且在HashMap的基础上进行了一定的改动,以实现LRU算法。

LinkedHashMap和TreeMap的区别 
首先2个都是map,所以用key取值肯定是没区别的,区别在于用Iterator遍历的时候 
LinkedHashMap保存了记录的插入顺序,先插入的先遍历到 
TreeMap默认是按升序排,也可以指定排序的比较器。遍历的时候按升序遍历。 

    private transient Entry<K,V> header;

    private final boolean accessOrder;

1、HashMap

首先需要说明的是,HashMap将每一个节点信息存储在Entry<K,V>结构中。Entry<K,V>中存储了节点对应的key、value、hash信息,同时存储了当前节点的下一个节点的引用。因此Entry<K,V>是一个单向链表。HashMap的存储结构是一个数组加单向链表的形式。每一个key对应的hashCode,在HashMap的数组中都可以找到一个位置;而如果多个key对应了相同的hashCode,那么他们在数组中对应在相同的位置上,这时,HashMap将把对应的信息放到Entry<K,V>中,并使用链表连接这些Entry<K,V>。

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

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

下面贴一下HashMap的put方法的代码,并进行分析

  public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);

     //以上信息不关心,下面是正常的插入逻辑。

     //首先计算hashCode
        int hash = hash(key);
     //通过计算得到的hashCode,计算出hashCode在数组中的位置
        int i = indexFor(hash, table.length);

     //for循环,找到在HashMap中是否存在一个节点,对应的key与传入的key完全一致。如果存在,说明用户想要替换该key对应的value值,因此直接替换value即可返回。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

     //逻辑执行到此处,说明HashMap中不存在完全一致的kye.调用addEntry,新建一个节点保存key、value信息,并增加到HashMap中
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

在上面的代码中增加了一些注释,可以对整体有一个了解。下面具体对一些值得分析的点进行说明。

<1> int i = indexFor(hash, table.length);

可以看一下源码:

  static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

为什么获得的hashCode(h)要和(length-1)进行按位与运算?这是为了保证去除掉h的高位信息。如果数组大小为8(1000),而计算出的h的值为10(1010),如果直接获取数组的index为10的数据,肯定会抛出数组超出界限异常。所以使用按位与(0111&1010),成功清除掉高位信息,得到2(0010),表示对应数组中index为2的数据。效果与取余相同,但是位运算的效率明显更高。

但是这样有一个问题,如果length为9,获取得length-1信息为8(1000),这样进行位运算,不但不能清除高位数据,得到的结果肯定不对。所以数组的大小一定有什么特别的地方。通过查看源码,可以发现,HashMap无时无刻不在保证对应的数组个数为2的n次方。

首先在put的时候,调用inflateTable方法。重点在于roundUpToPowerOf2方法,虽然它的内容包含大量的位相关的运算和处理,没有看的很明白,但是注释已经明确了,会保证数组的个数为2的n次方。

private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}

其次,在addEntry等其他位置,也会使用(2 * table.length)、table.length
<< 1等方式,保证数组的个数为2的n次方。

<2> for (Entry<K,V> e = table[i]; e != null; e = e.next)

因为HashMap使用的是数组加链表的形式,所以通过hashCode获取到在数组中的位置后,得到的不是一个Entry<K,V>,而是一个Entry<K,V>的链表,一定要循环链表,获取key对应的value。

<3> addEntry(hash, key, value, i);

先判断数组个数是否超出阈值,如果超过,需要增加数组个数。然后会新建一个Entry,并加到数组中。

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    /**
     * Like addEntry except that this version is used when creating entries
     * as part of Map construction or "pseudo-construction" (cloning,
     * deserialization).  This version needn't worry about resizing the table.
     *
     * Subclass overrides this to alter the behavior of HashMap(Map),
     * clone, and readObject.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

一.LinkedHashMap的存储结构

同时LinkedHashMap的自定义内部类Entry也继承了HashMap的Entry,但是新增了两个指针before和after。在哈希表的基础上又构成了双向链接列表。

2、LinkedHashMap

LinkedHashMap在HashMap的基础上,进行了修改。首先将Entry由单向链表改成双向链表。增加了before和after两个队Entry的引用。

    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

同时,LinkedHashMap提供了一个对Entry的引用header(private transient
Entry<K,V>
header)。header的作用就是永远只是HashMap中所有成员的头(header.after)和尾(header.before)。这样把HashMap本身的数组加链表的格式进行了修改。在LinkedHashMap中,即保留了HashMap的数组加链表的数据保存格式,同时增加了一套header作为开始标记的双向链表(我们暂且称之为header的双向链表)。LinkedHashMap就是通过header的双向链表来实现LRU算法的。header.after永远指向最近最不常使用的那个节点,删除的话,就是删除这个header.after对应的节点。相对的,header.before指向的就是刚刚使用过的那个节点。

LinkedHashMap并没有提供put方法,但是LinkedHashMap重写了addEntry和createEntry方法,如下:

    /**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

    /**
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

HashMap的put方法,调用了addEntry方法;HashMap的addEntry方法又调用了createEntry方法。因此可以把上面的两个方法和HashMap中的内容放到一起,方便分析,形成如下方法:

  void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

同样,先判断是否超出阈值,超出则增加数组的个数。然后创建Entry对象,并加入到HashMap对应的数组和链表中。与HashMap不同的是LinkedHashMap增加了e.addBefore(header);和removeEntryForKey(eldest.key);这样两个操作。

首先分析一下e.addBefore(header)。其中e是LinkedHashMap.Entry对象,addBefore代码如下,作用就是讲header与当前对象相关联,使当前对象增加到header的双向链表的尾部(header.before):

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

其次是另一个重点,代码如下:

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }

其中,removeEldestEntry判断是否需要删除最近最不常使用的那个节点。LinkedHashMap中的removeEldestEntry(eldest)方法永远返回false,如果我们要实现LRU算法,就需要重写这个方法,判断在什么情况下,删除最近最不常使用的节点。removeEntryForKey的作用就是将key对应的节点在HashMap的数组加链表结构中删除,源码如下:

  final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

removeEntryForKey是HashMap的方法,对LinkedHashMap中header的双向链表无能为力,而LinkedHashMap又没有重写这个方法,那header的双向链表要如何处理呢。

仔细看一下代码,可以看到在成功删除了HashMap中的节点后,调用了e.recordRemoval(this);方法。这个方法在HashMap中为空,LinkedHashMap的Entry则实现了这个方法。其中remove()方法中的两行代码为双向链表中删除当前节点的标准代码,不解释。

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }void recordRemoval(HashMap<K,V> m) {
            remove();
        }

以上,LinkedHashMap增加节点的代码分析完毕,可以看到完美的将新增的节点放在了header双向链表的末尾。

但是,这样显然是先进先出的算法,而不是最近最不常使用算法。需要在get的时候,更新header双向链表,把刚刚get的节点放到header双向链表的末尾。我们来看看get的源码:

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

代码很短,第一行的getEntry调用的是HashMap的getEntry方法,不需要解释。真正处理header双向链表的代码是e.recordAccess(this)。看一下代码:

     /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

首先在header双向链表中删除当前节点,再将当前节点添加到header双向链表的末尾。当然,在调用LinkedHashMap的时候,需要将accessOrder设置为true,否则就是FIFO算法。

图片 1

   private static class Entry<K,V> extends HashMap.Entry<K,V> {
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

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

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

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

三、Android的LRU算法

Android同样提供了HashMap和LinkedHashMap,而且总体思路有些类似,但是实现的细节明显不同。而且Android提供的LruCache虽然使用了LinkedHashMap,但是实现的思路并不一样。Java需要重写removeEldestEntry来判断是否删除节点;而Android需要重写LruCache的sizeOf,返回当前节点的大小,Android会根据这个大小判断是否超出了限制,进行调用trimToSize方法清除多余的节点。

Android的sizeOf方法默认返回1,默认的方式是判断HashMap中的数据个数是否超出了设置的阈值。也可以重写sizeOf方法,返回当前节点的大小。Android的safeSizeOf会调用sizeOf方法,其他判断阈值的方法会调用safeSizeOf方法,进行加减操作并判断阈值。进而判断是否需要清除节点。

Java的removeEldestEntry方法,也可以达到同样的效果。Java需要使用者自己提供整个判断的过程,两者思路还是有些区别的。

sizeOf,safeSizeOf不需要说明,而put和get方法,虽然和Java的实现方式不完全一样,但是思路是相同的,也不需要分析。在LruCache中put方法的最后,会调用trimToSize方法,这个方法用于清除超出的节点。它的代码如下:

  public void trimToSize(int maxSize)
  {
    while (true)
    {
      Object key;
      Object value;
      synchronized (this) {
        if ((this.size < 0) || ((this.map.isEmpty()) && (this.size != 0))) {
          throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
        }
      if (size <= maxSize) {
        break;
      }

        Map.Entry toEvict = (Map.Entry)this.map.entrySet().iterator().next();

        key = toEvict.getKey();
        value = toEvict.getValue();
        this.map.remove(key);
        this.size -= safeSizeOf(key, value);
        this.evictionCount += 1;
      }

      entryRemoved(true, key, value, null);
    }
  }

重点需要说明的是Map.Entry toEvict =
(Map.Entry)this.map.entrySet().iterator().next();这行代码。它前面的代码判断是否需要删除最近最不常使用的节点,后面的代码用于删除具体的节点。这行代码用于获取最近最不常使用的节点。

首先需要说明的问题是,Android的LinkedHashMap和Java的LinkedHashMap在思路上一样,也是使用header保存双向链表。在put和get的时候,会更新对应的节点,保存header.after指向最久没有使用的节点;header.before用于指向刚刚使用过的节点。所以Map.Entry
toEvict =
(Map.Entry)this.map.entrySet().iterator().next();这行最终肯定是获取header.after节点。下面逐步分析代码,就可以看到是如何实现的了。

首先,map.entrySet(),HashMap定义了这个方法,LinkedHashMap没有重写这个方法。因此调用的是HashMap对应的方法:

  public Set<Entry<K, V>> entrySet() {
        Set<Entry<K, V>> es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
    }

上面代码不需要细说,new一个EntrySet类的实例。而EntrySet也是在HashMap中定义,LinkedHashMap中没有。

  private final class EntrySet extends AbstractSet<Entry<K, V>> {
        public Iterator<Entry<K, V>> iterator() {
            return newEntryIterator();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Entry))
                return false;
            Entry<?, ?> e = (Entry<?, ?>) o;
            return containsMapping(e.getKey(), e.getValue());
        }
        public boolean remove(Object o) {
            if (!(o instanceof Entry))
                return false;
            Entry<?, ?> e = (Entry<?, ?>)o;
            return removeMapping(e.getKey(), e.getValue());
        }
        public int size() {
            return size;
        }
        public boolean isEmpty() {
            return size == 0;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }

  Iterator<Entry<K, V>> newEntryIterator() { return new EntryIterator(); }

代码中很明显的可以看出,Map.Entry toEvict =
(Map.Entry)this.map.entrySet().iterator().next(),就是要调用newEntryIterator().next(),就是调用(new
EntryIterator()).next()。而EntryIterator类在LinkedHashMap中是有定义的。

  private final class EntryIterator
            extends LinkedHashIterator<Map.Entry<K, V>> {
        public final Map.Entry<K, V> next() { return nextEntry(); }
    }

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        LinkedEntry<K, V> next = header.nxt;
        LinkedEntry<K, V> lastReturned = null;
        int expectedModCount = modCount;

        public final boolean hasNext() {
            return next != header;
        }

        final LinkedEntry<K, V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            LinkedEntry<K, V> e = next;
            if (e == header)
                throw new NoSuchElementException();
            next = e.nxt;
            return lastReturned = e;
        }

        public final void remove() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (lastReturned == null)
                throw new IllegalStateException();
            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }
    }

现在可以得到结论,trimToSize中的那行代码得到的就是header.next对应的节点,也就是最近最不常使用的那个节点。

  1. LinkedHashMap是继承HashMap,也就继承了HashMap的结构,也就是图中的结构2,在下文中我用”Entry数组+next链表”来描述。而LinkedHashMap有其自己的变量header,也就是图中的结构1,下文中我用”header链表”来描述。
  2. 结构1中的Entry和结构2中的Entry本是同一个,结构1中应该就只有一个header,它指向的是结构2中的e1
    e2,但这样会使结构图难画。为了说明问题的方便,我把结构2里的e1
    e2在结构1中多画一个。

构造方法:

 

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

二.LinkedHashMap成员变量

可以看到,默认调用了父类HashMap的构造方法,传入loadFactor,默认为
false,代表按照插入顺序进行迭代。可以显式设置为
true,代表以访问顺序进行迭代。

Java代码  图片 2

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }
  1. // LinkedHashMap维护了一个链表,header是链表头。此链表不同于HashMap里面的那个next链表  
  2. private transient Entry<K, V> header;  
  3.   
  4. // LRU:Least Recently Used最近最少使用算法  
  5. // accessOrder决定是否使用此算法,accessOrder=true使用  
  6. private final boolean accessOrder;  

可以看到最后一步构造调用了init()方法,在HashMap中方法为空。而在LinkedHashMap中重写了这个方法,进一步实现了对其元素Entry的初始化。

 

  @Override
    void init() {
        header = new Entry<>(-1, null, null,   );
        header.before = header.after = header;
    }

三.LinkedHashMap里的Entry对象

在HashMap中,其Put方法如下。它的Entry.recordAccess是空方法。
过程如下:先哈希定位到数组中哈希桶位置,然后遍历entry链表,如果hash相同并且key相同,覆盖原value,更新成新value。如果对应哈希桶中没有元素,调用addEntry()方法

Java代码  图片 3

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

   void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

   void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
  1.       // 继承了HashMap.Entry,其他几个方法边用边分析  
  2. rivate static class Entry<K, V> extends HashMap.Entry<K, V> {  
  3. // 增加了两个属性,每个Entry有before Entry和after Entry,就构成了一个链表  
  4. Entry<K, V> before, after;  
  5.   
  6. Entry(int hash, K key, V value, HashMap.Entry<K, V> next) {  
  7.     super(hash, key, value, next);  
  8. }  
  9.   
  10. private void addBefore(Entry<K, V> existingEntry) {  
  11.     …..  
  12. }  
  13.   
  14. void recordAccess(HashMap<K, V> m) {  
  15.     …..  
  16. }  
  17.   
  18. void recordRemoval(HashMap<K, V> m) {  
  19.     …..  
  20. }  
  21.   
  22. private void remove() {  
  23.     …..  
  24. }  

而LinkedHashMap没有重写Put方法,而是重写了父Entry.recordAccess()方法。还有addEntry(),createEntry()方法
如果accessOrder为真,表示按照访问顺序迭代时,调用addBefore(lm.header)方法,表示将元素放到最后。(双向链表,头结点的before代表最后元素)
注意:这里调用情况是,同一个哈希桶对应的entry链表的调整。

 

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

四.构造函数

重写Entry.addBefore方法,实现链表的链接

Java代码  图片 4

private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
  1. //默认accessOrder为false  
  2. //调用HashMap构造函数  
  3. public LinkedHashMap() {  
  4.     super();  
  5.     accessOrder = false;  
  6. }  
  7.   
  8. //如果想实现LRU算法,参考这个构造函数  
  9. public LinkedHashMap(int initialCapacity, float loadFactor,  
  10.         boolean accessOrder) {  
  11.     super(initialCapacity, loadFactor);  
  12.     this.accessOrder = accessOrder;  
  13. }  
  14.   
  15. //模板方法模式,HashMap构造函数里面的会调用init()方法  
  16. //初始化的时候map里没有任何Entry,让header.before = header.after = header  
  17. void init() {  
  18.     header = new Entry<K, V>(-1, null, null, null);  
  19.     header.before = header.after = header;  
  20. }  

重写的addEnty,createEntry方法。主要是重写createEntry方法,通过调用
e.addBefore(header)完成链表的链接。

 

   /**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

    /**
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

五.存数据

LinkedHashMap 重写了父类 HashMap 的 get
方法,在每一次get后调用了我们前面分析过的recordAccess方法,将元素放置到最后一个,这样就形成了一个按访问顺序迭代的哈希链表。由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。

Java代码  图片 5

   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;
    }
  1. //LinkedHashMap没有put(K key, V value)方法,只重写了被put调用的addEntry方法  
  2. //1是HashMap里原有的逻辑,23是LinkedHashMap特有的  
  3. void addEntry(int hash, K key, V value, int bucketIndex) {  
  4.     createEntry(hash, key, value, bucketIndex);  
  5.   
  6.     Entry<K, V> eldest = header.after;  
  7.     //3.如果有必要,移除LRU里面最老的Entry,否则判断是否该resize  
  8.     if (removeEldestEntry(eldest)) {  
  9.         removeEntryForKey(eldest.key);  
  10.     } else {  
  11.         if (size >= threshold)  
  12.             resize(2 * table.length);  
  13.     }  
  14. }  
  15.   
  16. void createEntry(int hash, K key, V value, int bucketIndex) {  
  17.     //1.同HashMap一样:在Entry数组+next链表结构里面加入Entry  
  18.     HashMap.Entry<K, V> old = table[bucketIndex];  
  19.     Entry<K, V> e = new Entry<K, V>(hash, key, value, old);  
  20.     table[bucketIndex] = e;  
  21.     //2.把新Entry也加到header链表结构里面去  
  22.     e.addBefore(header);  
  23.     size++;  
  24. }  
  25.   
  26. //默认是false,我们可以重写此方法  
  27. protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {  
  28.     return false;  
  29. }  
  30.   
  31. private static class Entry<K, V> extends HashMap.Entry<K, V> {  
  32.     //链表插入元素四个步骤,对着图看  
  33.     private void addBefore(Entry<K, V> existingEntry) {  
  34.         after = existingEntry;                //1  
  35.         before = existingEntry.before;     //2  
  36.         before.after = this;                   //3  
  37.         after.before = this;                   //4  
  38.     }  
  39.        }  
  40.        
  41.         //如果走到resize,会调用这里重写的transfer  
  42. //HashMap里面的transfer是n * m次运算,LinkedHashtable重写后是n + m次运算  
  43. void transfer(HashMap.Entry[] newTable) {  
  44.     int newCapacity = newTable.length;  
  45.     //直接遍历header链表,HashMap里面是遍历Entry数组  
  46.     for (Entry<K, V> e = header.after; e != header; e = e.after) {  
  47.         int index = indexFor(e.hash, newCapacity);  
  48.         e.next = newTable[index];  
  49.         newTable[index] = e;  
  50.     }  
  51.  }  

     下面三个图是初始化LinkedHashMap——->添加Entry
e1——>添加Entry e2时,LinkedHashMap结构的变化。

如何通过这种数据结构实现lru缓存?
该哈希映射的迭代顺序就是最后访问其条目的顺序,这种映射很适合构建 LRU
缓存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V>
eldest)
方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序,默认返回
false,这样,此映射的行为将类似于正常映射,即永远不能移除最旧的元素。

图片 6

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

图片 7

LinkedHashMap在添加元素的时候会对此进行判断

图片 8

    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

 

通过重写removeEldestEntry可以实现自定义容量的linkedlist
LRU具体实现代码如下:

六.取数据

public class LRUCache<K, V> {
    private static final float hashTableLoadFactor = 0.75f;
    private LinkedHashMap<K, V> map;
    private int cacheSize;
    static Logger logger = LoggerFactory.getLogger(LRUCache.class);

    public LRUCache(int cacheSize) {
        this.cacheSize = cacheSize;
        int hashTableCapacity = (int) Math
                .ceil(cacheSize / hashTableLoadFactor) + 1;
        map = new LinkedHashMap<K, V>(hashTableCapacity, hashTableLoadFactor, true) {
            private static final long serialVersionUID = 1;

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LRUCache.this.cacheSize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized Collection<Map.Entry<K, V>> getAll() {
        return Lists.newArrayList(map.entrySet());
    }


    public static void main(String[] args) {
        LRUCache<String, String> c = new LRUCache<String, String>(3);
        c.put("1", "one");
        c.put("2", "two");
        c.put("3", "three");
        c.put("4", "four");
        if (c.get("2") == null) {
            throw new Error();
        }
        c.put("5", "five");
        c.put("4", "second four");
        c.get("5");
        for (Map.Entry<String, String> e : c.getAll()) {
            logger.info(e.getKey() + " : " + e.getValue());
        }
    }

Java代码  图片 9

  1. //重写了get(Object key)方法  
  2. public V get(Object key) {  
  3.     //1.调用HashMap的getEntry方法得到e  
  4.     Entry<K, V> e = (Entry<K, V>) getEntry(key);  
  5.     if (e == null)  
  6.         return null;  
  7.     //2.LinkedHashMap牛B的地方  
  8.     e.recordAccess(this);  
  9.     return e.value;  
  10. }  
  11.   
  12.        // 继承了HashMap.Entry  
  13. private static class Entry<K, V> extends HashMap.Entry<K, V> {  
  14.     //1.此方法提供了LRU的实现  
  15.     //2.通过12两步,把最近使用的当前Entry移到header的before位置,而LinkedHashIterator遍历的方式是从header.after开始遍历,先得到最近使用的Entry  
  16.     //3.最近使用是什么意思:accessOrder为true时,get(Object key)方法会导致Entry最近使用;put(K key, V value)/putForNullKey(value)只有是覆盖操作时会导致Entry最近使用。它们都会触发recordAccess方法从而导致Entry最近使用  
  17.     //4.总结LinkedHashMap迭代方式:accessOrder=false时,迭代出的数据按插入顺序;accessOrder=true时,迭代出的数据按LRU顺序+插入顺序  
  18.     //  HashMap迭代方式:横向数组 * 竖向next链表  
  19.     void recordAccess(HashMap<K, V> m) {  
  20.         LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>) m;  
  21.         //如果使用LRU算法  
  22.         if (lm.accessOrder) {  
  23.             lm.modCount++;  
  24.             //1.从header链表里面移除当前Entry  
  25.             remove();  
  26.             //2.把当前Entry移到header的before位置  
  27.             addBefore(lm.header);  
  28.         }  
  29.     }  
  30.       
  31.     //让当前Entry从header链表消失  
  32.     private void remove() {  
  33.         before.after = after;  
  34.         after.before = before;  
  35.     }  
  36.        }  

 

七.删数据

Java代码  图片 10

  1.        // 继承了HashMap.Entry  
  2. private static class Entry<K, V> extends HashMap.Entry<K, V> {  
  3.     //LinkedHashMap没有重写remove(Object key)方法,重写了被remove调用的recordRemoval方法  
  4.     //这个方法的设计也和精髓,也是模板方法模式  
  5.     //HahsMap remove(Object key)把数据从横向数组 * 竖向next链表里面移除之后(就已经完成工作了,所以HashMap里面recordRemoval是空的实现调用了此方法  
  6.     //但在LinkedHashMap里面,还需要移除header链表里面Entry的after和before关系  
  7.     void recordRemoval(HashMap<K, V> m) {  
  8.         remove();  
  9.     }  
  10.       
  11.     //让当前Entry从header链表消失  
  12.     private void remove() {  
  13.         before.after = after;  
  14.         after.before = before;  
  15.     }  
  16. }  

 

八.LinkedHashMap EntrySet遍历

Java代码  图片 11

  1.        private abstract class LinkedHashIterator<T> implements Iterator<T> {  
  2.     //从header.after开始遍历  
  3.     Entry<K, V> nextEntry = header.after;  
  4.       
  5.     Entry<K, V> nextEntry() {  
  6.         if (modCount != expectedModCount)  
  7.             throw new ConcurrentModificationException();  
  8.         if (nextEntry == header)  
  9.             throw new NoSuchElementException();  
  10.   
  11.         Entry<K, V> e = lastReturned = nextEntry;  
  12.         nextEntry = e.after;  
  13.         return e;  
  14.     }  
  15. }  

  16. 上图中,遍历的结果是先e1然后e2。

  17. accessOrder为true时,get(e1.key)或者put(e1.key,
    value)一下,则结构1变成e2——e1——header,遍历的结果就是先e2然后e1。

 

九.总结

  1. LinkedHashMap继承HashMap,结构2里数据结构的变化交给HashMap就行了。
  2. 结构1里数据结构的变化就由LinkedHashMap里重写的方法去实现。
  3. 简言之:LinkedHashMap比HashMap多维护了一个链表。

LinkedHashMap保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.也可以在构造时用带参数,按照应用次数排序。在遍历的时候会比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关。

 

如果需要输出的顺序和输入的相同,那么用LinkedHashMap
可以实现,它还可以按读取顺序来排列.

优点:可前后查询
缺点:效率没有hashmap高

LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.也可以在构造时用带参数,按照应用次数排序。
在遍历的时候会比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关

LinkedHashMap输出时其元素是有顺序的,而HashMap输出时是随机的,如果Map映射比较复杂而又要求高效率的话,最好使用LinkedHashMap,但是多线程访问的话可能会造成不同步,所以要用Collections.synchronizedMap来包装一下,从而实现同步。其实现一般为:
    Map<String String> map = Collections.synchronizedMap(new
LinkedHashMap(<String String));

 

LinkedHashMap和HashMap的区别在于它们的基本数据结构上,看一下LinkedHashMap的基本数据结构,也就是Entry:

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    ...
}

列一下Entry里面有的一些属性吧:

1、K key

2、V value

3、Entry<K, V> next

4、int hash

5、Entry<K, V> before

6、Entry<K, V> after

其中前面四个,也就是红色部分是从HashMap.Entry中继承过来的;后面两个,也就是蓝色部分是LinkedHashMap独有的。不要搞错了next和before、After,next是用于维护HashMap指定table位置上连接的Entry的顺序的,before、After是用于维护Entry插入的先后顺序的

还是用图表示一下,列一下属性而已:

图片 12

 

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder);
 initialCapacity   初始容量
 loadFactor    加载因子,一般是 0.75f
 accessOrder   false 基于插入顺序  true  基于访问顺序(get一个元素后,这个元素被加到最后,使用了LRU 最  近最少被使用的调度算法)
如 boolean accessOrder = true; 
      Map<String, String> m = new LinkedHashMap<String, String>(20, .80f,  accessOrder  );
      m.put("1", "my"));
      m.put("2", "map"));
      m.put("3", "test"));
      m.get("1");
      m.get("2");
      Log.d("tag",  m);
     若 accessOrder == true;  输出 {3=test, 1=my, 2=map}
         accessOrder == false;  输出 {1=my, 2=map,3=test}

 

顾名思义,LRUCache就是基于LRU算法的Cache(缓存),这个类继承自LinkedHashMap,而类中看到没有什么特别的方法,这说明LRUCache实现缓存LRU功能都是源自LinkedHashMap的。LinkedHashMap可以实现LRU算法的缓存基于两点:

1、LinkedList首先它是一个Map,Map是基于K-V的,和缓存一致

2、LinkedList提供了一个boolean值可以让用户指定是否实现LRU

那么,首先我们了解一下什么是LRU:LRU即Least Recently
Used,最近最少使用,也就是说,当缓存满了,会优先淘汰那些最近最不常访问的数据
。比方说数据a,1天前访问了;数据b,2天前访问了,缓存满了,优先会淘汰数据b。

我们看一下LinkedList带boolean型参数的构造方法:

public LinkedHashMap(int initialCapacity,
         float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

就是这个accessOrder,它表示:

(1)false,所有的Entry按照插入的顺序排列

(2)true,所有的Entry按照访问的顺序排列

第二点的意思就是,如果有1 2
3这3个Entry,那么访问了1,就把1移到尾部去,即2 3
1。每次访问都把访问的那个数据移到双向队列的尾部去,那么每次要淘汰数据的时候,双向队列最尾的那个数据不就是最不常访问的那个数据了吗?换句话说,双向链表最尾的那个数据就是要淘汰的数据。

“访问”,这个词有两层意思:

1、根据Key拿到Value,也就是get方法

2、修改Key对应的Value,也就是put方法

 

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图