`

java.uitl.WeakHashMap

阅读更多
在上篇文章中我提到过java.lang.ref.Reference类,这个东西有点用。
http://wangxinchun.iteye.com/blog/1954187
今天我就介绍下jdk中关于这块的一个应用:WeakHashMap,一个永不满的hashmap,一个和垃圾回收器相依相偎的缓存Map。

先看一个例子:
package com.qunar.flight.tts.policy.client.validator.impl;

import java.util.WeakHashMap;

public class Test {
	public static void main(String[] args) throws Exception {
		WeakHashMap<byte[][], byte[][]> map = new WeakHashMap<byte[][], byte[][]>();
		for (int i = 0; i < 10000000; i++) {
			map.put(new byte[1000][1000], new byte[1000][1000]);
			System.err.println(map.size());
		}
	}
}

在这个例子中,无限分配1M的内存,并存入WeakHashMap,程序运行多久都不会内存溢出。
要问原理,请参看链接:
http://wangxinchun.iteye.com/blog/1954187
本文重点关注WeakHashMap的实现。
介绍:
首先,WeakHashMap 是一个map,具有map的一般实现。
其次,它很大程度上实现和HashMap极为相似。负载因子,Entry数组,默认大小等等。
独特处是 它的实现依赖了 ReferenceQueue 和 WeakReference,这也是WeakHashMap  和HashMap的特性差异所依赖的底层技术。

下面简单分析下WeakHashMap 的部分源码,和HashMap相似的请查看
http://wangxinchun.iteye.com/blog/1872356

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

    /**
     * 默认Map内的Entry数字的默认大小
     */
    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;

    /**
    map所依赖的底层数组,业界文章多称之概念为:桶
     */
    private Entry[] table;

    /**
     * 现有的记录数量
     */
    private int size;

    /**
     * 下一次resize 增长的值(capacity * load factor)
     */
    private int threshold;

    /**
     * 负载因子
     */
    private final float loadFactor;

    /**
     * Reference queue for cleared WeakEntries
     这个queue主要用于保存被垃圾回收器回收后的key对应的引用
     */
    private final ReferenceQueue<K> queue = new ReferenceQueue<K>();

    /**
     * 详细 请查看ConcurrentHashMap  的分析。
     */
    private volatile 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 = new Entry[capacity];
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
    }
    
    public WeakHashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
             DEFAULT_LOAD_FACTOR);
        putAll(m);
    }


    /**
     * 用来代替key = null的 记录的key
     */
    private static final Object NULL_KEY = new Object();

    /**
     * 把null转为 NULL_KEY
     */
    private static Object maskNull(Object key) {
        return (key == null ? NULL_KEY : key);
    }

    /**
     *maskNull 的反模式
     */
    private static <K> K unmaskNull(Object key) {
        return (K) (key == NULL_KEY ? null : key);
    }

    /**
     * Checks for equality of non-null reference x and possibly-null y.  By
     * default uses Object.equals.
     */
    static boolean eq(Object x, Object y) {
        return x == y || x.equals(y);
    }

    /**
     * 定位h所在桶的位置
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

    /**
     * 清理陈旧的Entry,这个方法很早很重要,也是WeakHashMap实现的核心方法之一
     */
    private void expungeStaleEntries() {
	      Entry<K,V> e;
        while ( (e = (Entry<K,V>) queue.poll()) != null) { //queue.poll() 能取出的对象都是被垃圾回收器回收过的,while循环可以保证清理掉所有被回收过的对象
            int h = e.hash;
            int i = indexFor(h, 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) { //一直找到一个对象,是 queue.poll(),准备对其进行回收
                    if (prev == e) //此种情况:只有e出现在了桶的第一个位置
                        table[i] = next;
                    else //如果没有出现在桶的第一个位置,那么要保证e.prev.next=e.next ,这个很重要!否则回去丢失数据
                        prev.next = next;
                    e.next = null;  // Help GC 让当前e对象不要引用e.next,让GC回收
                    e.value = null; //  清理value值
                    size--; //数量也要减1
                    break;退出
                }
                prev = p; //记录上一个
                p = next; //继续寻找等于queue.poll() 的Entry对象
            }
        }
    }

    /**
     * 每次获取桶会清理已经被垃圾回收器回收的数据
     */
    private Entry[] getTable() {
        expungeStaleEntries();
        return table;
    }

    /**
     * 每次取size之前会清理已经被垃圾回收器回收的数据
     */
    public int size() {
        if (size == 0)
            return 0;
        expungeStaleEntries();
        return size;
    }

    /
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 获取一个对象,和普通的HashMap没有区别
     */
    public V get(Object key) {
        Object k = maskNull(key); //如果key =null,需要做特殊处理。
        int h = HashMap.hash(k.hashCode());
        Entry[] 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())) //注意:e.get() 返回的引用的值,如果值已经失效,那么e.get() 返回null。这也是不能使用Null为key的原因!!!
                return e.value;
            e = e.next;
        }
        return null;
    }

   
    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

    /**
     同get 方法
     */
    Entry<K,V> getEntry(Object key) {
        Object k = maskNull(key);
        int h = HashMap.hash(k.hashCode());
        Entry[] tab = getTable();
        int index = indexFor(h, tab.length);
        Entry<K,V> e = tab[index];
        while (e != null && !(e.hash == h && eq(k, e.get())))
            e = e.next;
        return e;
    }

 
 /** 添加记录*/
    public V put(K key, V value) {
        K k = (K) maskNull(key); // null ->NULL_KEY 的转换
        int h = HashMap.hash(k.hashCode());
        Entry[] tab = getTable();
        int i = indexFor(h, tab.length);

        for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
            if (h == e.hash && eq(k, e.get())) { //如果已经存在的处理
                V oldValue = e.value;
                if (value != oldValue)
                    e.value = value;
                return oldValue;
            }
        }

        modCount++; //结构改变标志
	      Entry<K,V> e = tab[i];
        tab[i] = new Entry<K,V>(k, value, queue, h, e); //注意:queue:如果k失效,那么会添加以key为值的WeakReference到queue ,h:key的hash值
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }

    /**
    扩容 (和hashmap 没有区别)
     */
    void resize(int newCapacity) {
        Entry[] oldTable = getTable();
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(oldTable, newTable);
        table = newTable;

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

    /** 扩容的时候,数据的处理 */
    private void transfer(Entry[] src, Entry[] dest) {
        for (int j = 0; j < src.length; ++j) {
            Entry<K,V> e = src[j];
            src[j] = null;
            while (e != null) {
                Entry<K,V> next = e.next;
                Object key = e.get(); 
                if (key == null) { //扩容的时候,发现了key 已经被垃圾回收器回收,那么做引用的处理。
                    e.next = null;  // 解除引用,help GC
                    e.value = null; //  值情况
                    size--;
                } else { //依然有效
                    int i = indexFor(e.hash, dest.length);
                    e.next = dest[i];
                    dest[i] = e;
                }
                e = next;
            }
        }
    }

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

        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }

   /**删除一个记录
   */
    public V remove(Object key) {
        Object k = maskNull(key);
        int h = HashMap.hash(k.hashCode());
        Entry[] tab = getTable();
        int i = indexFor(h, tab.length);
        Entry<K,V> prev = tab[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            if (h == e.hash && eq(k, e.get())) { //如果存在
                modCount++; //结构变化标志
                size--; 
                if (prev == e) //如果出现在表头
                    tab[i] = next;
                else //如果没有出现在表头
                    prev.next = next;
                return e.value;
            }
            prev = e; //循环桶进入下一轮寻找key
            e = next;
        }

        return null;
    }



    /** Special version of remove needed by Entry set 
     同上
    */
    Entry<K,V> removeMapping(Object o) {
        if (!(o instanceof Map.Entry))
            return null;
        Entry[] tab = getTable();
        Map.Entry entry = (Map.Entry)o;
        Object k = maskNull(entry.getKey());
        int h = HashMap.hash(k.hashCode());
        int i = indexFor(h, tab.length);
        Entry<K,V> prev = tab[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            if (h == e.hash && e.equals(entry)) {
                modCount++;
                size--;
                if (prev == e)
                    tab[i] = next;
                else
                    prev.next = next;
                return e;
            }
            prev = e;
            e = next;
        }

        return null;
    }

    /**
     * 清空
     */
    public void clear() {
        // 先清理已经被垃圾回收器处理过的记录
        while (queue.poll() != null)
            ;

        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
        size = 0;

        //再次处理被垃圾回收器处理过的记录
        while (queue.poll() != null)
            ;
    }

    /**
     *是否包含
     */
    public boolean containsValue(Object value) {
			if (value==null)
		            return containsNullValue();
		
			Entry[] tab = getTable();
		        for (int i = tab.length ; i-- > 0 ;)
		            for (Entry e = tab[i] ; e != null ; e = e.next) //e != null ,但是e.value 可能被回收过的。
		                if (value.equals(e.value))
		                    return true;
			return false;
    }

    /**
    同上
     */
    private boolean containsNullValue() {
	   Entry[] tab = getTable();
        for (int i = tab.length ; i-- > 0 ;)
            for (Entry e = tab[i] ; e != null ; e = e.next)
                if (e.value==null)
                    return true;
	return false;
    }

    /**
     * Entry继承了WeakReference,
     */
    private static class Entry<K,V> extends WeakReference<K> implements Map.Entry<K,V> {
        private V value;
        private final int hash; //这个值用在 Map.put 方法里面,判断key是否一致。
        private Entry<K,V> next;

        /**
         * Creates new entry.
         */
        Entry(K key, V value,
	      ReferenceQueue<K> queue,
              int hash, Entry<K,V> next) {
            super(key, queue); //这里指定了queue 来跟踪key的被垃圾回收器回收的时机
            this.value = value;
            this.hash  = hash; //entry的hash 是 key的hash值
            this.next  = next;
        }

        public K getKey() {
            return WeakHashMap.<K>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;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) { //key相等
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2))) //并且值相等
                    return true;
            }
            return false;
        }

        public int hashCode() {
            Object k = getKey();
            Object v = getValue();
            return  ((k==null ? 0 : k.hashCode()) ^
                     (v==null ? 0 : v.hashCode()));
        }

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


以上是我的分析,如有错误,请指正~
分享到:
评论

相关推荐

    观察者模式示例代码 android studio kotlin代码 基于java.uitl.*

    在Java的`java.util.Observable`类中,被观察者对象可以存储多个观察者,并在状态变化时调用它们的`update()`方法。`Observer`接口则定义了观察者应实现的方法,以便在接收到被观察者的通知时执行相应的操作。 在...

    java各种获取日期Uitl

    本篇文章将详细探讨如何使用Java的内置类`java.util.Date`,`java.text.SimpleDateFormat`,以及Java 8引入的`java.time`包来获取各种格式的日期。 首先,我们从`java.util.Date`开始,它是Java中最基本的日期类。...

    毕设项目:基于Javamail的邮件收发系统的设计与实现(系统+文档+开题报告+答辩PPT).zip

    Javamail API使邮件的发送与接收得到大大的简化。本文所开发的邮件客户端程序是在Eclipse 环境下实现的。...其文件名为smtpPop3.properties,位于工程的根目录下,可使用java.uitl. Properties 类的s

    HttpRequestUitl.java

    java http post raw 和 params 发送 博客介绍 https://blog.csdn.net/weixin_42749765/article/details/98472582

    网络时间类

    可以测试,将本地时间任意修改,再运行com.uitl.Date类,若联网时间就会是北京时间,否则就是电脑时间。 父类java.util.Date 也就是Date能用的地方他一样不含糊,从别的地方对Date没有任何修改,这个做服务器的开发...

    jsp防止跨域提交数据的具体实现

    代码如下: //ArgsIsValidFilter .java过滤器代码清单: package com.hety.uitl; import java.io.IOException; import java.util.Enumeration; import javax.servlet.Filter; import javax.servlet.FilterChain; ...

    jsp防止跨域提交数据的具体实现.docx

    package com.hety.uitl; import java.io.IOException; import java.util.Enumeration; import javax.servlet.Filter; import javax.servlet.FilterChain; import javax.servlet.FilterConfig; import javax....

    ibatis uitl

    在这个场景中,"uitl" 可能是指 iBATIS 的辅助工具或实用程序,可能是为了提高开发效率或者提供一些额外的功能。 在描述中提到的博客链接 "https://antlove.iteye.com/blog/1929065" 可能提供了更深入的解释,但...

    各种数据库的链接(JDBC)

    package uitl; // 定义包名 import java.sql.Connection; import java.sql.DriverManager; public class Dat { // 类名 public static Connection getConnection() { Connection conn = null; try { // 注册...

    JAVA做的图片浏览GUI源代码

    &lt;br&gt;其类有: &lt;br&gt;PicBrowseFrame.class 图片浏览器的主窗体 &lt;br&gt;ImageFilter.class 图片过滤 &lt;br&gt;FileNameFIlter.class 文件过滤 &lt;br&gt;Uitl.class 文件名后缀解析 &lt;br&gt;JFileChooserCre.class ...

    可以写到uitl里很好用的过滤

    根据给定的文件信息,我们可以总结出以下IT相关的知识点,主要围绕着Java编程语言中的实用工具类(Utility Class)设计与实现。 ### 1. Utility Class 设计原则 在Java中,工具类(Utility Class)通常用于封装一...

    DWZ 富客户端框架使用手册.pdf

    - **dwz.uitl.date.js**:日期处理工具函数。 - **dwz.regional.zh.js**:中文语言包。 - **dwz.validate.method.js**:重复列出,应该是某个特定版本的验证方法集。 #### 常见问题及解决办法 - **Error loading ...

    Node.js常用工具之util模块

    uitl.inherits(constructor,superConstructor)是一个实现对象间圆形继承的函数。JavaScript的面相对象特性是基于原型的,与常见的基于类的不同。JavaScript没有提供对象继承的语言级别特性,而是通过原型复制来实现...

    DWZ富客户端框架,使用教程

    - **dwz.uitl.date.js**:日期处理工具。 - **dwz.regional.zh.js**:区域设置(中文)。 - **dwz.validate.method.js**:验证方法库。 #### 四、优化与维护 - **Javascript混淆与压缩**:为了减小文件大小,...

    DWZ使用帮助文档

    - **dwz.uitl.date.js**: 日期工具函数。 - **dwz.regional.zh.js**: 地区化设置。 #### Javascript混淆和压缩 - **Javascript混淆**: 通过混淆工具将源码转换为难以阅读的形式,以提高代码的安全性和性能。 - **...

    基于SpringBoot和Vue的保险系统源码+sql数据库+项目说明(毕设项目).zip

    【项目说明】 1.项目代码均经过功能验证ok,确保稳定可靠运行...​ 该项目使用了OSS实现了文件管理,首先在uitl文件夹内的OSSUtils.java文件夹设置好您的oss信息,接下来找到application.yml文件夹修改为您的数据库配置

    软件资源管理下载系统全新带勋章功能 + Uniapp前端

    App个人主页随机背景图,在前端uitl文件夹里面的第一个js里面替换随机背景图api即可显示 前端 搭建好后台 在前端找到 util 这个文件 把两个js文件上面的填上自己的域名 以及在common文件夹找到config.js替换你的域名...

    edac-utils-开源

    Linux内核EDAC驱动程序的用户空间助手

Global site tag (gtag.js) - Google Analytics