java 集合框架 linkedhashset 和 linkedhashmap 源码剖析-亚博电竞手机版

总体介绍

如果你已看过前面关于hashset和hashmap，以及treeset和treemap的讲解，一定能够想到本文将要讲解的linkedhashset和linkedhashmap其实也是一回事。linkedhashset和linkedhashmap在java里也有着相同的实现，前者仅仅是对后者做了一层包装，也就是说linkedhashset里面有一个linkedhashmap（适配器模式）。因此本文将重点分析linkedhashmap。

linkedhashmap实现了map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和hashmap的混合体，也就是说它同时满足hashmap和linked list的某些特性。可将linkedhashmap看作采用linked list增强的hashmap。

事实上linkedhashmap是hashmap的直接子类，二者唯一的区别是linkedhashmap在hashmap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了linkedhashmap的结构图，主体部分跟hashmap完全一样，多了header指向双向链表的头部（是一个哑元），该双向链表的迭代顺序就是entry的插入顺序。

除了可以保迭代历顺序，这种结构还有一个好处：迭代linkedhashmap时不需要像hashmap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说linkedhashmap的迭代时间就只跟entry的个数相关，而跟table的大小无关。

有两个参数可以影响linkedhashmap的性能：初始容量（inital capacity）和负载系数（load factor）。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

将对象放入到linkedhashmap或linkedhashset中时，有两个方法需要特别关心：hashcode()和equals()。hashcode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到linkedhashmap或linkedhashset中，需要*@override*hashcode()和equals()方法。

通过如下方式可以得到一个跟源map迭代顺序一样的linkedhashmap：

void foo(map m) {     map copy = new linkedhashmap(m);  }

出于性能原因，linkedhashmap是非同步的（not synchronized），如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将linkedhashmap包装成（wrapped）同步的：

map m = collections.synchronizedmap(new linkedhashmap(...));

方法剖析

get()

get(object key)方法根据指定的key值返回对应的value。该方法跟hashmap.get()方法的流程几乎完全一样，读者可自行参考前文，这里不再赘述。

put()

put(k key, v value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，则会通过addentry(int hash, k key, v value, int bucketindex)方法插入新的entry。

注意，这里的插入有两重含义：

1. 从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
2. 从header的角度看，新的entry需要插入到双向链表的尾部。

addentry()代码如下：

// linkedhashmap.addentry() void addentry(int hash, k key, v value, int bucketindex) {     if ((size >= threshold) && (null != table[bucketindex])) {         resize(2 * table.length);// 自动扩容，并重新哈希         hash = (null != key) ? hash(key) : 0;         bucketindex = hash & (table.length-1);// hash%table.length     }     // 1.在冲突链表头部插入新的entry     hashmap.entry old = table[bucketindex];     entry e = new entry<>(hash, key, value, old);     table[bucketindex] = e;     // 2.在双向链表的尾部插入新的entry     e.addbefore(header);     size  ; }

上述代码中用到了addbefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addbefore()的代码如下：

// linkedhashmap.entry.addbefor()，将this插入到existingentry的前面 private void addbefore(entry existingentry) {     after  = existingentry;     before = existingentry.before;     before.after = this;     after.before = this; }

上述代码只是简单修改相关entry的引用而已。

remove()

remove(object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeentryforkey(object key)里实现的。removeentryforkey()方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应引用）。查找过程跟get()方法类似。

注意，这里的删除也有两重含义：

1. 从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。
2. 从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。

removeentryforkey()对应的代码如下：

// linkedhashmap.removeentryforkey()，删除key值对应的entry final entry removeentryforkey(object key) {      int hash = (key == null) ? 0 : hash(key);     int i = indexfor(hash, table.length);// hash&(table.length-1)     entry prev = table[i];// 得到冲突链表     entry e = prev;     while (e != null) {// 遍历冲突链表         entry next = e.next;         object k;         if (e.hash == hash &&             ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry             modcount  ; size--;             // 1. 将e从对应bucket的冲突链表中删除             if (prev == e) table[i] = next;             else prev.next = next;             // 2. 将e从双向链表中删除             e.before.after = e.after;             e.after.before = e.before;             return e;         }         prev = e; e = next;     }     return e; }

linkedhashset

前面已经说过linkedhashset是对linkedhashmap的简单包装，对linkedhashset的函数调用都会转换成合适的linkedhashmap方法，因此linkedhashset的实现非常简单，这里不再赘述。

public class linkedhashset     extends hashset     implements set, cloneable, java.io.serializable {      // linkedhashset里面有一个linkedhashmap     public linkedhashset(int initialcapacity, float loadfactor) {         map = new linkedhashmap<>(initialcapacity, loadfactor);     }      public boolean add(e e) {//简单的方法转换         return map.put(e, present)==null;     }  }