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

JDK源码分析(9)之 WeakHashMap 相关

程序员文章站 2022-05-23 19:42:12
平时我们使用最多的数据结构肯定是 HashMap,但是在使用的时候我们必须知道每个键值对的生命周期,并且手动清除它;但是如果我们不是很清楚它的生命周期,这时候就比较麻烦;通常有这样几种处理方式: 由一个线程定时处理,可以是 或者 ; 利用重写 ,实现 FIFOCache 或者 LRUCache;可以 ......

平时我们使用最多的数据结构肯定是 hashmap,但是在使用的时候我们必须知道每个键值对的生命周期,并且手动清除它;但是如果我们不是很清楚它的生命周期,这时候就比较麻烦;通常有这样几种处理方式:

  • 由一个线程定时处理,可以是timer或者scheduledthreadpoolexecutor
  • 利用重写linkedhashmap.removeeldestentry(),实现 fifocache 或者 lrucache;可以参考我之前写的一篇博客 linkedhashmap 相关
  • 利用 weakhashmap 的特性,如果逻辑比较复杂还可以直接使用reference;这里可以参考 reference 完全解读reference 框架概览

所以本文将主要介绍weakhashmap的特性,以及补充一些关于 hashmap 实现的对比;相关 hashmap 的介绍也可以参考 hashmap 相关

一、使用场景

上面也介绍了,weakhashmap适用于不是非常重要的缓存类似的场景;例如:

weakhashmap<object, integer> map = new weakhashmap<>();

for (int i = 0; i < 100; i++) {
  map.put(new object(), i);
}

system.out.println(map.size());  // 1
system.gc();                     // 2
system.out.println(map.size());  // 3
system.out.println(map.size());  // 4
system.out.println(map.size());  // 5
system.out.println(map);         // 6
system.out.println(map.size());  // 7

// 打印:
100
100
100
46
{}
0

对于以上的结果你可能和我打印的不一样,weakhashmap按照语义应该是,当 key 没有强引用指向的时候,会自动清除 key 和 value;我这里先解释它的释放过程,如果你觉得很清晰,那weakhashmap你就算是掌握了;

  • 首先 for 循环结束的时候,key 已经没用强引用指向了,此时所有的 key 都是弱引用了;
  • 接下来执行1,因为我这里只有一个方法,新生代还有足够的空间,所以不会触发 gc,所以所有的 key 任然在堆里面,所以打印100;
  • 然后手动触发 gc,虽然system.gc();不一定会立即执行,但是我这里只有一个方法,所以肯定会执行 gc,这里可以打开 gc 日志查看,-verbose:gc;因为 所有的 key 都是弱引用,所以referent被致为 null,同时将 key 注册到 referencequeue中;
  • 在执行 3-7 的时候,按语义 map 应该为空;但是将 key 注册到 referencequeue并非原子性一次完成的,所以这里会打印不同的值,每注册完成一个,在 map 进行操作的时候,就会将其移除;

将上面的代码改成多线程分析思路也是一样的,如果你觉得有不清楚的地方可以查看下文;

二、weakhashmap 源码分析

1. 类定义

public class weakhashmap<k,v> extends abstractmap<k,v> implements map<k,v>

可以看到虽然weakhashmap也是基于哈希表,但是却并非像linkedhashmap一样是继承于hashmap,并且weakhashmap也没有实现cloneable, serializable两个接口,这是因为weakhashmap基于weakreference实现的,弱引用并不建议实现序列化,同时弱引用一般用于不是很重要的缓存,也就没必要实现cloneable, serializable两个接口了;

2. 核心方法

private final referencequeue<object> queue = new referencequeue<>();

private static class entry<k,v> extends weakreference<object> implements map.entry<k,v> {
  v value;
  final int hash;
  entry<k,v> next;

  entry(object key, v value, referencequeue<object> queue, int hash, entry<k,v> next) {
    super(key, queue);
    this.value = value;
    this.hash  = hash;
    this.next  = next;
  }

  public k getkey() { }
  public v getvalue() {
  public v setvalue(v newvalue) {
  public int hashcode() {
  public string tostring() {
}

private void expungestaleentries() {
  for (object x; (x = queue.poll()) != null; ) {
    synchronized (queue) {
      @suppresswarnings("unchecked")
        entry<k,v> e = (entry<k,v>) x;
      int i = indexfor(e.hash, table.length);

      entry<k,v> prev = table[i];
      entry<k,v> p = prev;
      while (p != null) {
        entry<k,v> next = p.next;
        if (p == e) {
          if (prev == e)
            table[i] = next;
          else
            prev.next = next;
          // must not null out e.next;
          // stale entries may be in use by a hashiterator
          e.value = null; // help gc
          size--;
          break;
        }
        prev = p;
        p = next;
      }
    }
  }
}

上面代码所列的referencequeue,entry,expungestaleentries()就是weakhashmap实现的核心了;这里强烈建议要先看 reference 完全解读reference 框架概览 这两篇博客,里面同样的内容我也不会再赘述了;

  • entry<k,v> extends weakreference<object>, 表明所有的节点都是weakreference,而 key 则是 referent;
  • queue,所有 key 使用同一个referencequeue监听器,每当 key 被回收的时候,entry 将会被注册到referencequeue中;
  • expungestaleentries,将注册到referencequeue中的 entry 移除,并将 value 置为 null;weakhashmap的所有操作都先执行expungestaleentries,这样weakhashmap就实现了自动回收不在需要的 key 和 value;

三、性能对比

其实上面的内容就已经将weakhashmap的主要实现讲完了,但是我之前在看hashmap源码的时候,并没有对比 jdk1.7 和 jdk1.8,但是在这里发现其实weakhashmap的实现和 jdk1.7 差不多,所以接下来我将主要对比一下weakhashmaphashmap

1. 容量计算

weakhashmaphashmap中都要求容量是2的幂,因为当容量为2的幂时,使用除留余数法计算哈希桶位置时可以使用hash % length = hash & (length-1)的性质进行优化;

// weakhashmap
int capacity = 1;
while (capacity < initialcapacity)
  capacity <<= 1;

// hashmap
static final int tablesizefor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= maximum_capacity) ? maximum_capacity : n + 1;
}

简单测试可以得到:

initcap = 10 50 100
weakhashmap 30 32 26
hashmap 3 3 3

代码比较简单我就不贴了,从上表也可以看到了tablesizefor不仅高效而且稳定;

2. 哈希计算

// weakhashmap
final int hash(object k) {
  int h = k.hashcode();
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

// hashmap
static final int hash(object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}

两种hash算法都是要避免极端的hashcode(),但是hashmap却更为透彻,因为影响哈希桶位置的只有 hash 的低位(容量2的n次方,n个低位),直接将高位与上低位,使高位 hash 参与位置计算,简洁且高效;

此外还有put方法,但是里面还牵涉红黑树,对于本文就扯得有点远了,所以暂不讲;

总结

  • weakhashmapweakreference的典型应用,在灵活应用weakhashmap之后,如果有更为复杂的逻辑,可以直接使用reference实现;