集合框架（三）-专用set和map机制分析

-----------------------------------------------------------------------------------------------------------------------
弱散列映射表WeakHashMap


该类的设计是为了解决在map中一个元素没有外部引用却在map的生命周期内总不被回收的bug。

public V put(K key, V value) {
        K k = (K) maskNull(key);//如果key为空，就new一个Object对象作为key
//调用HashMap的hash()方法处理经过hashcode()(自定义或者用java类库的)计算过的哈码
        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) {
	//在要插入元素和i位置的元素的hash code相等情况下，还要保证原来在这个位置的元素e没有被自己写的program或者GC收掉的情况下，才用要插入的value替换原来位置的value，并返回原来位置的value
            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];
	//我们会发现本类的内部组织数据的节点类Entry<K,V>继承了WeakReference<K>，而这个类继承了Reference<T>类。构造Entry<K,V>的时候一路super过去，最终我将key和queue变成了Reference中定义的两个属性referent(泛型T)和queue( 类型ReferenceQueue<? super T>)。而我们传进去的key是要插入的键，queue是WeakHashMap的一个属性queue（类型ReferenceQueue<? super T>）。
	一句话，我们将key和WeakHashMap中的queue属性绑定在reference类中，由ReferenceQueue管理。我们发现WeakHashMap中的Entry根本不保存key值。
	这时候，我们在回过头去看getTable()方法，当在expungeStaleEntries()方法中调用queue.poll()方法的时候我们已经用queue定义的规则来对外部对象引用不到和只有WeakReference对象获得的对象实施回收（sun.misc.VM.addFinalRefCount(-1);）。里面判断是否该回收的机制过于复杂，现在我还没看懂。
        tab[i] = new Entry<K,V>(k, value, queue, h, e);
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
	}
//正如API文档里说的，先清理staleEntries(暂时译为陈旧的条目)，然后返回作为本类的属性Entry[] table
private Entry[] getTable() {
        expungeStaleEntries();
        return table;
	    }
//正如这个方法的名字，它可以删除一些stale的条目。
private void expungeStaleEntries() {
	Entry<K,V> e;
	//'queue'是存储将被清除的ReferenceQueue<K>类型的属性
        while ( (e = (Entry<K,V>) queue.poll()) != null) {
            int h = e.hash;
	//调用一个本类定义的方法获得hash code对应的index
	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) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    e.next = null;  // Help GC
                    e.value = null; //  "   "
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
	}

确实是一个挺有意思的类。虽然里面的机制很复杂，不过作为使用者的我们，我认为只要用的时候知道用WeakHashMap这个类创建对象可以自动回收没有任何引用的元素就行了。


-----------------------------------------------------------------------------------------------------------------------
链接散列集和链接散列映射表
包括LinkedHashMap和LinkedHashSet两个类。


同样是很有意思的一个类，它能克服一般散列表的缺点，记住我们插入元素的顺序。你可以获得key或value的符合插入顺序的迭代器。
下面，一起来看看LinkedHashMap是如何实现的：
本类就继承自HashMap<K,V>。
put()方法直接使用HashMap的，都没覆写。
不过put()方法的内部属性和方法如果LinkedHashMap有覆写，照样是用的LinkedHashMap的。

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
	//这一步会调用LinkedHashMap中的方法，将新元素插进双向链表的末尾。
	并且判断removeEldestEntry()返回的值，为ture的话，就删除hear.after位置的额节点
        addEntry(hash, key, value, i);
        return null;
    }
get()方法字节重写了：
 public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);//调用了字节覆写的内部类Entry的方法
        return e.value;
    }
void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {//如果带顺序的方法定义为true（for access-order）
                lm.modCount++;
                remove();//在原来的链表位置移除该元素
                addBefore(lm.header);//传进去的参数是LinkedHashMap的一个属性，表示双向链表的头部，将我们调用get方法的那个元素重新插入到双向链表的尾部。
            }
        }
默认情况下，LinkedHashMap的判断是否可以按插入顺序排序的属性accessOrder为false，如果你想实现按插入迭代，用这个迭代器：
//accessOrder传入true值
public LinkedHashMap(int initialCapacity,
			 float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
	}


我们发现LinkedHashMap的属性从头到尾都没有实例化啊，到底是在哪里实例化的呢？
void init() {
        header = new Entry<K,V>(-1, null, null, null);
        header.before = header.after = header;
	}

原来自动实例化了。
如果你put一个新的元素的话，会加在链表的header.before位置（可以成为the doubly linked list的尾部）。
所以，如果你想实现一个每插进一个新的元素就删除一个（给定你自己的判断标准，对eldest元素进行评估），可以自定义removeEldestEntry()方法，让它返回true。
这个类可以应用在需要不断的从内存中读取数据，可以自己定义标准把常用的数据存在内存中，不常用的存在数据库中。嘿嘿~~

