您的当前位置：首页正文

linkedHashMap的应用

2024-11-07 来源：个人技术集锦

一. 概述： 
        LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。LinkedHashMap实现与HashMap的不同之处在于，LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序（insert-order）或者是访问顺序，其中默认的迭代访问顺序就是插入顺序，即可以按插入的顺序遍历元素，这点和HashMap有很大的不同。


二.LinkedHashMap的accessOrder 
    1.访问顺序 
        LinkedHashMap除了支持默认的插入顺序，还支持访问顺序。所谓访问顺序(access-order)是指在迭代遍历列表中的元素时最近访问的元素会排在LinkedHashMap的尾部 。从其构造函数中可以看出当accessOrder设为true时即为访问顺序。

Java代码  

java代码  ，继承的HashMap的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;
    }

HashMap的 getEntry()方法

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


java代码，recordAccess()

        /**
         * 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);  //将元素m放到链表的末尾
            }
        }
java代码，addBefore() 

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

     2.访问顺序时程序举例

Java代码  
  1. public class LinkedHashMapTest {  
  2.   
  3.     public static void main(String[] args) {  
  4.         Map<String, Object> map = new LinkedHashMap<String, Object>(16, 0.75F, true);  
  5.   
  6.         for (int i = 1; i <= 5; i++) {  
  7.             map.put(i + "", i);  
  8.         }  
  9.         Iterator<Entry<String, Object>> iterator = map.entrySet().iterator();  
  10.         while (iterator.hasNext()) {  
  11.             System.out.println(iterator.next().getValue());  
  12.         }  
  13.   
  14.         map.get("2");  
  15.         map.get("3");  
  16.         System.out.println("===============split line==================");  
  17.   
  18.         Iterator<Entry<String, Object>> iterator2 = map.entrySet().iterator();  
  19.         while (iterator2.hasNext()) {  
  20.             System.out.println(iterator2.next().getValue());  
  21.         }  
  22.     }  
  23. }  

     
    输出如下：

Java代码  
  1. 1  
  2. 2  
  3. 3  
  4. 4  
  5. 5  
  6. ===============separator bar ======================  
  7. 1  
  8. 4  
  9. 5  
  10. 2  
  11. 3  

 

    通过例子可以看出，最近经常使用的元素就放在后面，最近最少使用的就排在了链表的前面。
    
三.LinkedHashMap的扩展应用 
    基于LinkedHashMap的访问顺序的特点，可构造一个LRU（Least Recently Used）最近最少使用简单缓存。也有一些开源的缓存产品如ehcache的淘汰策略（LRU）就是在LinkedHashMap上扩展的。
    
    1.LruCache的简单代码 

Java代码  
  1. public class LruCache<K, V> extends LinkedHashMap<K, V> {  
  2.          
  3.             private static final long serialVersionUID = -9062508768983283300L;  
  4.              
  5.             /** 最大容量 */  
  6.             private int maxCapacity;  
  7.          
  8.             public LruCache(int maxCapacity) {  
  9.                 super(16, 0.75f, true);  
  10.                 this.maxCapacity = maxCapacity;  
  11.             }  
  12.          
  13.             public int getMaxCapacity() {  
  14.                 return this.maxCapacity;  
  15.             }  
  16.          
  17.             public void setMaxCapacity(int maxCapacity) {  
  18.                 this.maxCapacity = maxCapacity;  
  19.             }  
  20.          
  21.             /** 
  22.              * 当列表中的元素个数大于指定的最大容量时，返回true,并将最老的元素删除。 
  23.              */  
  24.             @Override  
  25.             protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {  
  26.                 if (super.size() > maxCapacity) {  
  27.                     return true;  
  28.                 }  
  29.                 return false;  
  30.             }  
  31.         }  
 

    2.测试代码

