现在的位置: 首页 > 编程语言 > 正文

JDK源代码分析聚集篇——-LinkedHashMap(排队不能光图快却不讲次序啊！总有个先来后到吧！)

2019年06月12日 ⁄ 编程语言 ⁄ 共 6378字 ⁄ 字号 小 中 大 ⁄ 评论关闭
在上一节的分析中，我们已经对HashMap的内部实现机制有了一定的了解，我们感受到了快速定位对我们效率带来的好处和益处，但是我们不仅在嘀咕，效率是提高了，但是我却发现次序没有，除了能够预知"NULL"键的次序以外（傻瓜都知道在哪），其他的元素的次序我都是不感知的，如何是好，排队总得有个先来后到吧，别着急，我们下面来看一下LinkedHashMap这个类，他会帮我们解决问题的！
  1. package org.corey.demo;
  3. import java.util.HashMap;
  4. import java.util.Iterator;
  5. import java.util.LinkedHashMap;
  6. import java.util.Map;
  8. public class Test {
  10.     /**
  11.      * @param args
  12.      */
  13.     public static void main(String[] args) {
  14.         Map map = new LinkedHashMap(4);
  15.         map.put("1", "corey");
  16.         map.put("2", "syna");
  17.         map.put("3", "bobo"); 
  18.         
  19.         Iterator it=map.keySet().iterator();
  20.         System.out.println("-------------------------linked hash map----------------------");
  21.         while(it.hasNext()){
  22.             String key=(String)it.next();
  23.             System.out.println(key+":"+map.get(key));
  24.         }
  25.         
  26.         Map map2 = new HashMap(4);
  27.         map2.put("1", "corey");
  28.         map2.put("2", "syna");
  29.         map2.put("3", "bobo"); 
  30.         
  31.         Iterator it2=map2.keySet().iterator();
  32.         System.out.println("-------------------------hash map----------------------");
  33.         while(it2.hasNext()){
  34.             String key=(String)it2.next();
  35.             System.out.println(key+":"+map2.get(key));
  36.         }
  38.     }
  40. }

console:

-------------------------linked hash map----------------------
1:corey
2:syna
3:bobo
-------------------------hash map----------------------
2:syna
1:corey
3:bobo

从而可见，我们的问题得到了解决；

现在我们从LinkEdHashMap代码内部来详细的分析其实现原理；

  1. private transient Entry<K,V> header;

在LinkedHashMap中含有一个Entry的属性；注意，这个Entry不是上一次我们在HashMap中见到的单向Entry,他被扩充了：

  1.   private static class Entry<K,V> extends HashMap.Entry<K,V> {
  2.         //他有两个指针分别指向了before和after的Entry
  3.         //请注意，不要把next和他们混淆了，next的用处还是和HashMap中一//样；
  4.         Entry<K,V> before, after;
  6.     Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
  7.             super(hash, key, value, next);
  8.         }
  10.      
  11.         private void remove() {
  12.             before.after = after;
  13.             after.before = before;
  14.         }
  16.      、
  17.         //在当前节点前面插入节点；
  18.         private void addBefore(Entry<K,V> existingEntry) {
  19.             after  = existingEntry;
  20.             before = existingEntry.before;
  21.             before.after = this;
  22.             after.before = this;
  23.         }
  25.      
  26.         void recordAccess(HashMap<K,V> m) {
  27.             LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  28.             if (lm.accessOrder) {
  29.                 lm.modCount++;
  30.                 remove();
  31.                 addBefore(lm.header);
  32.             }
  33.         }
  35.         void recordRemoval(HashMap<K,V> m) {
  36.             remove();
  37.         }
  38.     }

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

  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.                 e.recordAccess(this);
  12.                 return oldValue;
  13.             }
  14.         }
  16.         modCount++;
  17.         addEntry(hash, key, value, i);
  18.         return null;
  19.     }
  1.  void addEntry(int hash, K key, V value, int bucketIndex) {
  2.     Entry<K,V> e = table[bucketIndex];
  3.         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  4.         if (size++ >= threshold)
  5.             resize(2 * table.length);
  6.     }

在上一节中我们已经详细的分析过了，在LinkedHashMap中被重载的方法是addEntry;

  1. void addEntry(int hash, K key, V value, int bucketIndex) {
  2.         createEntry(hash, key, value, bucketIndex);
  4.        
  5.         Entry<K,V> eldest = header.after;
  6.         if (removeEldestEntry(eldest)) {
  7.             removeEntryForKey(eldest.key);
  8.         } else {
  9.             if (size >= threshold)
  10.                 resize(2 * table.length);
  11.         }
  12.     }
  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, null, null, null);
  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;
  7.     int expectedModCount = modCount;
  8.         
  9.         //nextnEntry不是header就不是末尾
  10.     public boolean hasNext() {         
  11.             return nextEntry != header;
  12.     }
  14.     public void remove() {
  15.         if (lastReturned == null)
  16.         throw new IllegalStateException();
  17.         if (modCount != expectedModCount)
  18.         throw new ConcurrentModificationException();
  20.             LinkedHashMap.this.remove(lastReturned.key);
  21.             lastReturned = null;
  22.             expectedModCount = modCount;
  23.     }
  25.     Entry<K,V> nextEntry() {
  26.         if (modCount != expectedModCount)
  27.         throw new ConcurrentModificationException();
  28.             if (nextEntry == header)
  29.                 throw new NoSuchElementException();
  31.             //指针沿着after往下走
  32.             Entry<K,V> e = lastReturned = nextEntry;
  33.             //预先把nextEntry移动到了下一位
  34.             nextEntry = e.after;
  35.             return e;
  36.     }
  37.     }

把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.     }
  8.     private class ValueIterator extends LinkedHashIterator<V> {
  9.     public V next() { return nextEntry().value; }
  10.     }
  12.     private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
  13.     public Map.Entry<K,V> next() { return nextEntry(); }
  14.     }

这里我个人觉得是处理得十分巧妙的地方；

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