现在的位置: 首页 > 综合 > 正文

LinkedHashMap

2018年12月12日 ⁄ 综合 ⁄ 共 6005字 ⁄ 字号 评论关闭

LinkedHashMap就是在HashMap的基础之上,再将每个元素用双向链表连接起来,如此,可以设定两种连接顺序,一种是按照元素的插入的顺序进行连接,另一种是LRU算法(最近最少使用)次序,即对于没有访问过的元素将出现在链表的前面,而访问过的元素被调整到链表的后面

http://blog.csdn.net/turkeyzhou/article/details/3201513

LinkedHashMap中的entry是继承HashMap的entry,但是增加了before和after的指针

  private static class Entry<K,V> extends HashMap.Entry<K,V> {
        //他有两个指针分别指向了before和after的Entry
        //<span style="color:#ff0000;">请注意,不要把next和他们混淆了,next的用处还是和HashMap中一</span>//样;
        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();
        }
    }

因为LinkedHashMap是继承的HashMap,那么他们的增删改的操作基本一致,只是利用了模板模式具有了不同的实现;
我们来看一下put方法吧;
下面是HashMap的put方法:

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        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) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

在LinkedHashMap中被重载的方法是addEntry;

  1. void addEntry(int hash, K key, V value, int bucketIndex) {
  2.         createEntry(hash, key, value, bucketIndex);
  3.        
  4.         Entry<K,V> eldest = header.after;
  5.         if (removeEldestEntry(eldest)) {
  6.             removeEntryForKey(eldest.key);
  7.         } else {
  8.             if (size >= threshold)
  9.                 resize(2 * table.length);
  10.         }
  11.     }
  1.     void createEntry(int hash, K key, V value, int bucketIndex) {
  2.         //和以前一样,首先操作了table序列的链表枝条;
  3.         HashMap.Entry<K,V> old = table[bucketIndex];
  4.     Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
  5.         table[bucketIndex] = e;
  6.         //关键在于这一步做了什么;我们知道他在header之前插入了Entry;
  7.         e.addBefore(header);
  8.         size++;
  9.     }

Header元素在构造的时候被初始化,记得吗,这个方法是HashMap在构造函数中利用模板模式传下来的 

  1.     void init() {
  2.         header = new Entry<K,V>(-1, nullnullnull);
  3.         header.before = header.after = header;
  4.     }

开始的时候Header头尾都是指向自身的;



第二步的时候就是被e.addBefore(header);

  1.  private void addBefore(Entry<K,V> existingEntry) {
  2.             after  = existingEntry;
  3.             before = existingEntry.before;
  4.             before.after = this;
  5.             after.before = this;
  6.         }


如果再put那么就是:


我们再来看一看他的keySet是如何得到的:

重载了newKeyIterator() 的方法:  

  1. Iterator<K> newKeyIterator()   { return new KeyIterator();   }

我们看一下迭代器是如何实现的:

  1.  private abstract class LinkedHashIterator<T> implements Iterator<T> {
  2.         //从开始的图3我们可见,第一次加入的节点是位于header.after的位置;
  3.     Entry<K,V> nextEntry    = header.after;
  4.        
  5.     Entry<K,V> lastReturned = null;
  6.     int expectedModCount = modCount;
  7.         
  8.         //nextnEntry不是header就不是末尾
  9.     public boolean hasNext() {         
  10.             return nextEntry != header;
  11.     }
  12.     public void remove() {
  13.         if (lastReturned == null)
  14.         throw new IllegalStateException();
  15.         if (modCount != expectedModCount)
  16.         throw new ConcurrentModificationException();
  17.             LinkedHashMap.this.remove(lastReturned.key);
  18.             lastReturned = null;
  19.             expectedModCount = modCount;
  20.     }
  21.     Entry<K,V> nextEntry() {
  22.         if (modCount != expectedModCount)
  23.         throw new ConcurrentModificationException();
  24.             if (nextEntry == header)
  25.                 throw new NoSuchElementException();
  26.             //指针沿着after往下走
  27.             Entry<K,V> e = lastReturned = nextEntry;
  28.             //预先把nextEntry移动到了下一位
  29.             nextEntry = e.after;
  30.             return e;
  31.     }
  32.     }


把next方法抽象出去是因为values和keySet的迭代次序是一样的,就是返回的数值不同,所以可以把
Entry的遍历方式推到上层,而values和keys分别留给子类实现;


  1.   private class KeyIterator extends LinkedHashIterator<K> {
  2.     public K next() { return nextEntry().getKey(); }
  3.     }
  4.     private class KeyIterator extends LinkedHashIterator<K> {
  5.     public K next() { return nextEntry().getKey(); }
  6.     }
  7.     private class ValueIterator extends LinkedHashIterator<V> {
  8.     public V next() { return nextEntry().value; }
  9.     }
  10.     private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
  11.     public Map.Entry<K,V> next() { return nextEntry(); }
  12.     }

package tst;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


class CachedMap<K,V> extends LinkedHashMap<K,V> {
    private int maxEntres;
    
    /*
     * 
     */
    public CachedMap(int initCap, int maxEnt) {
        super(initCap);
        maxEntres = maxEnt;
    }
    
    
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest ) {
        boolean flag = false;
        if (size() > maxEntres ) {
            //System.out.println("rm "+eldest.getKey());
            flag = true;
        }
        return flag;
          
    }
    
}

public class Tar {
        public static void iterClc(Map<String,String> mp) {
            for (Map.Entry<String, String> ent : mp.entrySet()) {
                System.out.print(ent.getKey() + ":" + ent.getValue()+"  ");
            }
            System.out.println();
            
        }
	public static void main(String[] args) throws Exception{

	    Map<String, String> mp1 = new HashMap<String,String>();
	    Map<String, String> cm = new CachedMap<String, String>(3, 5);
	    mp1.put("1b", "dd");
	    mp1.put("34", "vc");
	    mp1.put("rt", "ae");
	    mp1.put("yu", "ao");
	    mp1.put("pu", "21");
	    //iterClc(mp1);
	    System.out.println();
	    
	    cm.put("1b", "dd");
	    cm.put("34", "vc");
	    cm.put("rt", "ae");
	    cm.put("yu", "ao");
	    cm.put("pu", "21");
	    //iterClc(cm);
	    
	    cm.put("py", "dd");
	    //iterClc(cm);
	    cm.put("34", "vd");
	   // iterClc(cm);
	    cm.put("oy", "87");
	    iterClc(cm);
	    
	    String val = cm.get("pu");
	    cm.remove("pu");
	    
	    System.out.println("rm");
	    iterClc(cm);
	    
	    cm.put("nss", "caac");
	    
	    iterClc(cm);
	    
	    
	    
	}
}

output:

rt:ae  yu:ao  pu:21  py:dd  oy:87  
rm
rt:ae  yu:ao  py:dd  oy:87  
rt:ae  yu:ao  py:dd  oy:87  nss:caac  

上面的例子重载了LinkedHashMap的removeEldestEntry函数,在原始定义中,

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

经过重载之后,我们的数据结构就成了一个cache,一旦原始个数超过给定的数目,就会把最先放入map的元素删除

值得注意的是,如果put一个key值相同的,原有的value就要被替换,但是这个entry的顺序不变化

在放入"34":"vd"之前,“34”:“vc”是最老的元素,放入之后,"34":"vd"成为最老的元素,所以再放入新元素,会把"34":"vd"给删除。

抱歉!评论已关闭.