Java代码  
  1. public class LruCacheTest {  
  2.          
  3.             public static void main(String[] args) {  
  4.                 LruCache<String, Object> cache = new LruCache<String, Object>(10);  
  5.          
  6.                 for (int i = 1; i <= 15; i++) {  
  7.                     cache.put(i + "", i);  
  8.                 }  
  9.          
  10.                 // 此时访问指定KEY的元素  
  11.                 cache.get("10");  
  12.          
  13.                 Iterator<Entry<String, Object>> iterator = cache.entrySet().iterator();  
  14.                 for (; iterator.hasNext();) {  
  15.                     Entry<String, Object> entry = iterator.next();  
  16.                     System.out.println("key=" + entry.getKey() + ",value=" + entry.getValue());  
  17.                 }  
  18.             }  
  19.         }  

 

        输出如下：

Java代码  
  1. key=7,value=7  
  2. key=8,value=8  
  3. key=9,value=9  
  4. key=11,value=11  
  5. key=12,value=12  
  6. key=13,value=13  
  7. key=14,value=14  
  8. key=15,value=15  
  9. key=10,value=10  

 


四.LinkedHashMap对上述特性支持的分析 
    1.添加时删除最老元素 
    LinkedHashMap如何在添加元素时把最早放入的元素删除的呢，LinkedHashMap没有提供put方法，而是使用基类HashMap的put方法，看下面的HashMap的put(K key, V value)方法的源代码：

Java代码  
  1. public V put(K key, V value) {  
  2.        if (key == null)  
  3.            return putForNullKey(value);  
  4.        int hash = hash(key.hashCode());  
  5.        int i = indexFor(hash, table.length);  
  6.        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  7.            Object k;  
  8.            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  9.                V oldValue = e.value;  
  10.                e.value = value;  
  11.            //HashMap中这个方法没有实现。  
  12.                e.recordAccess(this);  
  13.                return oldValue;  
  14.            }  
  15.        }  
  16.   
  17.        modCount++;  
  18.        addEntry(hash, key, value, i);  
  19.        return null;  
  20.    }  

 

     LinkedHashMap覆盖了HashMap中的这个addEntry(hash, key, value, i)方法，在 LinkedHashMap类中，removeEldestEntry（）永远返回false;
     也就是这个方法，提供了子类更强大功能扩展的机会。

Java代码  
  1.   void addEntry(int hash, K key, V value, int bucketIndex) {  
  2. createEntry(hash, key, value, bucketIndex);  
  3.   
  4. // Remove eldest entry if instructed, else grow capacity if appropriate  
  5. Entry<K,V> eldest = header.after;  
  6. //该方法返回false.  
  7. if (removeEldestEntry(eldest)) {  
  8.     removeEntryForKey(eldest.key);  
  9. } else {  
  10.     if (size >= threshold)  
  11.     resize(2 * table.length);  
  12. }  
  13.   }  

 

    
    2.访问时重组列表 
          在获取元素时，LinkedHashMap提供了get()方法，其代码如下：

Java代码  
  1. public V get(Object key) {  
  2.       Entry<K,V> e = (Entry<K,V>)getEntry(key);  
  3.       if (e == null)  
  4.           return null;  
  5.            //最近访问的元素重新插入到最后面。  
  6.       e.recordAccess(this);  
  7.       return e.value;  
  8. }  
 

    HashMap中这个recordAccess（）方法没有实现，只有空的方法体，在LinkedHashMap中的实现如下 ，也就是这个方法，将最近访问的元素给予重组，达到了LRU的目的。                 

Java代码  
  1. void recordAccess(HashMap<K,V> m) {  
  2.              LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
  3.                 //accessOrder要指定为true.  
  4.              if (lm.accessOrder) {  
  5.              lm.modCount++;  
  6.              remove();  
  7.              addBefore(lm.header);  
  8.              }  
  9.      }  
  10.        
  11.      
 

Copyright © 2019- zgxue.com 版权所有
京ICP备2021021884号-5

Top