转载

Java源码系列(12) -- WeakHashMap

一、类签名

WeakHashMap的元素 Entry 继承自WeakReference，当元素没有外部引用被回收，或因虚拟机内存不足而回收，元素会被放入到 queue 。虽然WeakHashMap和HashMap拥有相同父类，但在具体实现上HashMap有更好的优化，和WeakHashMap更相似反倒是HashTable。 

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>

UML:

Java源码系列(12) -- WeakHashMap

二、数据成员

// 默认初始化容量
private static final int DEFAULT_INITIAL_CAPACITY = 16;

// 保存键值对最大容量值
private static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 代表tables里的null_key
private static final Object NULL_KEY = new Object();

// 哈希表，长度必须为2的幂
Entry<K,V>[] table;

// 已保存键值对数量
private int size;

// 扩容阈值：threshold = capacity * load factor
private int threshold;

// 实际负载因子
private final float loadFactor;

//  保存已经清理WeakEntries的引用队列
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

// 修改次数
int modCount;

三、构造方法

public WeakHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load factor: "+
                                           loadFactor);
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    table = newTable(capacity);
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
}

public WeakHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public WeakHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public WeakHashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
            DEFAULT_INITIAL_CAPACITY),
         DEFAULT_LOAD_FACTOR);
    putAll(m);
}

// 构造方法中使用，用于创建Entry数组的方法
@SuppressWarnings("unchecked")
private Entry<K,V>[] newTable(int n) {
    return (Entry<K,V>[]) new Entry<?,?>[n];
}

四、成员方法

// 检查是否为空，为空使用NULL_KEY表示
private static Object maskNull(Object key) {
    return (key == null) ? NULL_KEY : key;
}

// 把NULL_KEY通过null表示
static Object unmaskNull(Object key) {
    return (key == NULL_KEY) ? null : key;
}

// 对象对比
private static boolean eq(Object x, Object y) {
    return x == y || x.equals(y);
}

// 计算key的哈希值
final int hash(Object k) {
    int h = k.hashCode();

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// 根据哈希值和表长度算出索引位置
private static int indexFor(int h, int length) {
    return h & (length-1);
}

// 清理废弃的Entry
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的哈希值选桶

            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; // e是头结点，解除链接
                    else
                        prev.next = next; // e是中间节点，解除链接

                    // 不能把e.next置null，因为废弃的元素可能还在被HashIterator使用
                    e.value = null; // 把e的value置空
                    size--; // 保存元素数量递减
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

// 清理废弃Entry后返回table
private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}

// 清理废弃Entry后返回已保存Entry数量
public int size() {
    if (size == 0)
        return 0;
    expungeStaleEntries();
    return size;
}

// 把所有src表的节点移动到dest表里
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
    // 遍历src表的哈希桶索引
    for (int j = 0; j < src.length; ++j) {
        Entry<K,V> e = src[j]; // 获取哈希桶索引
        src[j] = null; // 把当前处理的链表从src解链接
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            if (key == null) {
                e.next = null;  // 帮助GC
                e.value = null;
                size--;
            } else {
                int i = indexFor(e.hash, dest.length);
                e.next = dest[i]; // 头插法放入dest表中
                dest[i] = e;
            }
            e = next;
        }
    }
}

五、获取

public V get(Object key) {
    Object k = maskNull(key);
    int h = hash(k); // 计算key的哈希值
    Entry<K,V>[] tab = getTable(); // 获取表
    int index = indexFor(h, tab.length); // 获取哈希桶索引
    Entry<K,V> e = tab[index]; // 获取哈希桶
    while (e != null) {
        if (e.hash == h && eq(k, e.get())) // 匹配对应key
            return e.value; // 返回Entry.value
        e = e.next;
    }
    return null;
}

Entry<K,V> getEntry(Object key) {
    Object k = maskNull(key);
    int h = hash(k); // 计算key的哈希值
    Entry<K,V>[] tab = getTable(); // 获取表
    int index = indexFor(h, tab.length); // 获取哈希桶索引
    Entry<K,V> e = tab[index]; // 获取哈希桶
    // 循环查找，直到匹配对应key
    while (e != null && !(e.hash == h && eq(k, e.get())))
        e = e.next;
    return e;
}

六、存入

public V put(K key, V value) {
    Object k = maskNull(key);
    int h = hash(k); // 计算key的哈希值
    Entry<K,V>[] tab = getTable(); // 获取表
    int i = indexFor(h, tab.length); // 计算桶索引
    
    // 依次遍历桶里链表的元素
    for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
        // 匹配到已有Entry
        if (h == e.hash && eq(k, e.get())) {
            // 用newValue替换oldValue
            V oldValue = e.value;
            if (value != oldValue)
                e.value = value;
            return oldValue; // 返回oldValue
        }
    }
    
    // 不存在以后元素，执行下面的逻辑
    modCount++; // 修改次数递增
    Entry<K,V> e = tab[i]; // 获取哈希桶
    tab[i] = new Entry<>(k, value, queue, h, e); // 创建新Entry，通过头插法的方式放入链表
    if (++size >= threshold) // 如果已保存元素数量超过阈值，触发重哈希逻辑
        resize(tab.length * 2);

    return null; // 创建新的Entry会返回null，因为不存在oldValue
}

