java集合框架(三):LinkedHashMap


声明:本文转载自https://my.oschina.net/chenzanjin/blog/1557857,转载目的在于传递更多信息,仅供学习交流之用。如有侵权行为,请联系我,我会及时删除。

        LinkedHashMap的数据结构跟HashMap类似,只是在节点上多加了指向前和向后的两个属性,也可以概括为:数组+链表(双向)+红黑树(java8增加了红黑树),如下图所示:

    

一、类的定义

public class LinkedHashMap<K,V>     extends HashMap<K,V>     implements Map<K,V> {}

二、存储单元

        LinkedHashMap的基本存储单元也是继承HashMap的存储单元,新增了两个节点属性,一个指向前,一个向后。

// 定义在LinkedHashMap类中 static class Entry<K,V> extends HashMap.Node<K,V> {         Entry<K,V> before, after;// 指向前后节点         Entry(int hash, K key, V value, Node<K,V> next) {             super(hash, key, value, next);         } }
// 定义在HashMap类中 static class Node<K,V> implements Map.Entry<K,V> {         final int hash;         final K key;         V value;         Node<K,V> next;          Node(int hash, K key, V value, Node<K,V> next) {             this.hash = hash;             this.key = key;             this.value = value;             this.next = next;         } }

三、构造函数

        构造函数主要是初始化父类的属性值,LinkedHashMap新增的就只有一个:

boolean accessOrder = false;// 链表是否按照节点访问顺序排序,true:是,false:否。它起到什么作用,我在文章后面会解析。

