jdk源码阅读笔记-LinkedHashMap

Map是Javacollectionframework中重要的组成部分,特别是HashMap是在我们在日常的开发的过程中使用的最多的一个集合。但是遗憾的是,存放在HashMap中元素都是无序的,原因是我们在put或get数据的时候都是根据key的hash值来确定元素的位置。在具体的业务场景中,我们更多的希望对于HashMap集合能够进行顺序访问,好在jdk中已经给我们提供了一种解决方案,那就是Li...

jdk源码阅读笔记-LinkedHashMap

  Map是Java collection framework 中重要的组成部分,特别是HashMap是在我们在日常的开发的过程中使用的最多的一个集合。但是遗憾的是,存放在HashMap中元素都是无序的,原因是我们在put或get数据的时候都是根据key的hash值来确定元素的位置。在具体的业务场景中,我们更多的希望对于HashMap集合能够进行顺序访问,好在 jdk 中已经给我们提供了一种解决方案,那就是LinkedHashMap。该类继承与HashMap,因此HashMap拥有的特性它都有,同时还具备其他的特性,比如实现了插入顺序排序和访问顺序排序,默认以插入顺序排序。同时也能够利用LinkedHashMap实现LRU算法。LinkedHashMap api很少,基本都是调用HashMap的方法,所以建议熟悉HashMap源码之后再来看这篇文章,我之前也写过【HashMap源码分析笔记】,大家可以点进去参考一下。

  LRU算法:LRU是Least Recently Used的缩写,即最近最少使用,也就是说将热点数据放到最前面,冷门数据放到最后,当达到一定条件后会删除冷门数据,在一个缓存系统中经常会用到该算法。

  

  一、LinkedHashMap与HashMap数据结构对比

  从上图可以看到HashMap的数据结构位数组 单向链表,数据存放在链表的node节点上,每个node节点上都有一个指针指向下一个节点,每个数组index上的链表跟其他的index上面的链表是部相互链接的。LinkedHashMap在部破坏HashMap的结构基础之上,每个node节点都额外增加了两个指针,分别指向了前一个节点和下一个节点,所以在HashMap上所有的node节点形成了一条双向链表,每次添加往LinkedHashMap put数据的时候都将节点放在双向链表的最后位置,从而实现了插入顺序排序。在LinkedHashMap中,节点的定义如下:

/**  * HashMap.Node subclass for normal LinkedHashMap entries.  */ 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的 Node内部类,但是又额外添加了两个属性,before和after,分别指向前一个节点和后一个节点,形成一个双向链表。

  二、LinkedHashMap类结构

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

  LinkedHashMap继承了HashMap,所以拥有HashMap的所有特性。

  三、成员变量

 /**  * The head (eldest) of the doubly linked list.  */ 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: <tt>true</tt>  * for access-order, <tt>false</tt> for insertion-order.  *  * @serial  */ final boolean accessOrder;

  LinkedHashMap在HashMap的基础之上添加了head、tail和accessOrder属性:

  head:双向链表的表头

  tail: 双向链表的表尾

  accessOrder:排序的标志。默认为false,按插入顺序排序。可以通过构造方法设置为true,按访问顺序排序。

  四、构造方法

 /**  * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance  * with the specified initial capacity and load factor.  *  * @param  initialCapacity the initial capacity  * @param  loadFactorthe load factor  * @throws IllegalArgumentException if the initial capacity is negative  *or the load factor is nonpositive  */ public LinkedHashMap(int initialCapacity, float loadFactor) {  super(initialCapacity, loadFactor);  accessOrder = false; } /**  * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance  * with the specified initial capacity and a default load factor (0.75).  *  * @param  initialCapacity the initial capacity  * @throws IllegalArgumentException if the initial capacity is negative  */ public LinkedHashMap(int initialCapacity) {  super(initialCapacity);  accessOrder = false; } /**  * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance  * with the default initial capacity (16) and load factor (0.75).  */ public LinkedHashMap() {  super();  accessOrder = false; } /**  * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with  * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>  * instance is created with a default load factor (0.75) and an initial  * capacity sufficient to hold the mappings in the specified map.  *  * @param  m the map whose mappings are to be placed in this map  * @throws NullPointerException if the specified map is null  */ public LinkedHashMap(Map<? extends K, ? extends V> m) {  super();  accessOrder = false;  putMapEntries(m, false); } /**  * Constructs an empty <tt>LinkedHashMap</tt> instance with the  * specified initial capacity, load factor and ordering mode.  *  * @param  initialCapacity the initial capacity  * @param  loadFactorthe load factor  * @param  accessOrder  the ordering mode - <tt>true</tt> for  *access-order, <tt>false</tt> for insertion-order  * @throws IllegalArgumentException if the initial capacity is negative  *or the load factor is nonpositive  */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {  super(initialCapacity, loadFactor);  this.accessOrder = accessOrder; }

  5个构造方法都是直接调用父类HashMap的构造方法。

  

  五、添加数据put(Object key,V value)

  LinkedHashMap中并没有对HashMap进行复写,也就是说添加数据的时候其实就是调用的HashMap的put方法,那么它是怎么进行排序的呢?下面我们一起来看看HashMap中是怎么添加数据的吧。

public V put(K key, V value) {  return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {  Node<K,V>[] tab; Node<K,V> p; int n, i;  if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;  /*** 通过位与的方式来确定下标位置,判断当前下标位置是否为空,如果为空直接放入到该位置上* 不为空则通过equals方法来寻找当前位置上面的元素,如果有相同的key,则将覆盖掉,如果没有则将node放置在对应* 位置上面*/  if ((p = tab[i = (n - 1) & hash]) == null)//直接放到数组中tab[i] = newNode(hash, key, value, null);//创建新节点  else {//当前位置不为空Node<K,V> e; K k;if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//已存在相同的key的数据,将其覆盖 e = p;else if (p instanceof TreeNode)//当前位置是红黑树,将Node节点放到红黑树中 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//创建新树节点else {//
源文地址:https://www.guoxiongfei.cn/cntech/4169.html