public void putAll(Map<? extends K, ? extends V> m) {
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == 0)
        return;

    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        
        // 保存键值对数量不能超过最大值
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        if (newCapacity > table.length)
            resize(newCapacity);
    }

    // 递归调用put(K key, V value)
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry<K,V>[] newTable = newTable(newCapacity); // 构建新哈希表
    transfer(oldTable, newTable); // 把旧哈希表的元素放入新哈希表
    table = newTable;

    if (size >= threshold / 2) {
        threshold = (int)(newCapacity * loadFactor);
    } else {
        expungeStaleEntries();
        transfer(newTable, oldTable);
        table = oldTable;
    }
}

七、移除

// 根据key移除Entry
public V remove(Object key) {
    Object k = maskNull(key);
    int h = hash(k); // 用key计算hash
    Entry<K,V>[] tab = getTable();
    int i = indexFor(h, tab.length); // 用计算出来的hash选桶索引
    Entry<K,V> prev = tab[i]; // 用桶索引获取对应哈希桶
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        // 匹配对应key，把Entry从链中移除
        if (h == e.hash && eq(k, e.get())) {
            modCount++; // 修改次数递增
            size--; // 已保存元素数量递减
            if (prev == e)
                tab[i] = next; // 被移除的是链表头节点
            else
                prev.next = next; // 被移除的是表中节点
            return e.value; // 返回被移除节点的value
        }
        prev = e;
        e = next;
    }

    return null; // 没有移除任何节点，返回null
}

boolean removeMapping(Object o) {
    if (!(o instanceof Map.Entry))
        return false;
    Entry<K,V>[] tab = getTable();
    Map.Entry<?,?> entry = (Map.Entry<?,?>)o; // 类型转换
    Object k = maskNull(entry.getKey());
    int h = hash(k); // 用key计算hash
    int i = indexFor(h, tab.length); // 用计算出来的hash选桶索引
    Entry<K,V> prev = tab[i]; // 用桶索引获取对应哈希桶
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        // 匹配对应key，把Entry从链中移除
        if (h == e.hash && e.equals(entry)) {
            modCount++; // 修改次数递增
            size--; // 已保存元素数量递减
            if (prev == e)
                tab[i] = next; // 被移除的是链表头节点
            else
                prev.next = next; // 被移除的是表中节点
            return true; // 移除成功
        }
        prev = e;
        e = next;
    }

    return false; // 没有移除元素
}

// 清除所有键值对
public void clear() {
    // 队列元素全部出队
    while (queue.poll() != null)
        ;

    modCount++; // 修改次数递增
    Arrays.fill(table, null); // 把哈希桶置null
    size = 0; // 以保存元素数量置0

    // 队列元素全部出队
    while (queue.poll() != null)
        ;
}

八、包含

public boolean containsValue(Object value) {
    // 查找的value为null，调用containsNullValue()
    if (value==null)
        return containsNullValue();

    Entry<K,V>[] tab = getTable();

    // 遍历表的所有哈希桶
    for (int i = tab.length; i-- > 0;)
        // 遍历哈希桶中所有Entry
        for (Entry<K,V> e = tab[i]; e != null; e = e.next)
            // 检查该Entry的value是否匹配目标value
            if (value.equals(e.value))
                return true;

    return false; // 所有Entry都没有包含该value
}

// 检查所有Entry是否包含null的value
private boolean containsNullValue() {
    Entry<K,V>[] tab = getTable();

    // 遍历表的所有哈希桶
    for (int i = tab.length; i-- > 0;)
        // 遍历哈希桶中所有Entry
        for (Entry<K,V> e = tab[i]; e != null; e = e.next)
            // 如果发现Entry的存在value为null，返回true
            if (e.value==null)
                return true;
  
    return false; // 没有Entry的value为null
}

九、节点

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

    @SuppressWarnings("unchecked")
    public K getKey() {
        return (K) WeakHashMap.unmaskNull(get());
    }

    public V getValue() {
        return value;
    }

    public V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        K k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            V v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public int hashCode() {
        K k = getKey();
        V v = getValue();
        return Objects.hashCode(k) ^ Objects.hashCode(v);
    }

    public String toString() {
        return getKey() + "=" + getValue();
    }
}

  • 上一篇

    Java源码系列(11) -- LinkedHashMap

原文  https://phantomvk.github.io/2018/07/11/WeakHashMap/
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
Java入门教程 bootstrap3 CSS springboot-demo Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 Struts2教程 MongoDB教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 SpringCloud ANTLR教程 Hive教程 java实例教程 Ant教程 Hazelcast教程 Elastic-Job-Lite XStream教程 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 WebService CXF学习 Hadoop教程 solr教程 JPA教程 ActiveMQ中文指南 Java内存模型 dubbo教程 Linux入门视频教程
近期评论
  1. 1 Spring Boot集成oauth2快速入门demo
  2. 2 Spring Boot集成Spring AI实现快速接入openAI
  3. 3 Spring Boot集成Spring Session快速入门Demo
  4. 4 Spring Boot集成RabbitMQ快速入门Demo
  5. 5 Spring Boot集成Quartz快速入门Demo
  6. 6 Spring Boot集成Mybatis Plus快速入门Demo
  7. 7 Spring Boot集成zipkin快速入门Demo
  8. 8 能用365块大洋去解决的事，千万不要用时间
  9. 9 Spring Boot集成atomikos快速入门Demo
  10. 10 Spring Boot集成fastdfs快速入门Demo
网站信息
  • 文章总数：155,468 篇
  • 文件总数：468,747 个
  • 标签总数：2,269 个
  • 分类总数：90 个
  • 留言数量：2,542 条
  • 在线人数：624 人
  • 运行天数：4,199天
  • 最后更新：2024年04月26日04点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG