欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JDK源码分析(6)之 LinkedHashMap 相关

程序员文章站 2022-04-28 13:57:10
`LinkedHashMap HashMap+LinkedList`,提供了顺序访问的功能;所以在看这篇博客之前最好先看一下我之前的两篇博客, "HashMap 相关" 和 "LinkedList 相关" ; 一、整体结构 1. 定义 从上述定义中也能看到 其实就是继承了 ,并加了双向链表记录顺序, ......

linkedhashmap实质是hashmap+linkedlist,提供了顺序访问的功能;所以在看这篇博客之前最好先看一下我之前的两篇博客,hashmap 相关linkedlist 相关

一、整体结构

1. 定义

public class linkedhashmap<k,v> extends hashmap<k,v> implements map<k,v> {}

JDK源码分析(6)之 LinkedHashMap 相关

从上述定义中也能看到linkedhashmap其实就是继承了hashmap,并加了双向链表记录顺序,代码和结构本身不难,但是其中结构的组织,代码复用这些地方十分值得我们学习;具体结构如图所示:

JDK源码分析(6)之 LinkedHashMap 相关

2. 构造函数和成员变量

public linkedhashmap(int initialcapacity, float loadfactor) {}
public linkedhashmap(int initialcapacity) {}
public linkedhashmap() {}
public linkedhashmap(map<? extends k, ? extends v> m) {}
public linkedhashmap(int initialcapacity, float loadfactor, boolean accessorder) {}

/**
 * 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的5个构造函数和hashmap的作用基本是一样的,都是初始化initialcapacityloadfactor,但是多了一个accessorder,这也是linkedhashmap最重要的一个成员变量了;

  • accessordertrue的时候,表示linkedhashmap中记录的是访问顺序,也是就没放get一个元素的时候,这个元素就会被移到链表的尾部;
  • accessorderfalse的时候,表示linkedhashmap中记录的是插入顺序;

3. entry关系

JDK源码分析(6)之 LinkedHashMap 相关

扎眼一看可能会觉得hashmap体系的节点继承关系比较混乱;一所以这样设计因为

  • linkedhashmap继承至hashmap,其中的节点同样有普通节点和树节点两种;并且树节点很少使用;
  • 现在的设计中,树节点是可以完全复用的,但是hashmap的树节点,会浪费双向链表的能力;
  • 如果不这样设计,则至少需要两条继承关系,并且需要抽出双向链表的能力,整个继承体系以及方法的复用会变得非常复杂,不利于扩展;

二、重要方法

上面我们已经讲了linkedhashmap就是hashmap+链表,所以我们只需要在结构有可能改变的地方加上链表的修改就可以了,结构可能改变的地方只要有put/get/replace,这里需要注意扩容的时候虽然结构改变了,但是节点的顺序仍然保持不变,所以扩容可以完全复用;

1. put 方法

  • 未找到key时,直接在最后添加一个节点
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;
}

treenode<k,v> newtreenode(int hash, k key, v value, node<k,v> next) {
  treenode<k,v> p = new treenode<k,v>(hash, key, value, next);
  linknodelast(p);
  return p;
}

private void linknodelast(linkedhashmap.entry<k,v> p) {
  linkedhashmap.entry<k,v> last = tail;
  tail = p;
  if (last == null)
    head = p;
  else {
    p.before = last;
    last.after = p;
  }
}

上面代码很简单,但是很清晰的将添加节点到最后的逻辑抽离的出来;

  • 找到key,则替换value,这部分需要联系 hashmap 相关 中的put方法部分;
// hashmap.putval
...
// 如果找到key
if (e != null) { // existing mapping for key
  v oldvalue = e.value;
  if (!onlyifabsent || oldvalue == null)
    e.value = value;
  afternodeaccess(e);
  return oldvalue;
}

// 如果没有找到key
++modcount;
if (++size > threshold)
  resize();
afternodeinsertion(evict);
return null;
...

在之前的hashmap源码分析当中可以看到有几个空的方法

void afternodeaccess(node<k,v> p) { }
void afternodeinsertion(boolean evict) { }
void afternoderemoval(node<k,v> p) { }

这三个就是用来调整链表位置的事件方法,可以看到hashmap.putval中就使用了两个,

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;
  }
}

afternodeaccess可以算是linkedhashmap比较核心的方法了,当访问了一个节点的时候,如果accessorder = true则将节点放到最后,如果accessorder = false则不变;

void afternodeinsertion(boolean evict) { // possibly remove eldest
  linkedhashmap.entry<k,v> first;
  if (evict && (first = head) != null && removeeldestentry(first)) {
    k key = first.key;
    removenode(hash(key), key, null, false, true);
  }
}

protected boolean removeeldestentry(map.entry<k,v> eldest) {
  return false;
}

afternodeinsertion方法是插入节点后是否需要移除最老的节点,这个方法和维护链表无关,但是对于linkedhashmap的用途有很大作用,后天会举例说明;

2. get 方法

public v get(object key) {
  node<k,v> e;
  if ((e = getnode(hash(key), key)) == null)
    return null;
  if (accessorder)
    afternodeaccess(e);
  return e.value;
}

public v getordefault(object key, v defaultvalue) {
 node<k,v> e;
 if ((e = getnode(hash(key), key)) == null)
   return defaultvalue;
 if (accessorder)
   afternodeaccess(e);
 return e.value;
}

get方法主要也是通过afternodeaccess来维护链表位置关系;
以上就是linkedhashmap链表位置关系调整的主要方法了;

3. containsvalue 方法

public boolean containsvalue(object value) {
  for (linkedhashmap.entry<k,v> e = head; e != null; e = e.after) {
    v v = e.value;
    if (v == value || (value != null && value.equals(v)))
      return true;
  }
  return false;
}

可以看到linkedhashmap还重写了containsvalue,在hashmap中寻找value的时候,需要遍历所有节点,他是遍历每个哈希桶,在依次遍历桶中的链表;而在linkedhashmap里面要遍历所有节点的时候,就可以直接通过双向链表进行遍历了;

三、应用

public class cache<k, v> {
  private static final float default_load_factor = 0.75f;
  private final int max_capacity;
  private linkedhashmap<k, v> map;

  public cache(int capacity, boolean accessorder) {
    capacity = (int) math.ceil((max_capacity = capacity) / default_load_factor) + 1;
    map = new linkedhashmap(capacity, default_load_factor, accessorder) {
      @override
      protected boolean removeeldestentry(map.entry eldest) {
        return size() > max_capacity;
      }
    };
  }

  public synchronized void put(k key, v value) {
    map.put(key, value);
  }

  public synchronized v get(k key) {
    return map.get(key);
  }

  @override
  public string tostring() {
    stringbuilder sb = new stringbuilder();
    for (map.entry entry : map.entryset()) {
      sb.append(string.format("%s:%s ", entry.getkey(), entry.getvalue()));
    }
    return sb.tostring();
  }
}

以上是就是一个linkedhashmap的简单应用,

  • accessorder = true时,就是lrucache,
  • accessorder = false时,就是fifocache;
// lrucache
cache<string, string> cache = new cache<>(3, true);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.put("d", "4");
cache.get("c");

system.out.println(cache);

// 打印:b:2 d:4 c:3

// fifocache
cache<string, string> cache = new cache<>(3, false);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.put("d", "4");
cache.get("c");

system.out.println(cache);

// 打印:b:2 c:3 d:4

总结

  • 总体而言linkedhashmap的代码比较简单,但是我觉得里面代码的组织,逻辑的提取等方面特别值得借鉴;