-----------------------------------------------------------------------------------------------------------------------
枚举集和枚举映射表EnumSet和EnumMap


简单说，枚举类型A就是枚举类只有有限个A的实例对象的属性。
设置枚举类getXxx()有三种方式：
在实现类中定义属性(可定义多个)
让实现类继承一个接口
在实现类中定义抽象方法
这样可以获得枚举类型A的更多绑定值。

EnumMap<K extends Enum<K>, V>:
//A是我自定义的一个枚举类型
//实际上如RED("红色");这样的书写形式，是在编译器里定义了一个类似静态工厂类的机制。如果只有"RED"就会直接将RED这个String值赋给name属性，然后通过name()方法可获取；不过如果你想定义多个属性只要在A中加入很多属性，然后写一个构造器可以传入所有的参数即可，这样你就可以通过自己的getXxx()函数来获取参数的值了。
enum A{
		RED("红色");
		private String name;
		private A(String name){
			this.name=name;
		}
//实例化EnumMap并插入一个枚举类型的为key的pair
java.util.EnumMap<A, String> em=new java.util.EnumMap<A, String>(A.class);
		em.put(A.RED, "");

public V put(K key, V value) {
        typeCheck(key);//检查key类型是否合适

        int index = ((Enum)key).ordinal();
        Object oldValue = vals[index];
        vals[index] = maskNull(value);//用新value替代原来位置的value
        if (oldValue == null)
            size++;
        return unmaskNull(oldValue);//返回原来index位置的元素
	}
看到这里，大家应该明白了，EnumMap通过ordinal()返回的值来确定插入的pair在数组vals中的位置，而vals中只存value。


EnumSet<E extends Enum<E>>：
//设置一个枚举类型到其中
public static <E extends Enum<E>> EnumSet<E> of(E e) {
	//创建一个可以接收指定类型的空集合
        EnumSet<E> result = noneOf(e.getDeclaringClass());
        result.add(e);
        return result;
	}
//在执行这一步的时候，如果universe.length <= 64就会new一个RegularEnumSet类型的对象，最终调用RegularEnumSet中覆写的add(E e)方法将e添加进去。
universe[k]位置的元素的Bit vector为2^k.如果elements的2^k位二进制的值为1，则代表通过逆方法获得的ordinal值对应的对象e在set中，否则不在。另一个类型JumboEnumSet也类似，通过一个elements[]来判断是否在set中。
 public boolean add(E e) {
        typeCheck(e);//检查类型

        long oldElements = elements;
        elements |= (1L << ((Enum)e).ordinal());
        return elements != oldElements;
    }

我们会发现所有的value都缓存在本类属性Enum[] universe中，所有的一开始就缓存在这里面了，至于如何判断是否一个e在set中，可以通过EnumSet的子类JumboEnumSet或RegularEnumSet的属性elements来判断，详细分析见上一端源码里的注释。
我们发现，枚举集和枚举映射表是通过不同的机制来存储元素的。
一切为了应用：看到这里，大家应该发现一个东东——枚举集不就是特定类型的常量集嘛！对，就是这么简单。如果我们试图获取一组特定类型的常量可以使用枚举集和枚举映射对它们进行管理。


-----------------------------------------------------------------------------------------------------------------------
弱标识散列映射表IdentityHashMap


到底IdentityHashMap和HahsMap有什么区别呢？我们一起来深入源码看看。

//插入新的pair的方法
public V put(K key, V value) {
        Object k = maskNull(key);//如果key为null做相应调整
        Object[] tab = table;//Object[]类型的属性
        int len = tab.length;
	//这一步不同于hashmap中自定义的hashcode()方法，而是调用System.identityHashCode(x)获得hashcode，这也是Object调用hashcode()方法时执行的，是根据内存地址来计算的。
        int i = hash(k, len);

        Object item;
        while ( (item = tab[i]) != null) {
            if (item == k) {//使用"=="来比较而不是equals()方法
		V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;//将value放在i+1的索引位置，这里不同于HashMap的包装成Entry
                return oldValue;
            }
            i = nextKeyIndex(i, len);//如果i索引位置的key和原来的额key地址不同，就是所谓冲突了，就向后移两位（因为table中是i位置存key，i+1位置存value），最后遍历到table的末尾还是没有成功插入，就将i变为0，将pair插在0位置
        }

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        return null;
	}

源码里的注释说的很清晰了。

评论

2 楼 aabcc 2010-11-30  

建议把 一和二的链接也附上...方便阅读

支持分享。

1 楼 181054867 2010-11-30  

上传一下源码，在这里看代码是一种折磨！