public LinkedHashMap() {         // 调用父类构造器         super();         accessOrder = false; }
// 指定初始容量 public LinkedHashMap(int initialCapacity) {         super(initialCapacity);         accessOrder = false; }
// 指定初始容量和负载因子(负载因子一般使用默认的) public LinkedHashMap(int initialCapacity, float loadFactor) {         super(initialCapacity, loadFactor);         accessOrder = false; }
// 指定初始容量,负载因子,是否按访问顺序排序 public LinkedHashMap(int initialCapacity,                          float loadFactor,                          boolean accessOrder) {         super(initialCapacity, loadFactor);         this.accessOrder = accessOrder; }
// 可以把其他map的元素加载进来 public LinkedHashMap(Map<? extends K, ? extends V> m) {}

四、双向链表的构造

        LinkedHashMap构建双向链表是通过重写父类HashMap的方法newNode(int hash, K key, V value, Node<K,V> e)实现的。当往LinkedHashMap中插入新节点的时候,其直接调用父类HashMap的put方法,put方法生产新节点的时候会调用newNode方法。

        来看看重写之后的newNode方法做了什么:

 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {         LinkedHashMap.Entry<K,V> p =              new LinkedHashMap.Entry<K,V>(hash, key, value, e);         // 这个方法就是构建双向链表的         linkNodeLast(p);         return p; }

        看看双向链表的实现,如下所示。其实很好理解,就是把新节点链接到尾节点后面,并把新节点重新赋值为尾节点

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {         // 链表的尾节点         LinkedHashMap.Entry<K,V> last = tail;         // 新节点就是尾节点了         tail = p;         // 如果尾节点为空,说明p是头节点         if (last == null)             head = p;         else {             // 前后节点的链接             p.before = last;             last.after = p;         } }

五、遍历实现

        LinkedHashMap的遍历是通过LinkedHashIterator抽象类实现的,它从双向链表的头节点开始遍历,直到链表的尾部。

abstract class LinkedHashIterator {         LinkedHashMap.Entry<K,V> next;         LinkedHashMap.Entry<K,V> current;         int expectedModCount;          // 构造器初始化的时候把头节点传入         LinkedHashIterator() {             next = head;             // fast-fail机制,遍历时避免节点被改变             expectedModCount = modCount;             current = null;         }         // 迭代器的hasNext()方法会调用该方法         public final boolean hasNext() {             return next != null;         }         // 迭代器的next()方法会调用该方法         final LinkedHashMap.Entry<K,V> nextNode() {             LinkedHashMap.Entry<K,V> e = next;             if (modCount != expectedModCount)                 throw new ConcurrentModificationException();             if (e == null)                 throw new NoSuchElementException();             current = e;             // 对下一个节点赋值             next = e.after;             return e;         } }

        对比LinkedHashMap与HashMap的遍历:

public static void main(String[] args) {         Map<String,String> linkedHashMap = new LinkedHashMap<String, String>();         linkedHashMap.put("NO1","小明");         linkedHashMap.put("NO2","小赵");         linkedHashMap.put("NO3","小周");          System.out.println("----遍历LinkedHashMap----");         for(Map.Entry entry:linkedHashMap.entrySet()){             System.out.println(entry.getKey() + ":" + entry.getValue());         }          Map<String,String> hashMap = new HashMap<String, String>();         hashMap.put("NO1","小明");         hashMap.put("NO2","小赵");         hashMap.put("NO3","小周");          System.out.println("-----遍历HashMap-------");         for(Map.Entry entry:hashMap.entrySet()){             System.out.println(entry.getKey() + ":" + entry.getValue());         } }

        测试结果:

        从上面的测试结果可以看出,LinkedHashMap确实可以对节点进行先进先出的排序。而HashMap的排序顺序是不确定的。

六、访问顺序排序

        文章开头讨论过属性accessOrder,它决定链表是否按节点访问的顺序排序,如果为true就是访问顺序排序,这时当某个存在的节点被操作过(比如被get()方法调用过,或者值被替换过),那么先进先出的排序就会打乱,被访问的节点会被排到最后。看一个例子:

public static void main(String[] args) {         // 指定accessOrder为true         Map<String,String> linkedHashMap = new LinkedHashMap<String, String>(10,0.75f,true);         linkedHashMap.put("NO1","小明");         linkedHashMap.put("NO2","小赵");         linkedHashMap.put("NO3","小周");         // 对NO1进行get操作         linkedHashMap.get("NO1");          System.out.println("----按访问顺序遍历LinkedHashMap----");         for(Map.Entry entry:linkedHashMap.entrySet()){             System.out.println(entry.getKey() + ":" + entry.getValue());         } }

        测试结果:

        访问排序的实现是在每个操作函数里面调用了方法afterNodeAccess,来看看它的实现:

void afterNodeAccess(Node<K,V> e) { // move node to last         LinkedHashMap.Entry<K,V> last;         if (accessOrder && (last = tail) != e) {             LinkedHashMap.Entry<K,V> p =                 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;             p.after = null;             // 以下操作主要把当前访问的节点移到链表的尾部             if (b == null)                 head = a;             else                 b.after = a;             if (a != null)                 a.before = b;             else                 last = b;             if (last == null)                 head = p;             else {                 p.before = last;                 last.after = p;             }             tail = p;             ++modCount;         } }

七、总结

        LinkedHashMap在HashMap的基础上多维护了一条双向链表,其最重要特征就是可以对map进行先进先出的遍历操作,如有需要也可以对其按访问顺序遍历。

        以上就是我对LinkedHashMap的原理的理解,如有错误之处,请批评和指正。

本文发表于2017年10月30日 08:38
(c)注:本文转载自https://my.oschina.net/chenzanjin/blog/1557857,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如有侵权行为,请联系我们,我们会及时删除.

阅读 2007 讨论 0 喜欢 0

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

你要过得好哇,这样我才能恨你啊,你要是过得不好,我都不知道该恨你还是拥抱你啊。

直抵黄龙府,与诸君痛饮尔。

那时陪伴我的人啊,你们如今在何方。

不出意外的话,我们再也不会见了,祝你前程似锦。

这世界真好,吃野东西也要留出这条命来看看

快捷链接
网站地图
提交友链
Copyright © 2016 - 2021 Cion.
All Rights Reserved.
京ICP备2021004668号-1