LinkedHashMap如何保证有序

我们常说linkedHashMap是有序的&＃xff0c;这个有序也是分为两种的&＃xff0c;分别是&＃xff1a;插入顺序和访问顺序&＃xff0c;我们可以通俗的认为&＃xff1a;linkedHashMap &＃61; hashmap &＃43; 双向链表

以下的学习是基于jdk8

根据linkedHashMap的结构来看&＃xff0c;是依赖于hashmap的&＃xff0c;通过查看源码&＃xff0c;我们也会发现&＃xff0c;linkedHashMap只是维护了一个链表&＃xff0c;并没有put、remove方法的具体实现&＃xff0c;因为linkedHashMap的设计思想是&＃xff1a;对数据的操作&＃xff0c;是依赖于hashmap中的方法&＃xff0c;只是在其中的一些细节方法&＃xff0c;linkedHashMap会进行扩展&＃xff0c;接下来我们先说属性有哪些

属性信息

/*** The head (eldest) of the doubly linked list.* 链表的head节点*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.* 链表的尾结点*/transient LinkedHashMap.Entry<K,V> tail;/*** The iteration ordering method for this linked hash map: true* for access-order, false for insertion-order.* false:表示插入顺序&＃xff1b;true表示读取顺序* &＃64;serial*/final boolean accessOrder;

AccessOrder

该属性是来区分当前linkedHashMap是按照访问顺序排序&＃xff0c;还是按照put顺序有序&＃xff0c;当该参数为true的时候&＃xff0c;表示按照读取顺序有序&＃xff1b;默认为false&＃xff0c;按照put顺序有序

newNode()

在调用put方法的时候&＃xff0c;会调用父类hashmap的put方法&＃xff0c;那linkedHashMap如何维护节点之间的顺序呢&＃xff1f;
在put方法中&＃xff0c;如果得到当前key要存储的位置&＃xff0c;会调用newNode()方法&＃xff0c;初始化一个node节点&＃xff0c;

linkedHashMap对该方法&＃xff0c;进行了覆写&＃xff0c;

/*** 在向map中put元素的时候&＃xff0c;是会初始化一个node节点&＃xff0c;如果是linkedHashMap&＃xff0c;调用的是该方法* 在该方法中&＃xff0c;可以看到&＃xff0c;会初始化一个LinkedHashMap.Entry节点&＃xff0c;然后将该节点插入到linkedHashMap的双向链表中* 默认是加到链表尾部* &＃64;param hash* &＃64;param key* &＃64;param value* &＃64;param e* &＃64;return*/Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p &＃61;new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p);return p;}


这里可以看到&＃xff0c;除了初始化一个节点之外&＃xff0c;还会调用linkNodeLast方法&＃xff0c;在linkedNodeLast方法中&＃xff0c;会将p节点添加到自己维护的双向链表的尾部

/*** 这是加入到链表尾部的方法* 如果当前是第一个put的元素&＃xff0c;那p就是head&＃xff0c;否则&＃xff0c;就把节点放到tail的后面* &＃64;param p*/private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last &＃61; tail;tail &＃61; p;if (last &＃61;&＃61; null)head &＃61; p;else {p.before &＃61; last;last.after &＃61; p;}}


按访问顺序有序

假如在初始化linkedHashMap对象的时候&＃xff0c;指定accessOrder为true&＃xff0c;那表示按照访问顺序有序&＃xff0c;在get方法中&＃xff0c;会对访问到的元素进行处理

public V get(Object key) {Node<K,V> e;// 这里的getNode调用的是hashmap中的方法&＃xff0c;获取到当前key所对应的valueif ((e &＃61; getNode(hash(key), key)) &＃61;&＃61; null)return null;/*** 如果是按照访问顺序有序&＃xff0c;会把获取到的e节点插入到链表的尾部&＃xff0c;然后返回e.value*/if (accessOrder)afterNodeAccess(e);return e.value;}


这里可以看到&＃xff0c;如果是按照访问顺序有序的话&＃xff0c;会额外调用afterNodeAccess()方法&＃xff0c;如果为false&＃xff0c;会直接返回获取到的节点value值&＃xff0c;afterNodeAccess方法简单而言&＃xff0c;就是将e节点移到链表的尾部&＃xff0c;所以&＃xff0c;我们可以认为&＃xff0c;最近访问的在元素在链表的最后面

所以&＃xff1a;对于按照put顺序有序的设置&＃xff0c;在put元素的时候&＃xff0c;本身就会把最新插入的元素放入到链表的尾部&＃xff0c;如果是按照访问顺序有序的话&＃xff0c;在get的时候&＃xff0c;会把访问的元素移到链表的尾部&＃xff0c;根据该特点&＃xff0c;也可以实现一个简单的LRU算法

对于hashmap和linkedHashMap来说&＃xff0c;最大的区别就是&＃xff1a;hashmap是无序的&＃xff0c;linkedHashMap自己维护了节点的顺序