Java集合框架源码分析之LinkedHashMap详解
linkedhashmap简介
linkedhashmap是hashmap的子类,与hashmap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到linkedhashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同。
linkedhashmap可以用来实现lru算法(这会在下面的源码中进行分析)。
linkedhashmap同样是非线程安全的,只在单线程环境下使用。
linkedhashmap源码剖析
linkedhashmap源码如下(加入了详细的注释):
package java.util; import java.io.*; public class linkedhashmap<k,v> extends hashmap<k,v> implements map<k,v> { private static final long serialversionuid = 3801124242820219131l; //双向循环链表的头结点,整个linkedhashmap中只有一个header, //它将哈希表中所有的entry贯穿起来,header中不保存key-value对,只保存前后节点的引用 private transient entry<k,v> header; //双向链表中元素排序规则的标志位。 //accessorder为false,表示按插入顺序排序 //accessorder为true,表示按访问顺序排序 private final boolean accessorder; //调用hashmap的构造方法来构造底层的数组 public linkedhashmap(int initialcapacity, float loadfactor) { super(initialcapacity, loadfactor); accessorder = false; //链表中的元素默认按照插入顺序排序 } //加载因子取默认的0.75f public linkedhashmap(int initialcapacity) { super(initialcapacity); accessorder = false; } //加载因子取默认的0.75f,容量取默认的16 public linkedhashmap() { super(); accessorder = false; } //含有子map的构造方法,同样调用hashmap的对应的构造方法 public linkedhashmap(map<? extends k, ? extends v> m) { super(m); accessorder = false; } //该构造方法可以指定链表中的元素排序的规则 public linkedhashmap(int initialcapacity,float loadfactor,boolean accessorder) { super(initialcapacity, loadfactor); this.accessorder = accessorder; } //覆写父类的init()方法(hashmap中的init方法为空), //该方法在父类的构造方法和clone、readobject中在插入元素前被调用, //初始化一个空的双向循环链表,头结点中不保存数据,头结点的下一个节点才开始保存数据。 void init() { header = new entry<k,v>(-1, null, null, null); header.before = header.after = header; } //覆写hashmap中的transfer方法,它在父类的resize方法中被调用, //扩容后,将key-value对重新映射到新的newtable中 //覆写该方法的目的是为了提高复制的效率, //这里充分利用双向循环链表的特点进行迭代,不用对底层的数组进行for循环。 void transfer(hashmap.entry[] newtable) { int newcapacity = newtable.length; for (entry<k,v> e = header.after; e != header; e = e.after) { int index = indexfor(e.hash, newcapacity); e.next = newtable[index]; newtable[index] = e; } } //覆写hashmap中的containsvalue方法, //覆写该方法的目的同样是为了提高查询的效率, //利用双向循环链表的特点进行查询,少了对数组的外层for循环 public boolean containsvalue(object value) { // overridden to take advantage of faster iterator if (value==null) { for (entry e = header.after; e != header; e = e.after) if (e.value==null) return true; } else { for (entry e = header.after; e != header; e = e.after) if (value.equals(e.value)) return true; } return false; } //覆写hashmap中的get方法,通过getentry方法获取entry对象。 //注意这里的recordaccess方法, //如果链表中元素的排序规则是按照插入的先后顺序排序的话,该方法什么也不做, //如果链表中元素的排序规则是按照访问的先后顺序排序的话,则将e移到链表的末尾处。 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,并将双向链表还原为只有头结点的空链表 public void clear() { super.clear(); header.before = header.after = header; } //enty的数据结构,多了两个指向前后节点的引用 private static class entry<k,v> extends hashmap.entry<k,v> { // these fields comprise the doubly linked list used for iteration. entry<k,v> before, after; //调用父类的构造方法 entry(int hash, k key, v value, hashmap.entry<k,v> next) { super(hash, key, value, next); } //双向循环链表中,删除当前的entry private void remove() { before.after = after; after.before = before; } //双向循环立链表中,将当前的entry插入到existingentry的前面 private void addbefore(entry<k,v> existingentry) { after = existingentry; before = existingentry.before; before.after = this; after.before = this; } //覆写hashmap中的recordaccess方法(hashmap中该方法为空), //当调用父类的put方法,在发现插入的key已经存在时,会调用该方法, //调用linkedhashmap覆写的get方法时,也会调用到该方法, //该方法提供了lru算法的实现,它将最近使用的entry放到双向循环链表的尾部, //accessorder为true时,get方法会调用recordaccess方法 //put方法在覆盖key-value对时也会调用recordaccess方法 //它们导致entry最近使用,因此将其移到双向链表的末尾 void recordaccess(hashmap<k,v> m) { linkedhashmap<k,v> lm = (linkedhashmap<k,v>)m; //如果链表中元素按照访问顺序排序,则将当前访问的entry移到双向循环链表的尾部, //如果是按照插入的先后顺序排序,则不做任何事情。 if (lm.accessorder) { lm.modcount++; //移除当前访问的entry remove(); //将当前访问的entry插入到链表的尾部 addbefore(lm.header); } } void recordremoval(hashmap<k,v> m) { remove(); } } //迭代器 private abstract class linkedhashiterator<t> implements iterator<t> { entry<k,v> nextentry = header.after; entry<k,v> lastreturned = null; /** * the modcount value that the iterator believes that the backing * list should have. if this expectation is violated, the iterator * has detected concurrent modification. */ int expectedmodcount = modcount; public boolean hasnext() { return nextentry != header; } public void remove() { if (lastreturned == null) throw new illegalstateexception(); if (modcount != expectedmodcount) throw new concurrentmodificationexception(); linkedhashmap.this.remove(lastreturned.key); lastreturned = null; expectedmodcount = modcount; } //从head的下一个节点开始迭代 entry<k,v> nextentry() { if (modcount != expectedmodcount) throw new concurrentmodificationexception(); if (nextentry == header) throw new nosuchelementexception(); entry<k,v> e = lastreturned = nextentry; nextentry = e.after; return e; } } //key迭代器 private class keyiterator extends linkedhashiterator<k> { public k next() { return nextentry().getkey(); } } //value迭代器 private class valueiterator extends linkedhashiterator<v> { public v next() { return nextentry().value; } } //entry迭代器 private class entryiterator extends linkedhashiterator<map.entry<k,v>> { public map.entry<k,v> next() { return nextentry(); } } // these overrides alter the behavior of superclass view iterator() methods iterator<k> newkeyiterator() { return new keyiterator(); } iterator<v> newvalueiterator() { return new valueiterator(); } iterator<map.entry<k,v>> newentryiterator() { return new entryiterator(); } //覆写hashmap中的addentry方法,linkedhashmap并没有覆写hashmap中的put方法, //而是覆写了put方法所调用的addentry方法和recordaccess方法, //put方法在插入的key已存在的情况下,会调用recordaccess方法, //在插入的key不存在的情况下,要调用addentry插入新的entry void addentry(int hash, k key, v value, int bucketindex) { //创建新的entry,并插入到linkedhashmap中 createentry(hash, key, value, bucketindex); //双向链表的第一个有效节点(header后的那个节点)为近期最少使用的节点 entry<k,v> eldest = header.after; //如果有必要,则删除掉该近期最少使用的节点, //这要看对removeeldestentry的覆写,由于默认为false,因此默认是不做任何处理的。 if (removeeldestentry(eldest)) { removeentryforkey(eldest.key); } else { //扩容到原来的2倍 if (size >= threshold) resize(2 * table.length); } } void createentry(int hash, k key, v value, int bucketindex) { //创建新的entry,并将其插入到数组对应槽的单链表的头结点处,这点与hashmap中相同 hashmap.entry<k,v> old = table[bucketindex]; entry<k,v> e = new entry<k,v>(hash, key, value, old); table[bucketindex] = e; //每次插入entry时,都将其移到双向链表的尾部, //这便会按照entry插入linkedhashmap的先后顺序来迭代元素, //同时,新put进来的entry是最近访问的entry,把其放在链表末尾 ,符合lru算法的实现 e.addbefore(header); size++; } //该方法是用来被覆写的,一般如果用linkedhashmap实现lru算法,就要覆写该方法, //比如可以将该方法覆写为如果设定的内存已满,则返回true,这样当再次向linkedhashmap中put //entry时,在调用的addentry方法中便会将近期最少使用的节点删除掉(header后的那个节点)。 protected boolean removeeldestentry(map.entry<k,v> eldest) { return false; } }
总结
关于linkedhashmap的源码,给出以下几点比较重要的总结:
1、从源码中可以看出,linkedhashmap中加入了一个head头结点,将所有插入到该linkedhashmap中的entry按照插入的先后顺序依次加入到以head为头结点的双向循环链表的尾部。
1、实际上就是hashmap和linkedlist两个集合类的存储结构的结合。在linkedhashmapmap中,所有put进来的entry都保存在哈希表中,但它又额外定义了一个以head为头结点的空的双向循环链表,每次put进来entry,除了将其保存到对哈希表中对应的位置上外,还要将其插入到双向循环链表的尾部。
2、linkedhashmap由于继承自hashmap,因此它具有hashmap的所有特性,同样允许key和value为null。
3、注意源码中的accessorder标志位,当它false时,表示双向链表中的元素按照entry插入linkedhashmap到中的先后顺序排序,即每次put到linkedhashmap中的entry都放在双向链表的尾部,这样遍历双向链表时,entry的输出顺序便和插入的顺序一致,这也是默认的双向链表的存储顺序;当它为true时,表示双向链表中的元素按照访问的先后顺序排列,可以看到,虽然entry插入链表的顺序依然是按照其put到linkedhashmap中的顺序,但put和get方法均有调用recordaccess方法(put方法在key相同,覆盖原有的entry的情况下调用recordaccess方法),该方法判断accessorder是否为true,如果是,则将当前访问的entry(put进来的entry或get出来的entry)移到双向链表的尾部(key不相同时,put新entry时,会调用addentry,它会调用createntry,该方法同样将新插入的元素放入到双向链表的尾部,既符合插入的先后顺序,又符合访问的先后顺序,因为这时该entry也被访问了),否则,什么也不做。
4、注意构造方法,前四个构造方法都将accessorder设为false,说明默认是按照插入顺序排序的,而第五个构造方法可以自定义传入的accessorder的值,因此可以指定双向循环链表中元素的排序规则,一般要用linkedhashmap实现lru算法,就要用该构造方法,将accessorder置为true。
5、linkedhashmap并没有覆写hashmap中的put方法,而是覆写了put方法中调用的addentry方法和recordaccess方法,我们回过头来再看下hashmap的put方法:
// 将“key-value”添加到hashmap中 public v put(k key, v value) { // 若“key为null”,则将该键值对添加到table[0]中。 if (key == null) return putfornullkey(value); // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 int hash = hash(key.hashcode()); int i = indexfor(hash, table.length); for (entry<k,v> e = table[i]; e != null; e = e.next) { object k; // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出! if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { v oldvalue = e.value; e.value = value; e.recordaccess(this); return oldvalue; } } // 若“该key”对应的键值对不存在,则将“key-value”添加到table中 modcount++; //将key-value添加到table[i]处 addentry(hash, key, value, i); return null; }
当要put进来的entry的key在哈希表中已经在存在时,会调用recordaccess方法,当该key不存在时,则会调用addentry方法将新的entry插入到对应槽的单链表的头部。
我们先来看recordaccess方法:
//覆写hashmap中的recordaccess方法(hashmap中该方法为空), //当调用父类的put方法,在发现插入的key已经存在时,会调用该方法, //调用linkedhashmap覆写的get方法时,也会调用到该方法, //该方法提供了lru算法的实现,它将最近使用的entry放到双向循环链表的尾部, //accessorder为true时,get方法会调用recordaccess方法 //put方法在覆盖key-value对时也会调用recordaccess方法 //它们导致entry最近使用,因此将其移到双向链表的末尾 void recordaccess(hashmap<k,v> m) { linkedhashmap<k,v> lm = (linkedhashmap<k,v>)m; //如果链表中元素按照访问顺序排序,则将当前访问的entry移到双向循环链表的尾部, //如果是按照插入的先后顺序排序,则不做任何事情。 if (lm.accessorder) { lm.modcount++; //移除当前访问的entry remove(); //将当前访问的entry插入到链表的尾部 addbefore(lm.header); } }
该方法会判断accessorder是否为true,如果为true,它会将当前访问的entry(在这里指put进来的entry)移动到双向循环链表的尾部,从而实现双向链表中的元素按照访问顺序来排序(最近访问的entry放到链表的最后,这样多次下来,前面就是最近没有被访问的元素,在实现、lru算法时,当双向链表中的节点数达到最大值时,将前面的元素删去即可,因为前面的元素是最近最少使用的),否则什么也不做。
再来看addentry方法:
//覆写hashmap中的addentry方法,linkedhashmap并没有覆写hashmap中的put方法, //而是覆写了put方法所调用的addentry方法和recordaccess方法, //put方法在插入的key已存在的情况下,会调用recordaccess方法, //在插入的key不存在的情况下,要调用addentry插入新的entry void addentry(int hash, k key, v value, int bucketindex) { //创建新的entry,并插入到linkedhashmap中 createentry(hash, key, value, bucketindex); //双向链表的第一个有效节点(header后的那个节点)为近期最少使用的节点 entry<k,v> eldest = header.after; //如果有必要,则删除掉该近期最少使用的节点, //这要看对removeeldestentry的覆写,由于默认为false,因此默认是不做任何处理的。 if (removeeldestentry(eldest)) { removeentryforkey(eldest.key); } else { //扩容到原来的2倍 if (size >= threshold) resize(2 * table.length); } } void createentry(int hash, k key, v value, int bucketindex) { //创建新的entry,并将其插入到数组对应槽的单链表的头结点处,这点与hashmap中相同 hashmap.entry<k,v> old = table[bucketindex]; entry<k,v> e = new entry<k,v>(hash, key, value, old); table[bucketindex] = e; //每次插入entry时,都将其移到双向链表的尾部, //这便会按照entry插入linkedhashmap的先后顺序来迭代元素, //同时,新put进来的entry是最近访问的entry,把其放在链表末尾 ,符合lru算法的实现 e.addbefore(header); size++; }
同样是将新的entry插入到table中对应槽所对应单链表的头结点中,但可以看出,在createentry中,同样把新put进来的entry插入到了双向链表的尾部,从插入顺序的层面来说,新的entry插入到双向链表的尾部,可以实现按照插入的先后顺序来迭代entry,而从访问顺序的层面来说,新put进来的entry又是最近访问的entry,也应该将其放在双向链表的尾部。
上面还有个removeeldestentry方法,该方法如下:
//该方法是用来被覆写的,一般如果用linkedhashmap实现lru算法,就要覆写该方法, //比如可以将该方法覆写为如果设定的内存已满,则返回true,这样当再次向linkedhashmap中put //entry时,在调用的addentry方法中便会将近期最少使用的节点删除掉(header后的那个节点)。 protected boolean removeeldestentry(map.entry<k,v> eldest) { return false; } }
该方法默认返回false,我们一般在用linkedhashmap实现lru算法时,要覆写该方法,一般的实现是,当设定的内存(这里指节点个数)达到最大值时,返回true,这样put新的entry(该entry的key在哈希表中没有已经存在)时,就会调用removeentryforkey方法,将最近最少使用的节点删除(head后面的那个节点,实际上是最近没有使用)。
6、linkedhashmap覆写了hashmap的get方法:
//覆写hashmap中的get方法,通过getentry方法获取entry对象。 //注意这里的recordaccess方法, //如果链表中元素的排序规则是按照插入的先后顺序排序的话,该方法什么也不做, //如果链表中元素的排序规则是按照访问的先后顺序排序的话,则将e移到链表的末尾处。 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; }
先取得entry,如果不为null,一样调用recordaccess方法,上面已经说得很清楚,这里不在多解释了。
7、最后说说linkedhashmap是如何实现lru的。
首先,当accessorder为true时,才会开启按访问顺序排序的模式,才能用来实现lru算法。我们可以看到,无论是put方法还是get方法,都会导致目标entry成为最近访问的entry,因此便把该entry加入到了双向链表的末尾(get方法通过调用recordaccess方法来实现,put方法在覆盖已有key的情况下,也是通过调用recordaccess方法来实现,在插入新的entry时,则是通过createentry中的addbefore方法来实现),这样便把最近使用了的entry放入到了双向链表的后面,多次操作后,双向链表前面的entry便是最近没有使用的,这样当节点个数满的时候,删除的最前面的entry(head后面的那个entry)便是最近最少使用的entry。
结束语
以上就是本文关于java集合框架源码分析之linkedhashmap详解的全部内容,希望对大家学习java能够有所帮助。欢迎大家参阅本站其他专题,感谢大家读的支持!
上一篇: 使用vim编辑器的一些常用开发功能
推荐阅读
-
Java集合框架源码分析之LinkedHashMap详解
-
Java集合框架源码分析之LinkedHashMap详解
-
java集合类源码分析之Set详解
-
基于Java中最常用的集合类框架之HashMap(详解)
-
死磕 java集合之ArrayList源码分析
-
死磕 java集合之LinkedHashMap源码分析
-
Java基础之Collections框架Map接口实现类HashMap及其源码分析(1)
-
Java源码解析——集合框架(四)——LinkedListLinkedList原码分析
-
死磕 java集合之TreeMap源码分析(二)- 内含红黑树分析全过程
-
死磕 java集合之TreeMap源码分析(三)- 内含红黑树分析全过程