【集合框架】JDK1.8源码分析之IdentityHashMap(四)

Java框架

浏览数:256

2019-3-19

AD:资源代下载服务

一、前言

  前面已经分析了HashMap与LinkedHashMap,现在我们来分析不太常用的IdentityHashMap,从它的名字上也可以看出来用于表示唯一的HashMap,仔细分析了其源码,发现其数据结构与HashMap使用的数据结构完全不同,因为在继承关系上面,他们两没有任何关系。下面,进入我们的分析阶段。

二、IdentityHashMap示例  

import java.util.Map;
import java.util.HashMap;
import java.util.IdentityHashMap;

public class IdentityHashMapTest {
    public static void main(String[] args) {
        Map<String, String> hashMaps = new HashMap<String, String>();
        Map<String, String> identityMaps = new IdentityHashMap<String, String>();
        hashMaps.put(new String("aa"), "aa");
        hashMaps.put(new String("aa"), "bb");
        
        identityMaps.put(new String("aa"), "aa");
        identityMaps.put(new String("aa"), "bb");
        
        System.out.println(hashMaps.size() + " : " + hashMaps);
        System.out.println(identityMaps.size() + " : " + identityMaps);
    }
}

  运行结果:

1 : {aa=bb}
2 : {aa=bb, aa=aa}  

说明:IdentityHashMap只有在key完全相等(同一个引用),才会覆盖,而HashMap则不会。

三、IdentityHashMap数据结构

  说明:IdentityHashMap的数据很简单,底层实际就是一个Object数组,在逻辑上需要看成是一个环形的数组,解决冲突的办法是:根据计算得到散列位置,如果发现该位置上已经有元素,则往后查找,直到找到空位置,进行存放,如果没有,直接进行存放。当元素个数达到一定阈值时,Object数组会自动进行扩容处理。

四、IdentityHashMap源码分析

  4.1 类的继承关系 

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable

  说明:继承了AbstractMap抽象类,实现了Map接口,可序列化接口,可克隆接口。

  4.2 类的属性  

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable
{
    // 缺省容量大小
    private static final int DEFAULT_CAPACITY = 32;
    // 最小容量
    private static final int MINIMUM_CAPACITY = 4;
    // 最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 29;
    // 用于存储实际元素的表
    transient Object[] table;
    // 大小
    int size;
    // 对Map进行结构性修改的次数
    transient int modCount;
    // null key所对应的值
    static final Object NULL_KEY = new Object();
}

  说明:可以看到类的底层就是使用了一个Object数组来存放元素。

  4.3 类的构造函数

  1. IdentityHashMap()型构造函数  

public IdentityHashMap() {
    init(DEFAULT_CAPACITY);
}

  2. IdentityHashMap(int)型构造函数

public IdentityHashMap(int expectedMaxSize) {
        if (expectedMaxSize < 0)
            throw new IllegalArgumentException("expectedMaxSize is negative: "
                                               + expectedMaxSize);
        init(capacity(expectedMaxSize));
    }

  3. IdentityHashMap(Map<? extends K, ? extends V>)型构造函数

public IdentityHashMap(Map<? extends K, ? extends V> m) {
        // 调用其他构造函数
        this((int) ((1 + m.size()) * 1.1));
        putAll(m);
    }

  4.4 重要函数分析

  1. capacity函数 

// 此函数返回的值是最小大于expectedMaxSize的2次幂
    private static int capacity(int expectedMaxSize) {
        // assert expectedMaxSize >= 0;
        return
            (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
            (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
            Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
    }

  说明: 此函数返回的值是最小的且大于expectedMaxSize的2次幂的值。

  2. hash函数 

// hash函数,由于length总是为2的n次幂,所以 & (length - 1)相当于对length取模
    private static int hash(Object x, int length) {
        int h = System.identityHashCode(x);
        // Multiply by -127, and left-shift to use least bit as part of hash
        return ((h << 1) - (h << 8)) & (length - 1);
    }

  说明:hash函数用于散列,并且保证元素的散列值会在数组偶次索引。

  3. get函数 

public V get(Object key) {
        // 保证null的key会转化为Object(NULL_KEY)
        Object k = maskNull(key);
        // 保存table
        Object[] tab = table;
        int len = tab.length;
        // 得到key的散列位置
        int i = hash(k, len);
        // 遍历table,解决散列冲突的办法是若冲突,则往后寻找空闲区域
        while (true) {
            Object item = tab[i];
            // 判断是否相等(地址是否相等)
            if (item == k)
                // 地址相等,即完全相等的两个对象
                return (V) tab[i + 1];
            // 对应散列位置的元素为空,则返回空
            if (item == null)
                return null;
            // 取下一个Key索引
            i = nextKeyIndex(i, len);
        }
    }

  说明:该函数比较key值是否完全相同(对象类型则是否为同一个引用,基本类型则是否内容相等)

  4. nextKeyIndex函数 

// 下一个Key索引
    private static int nextKeyIndex(int i, int len) {
        // 往后移两个单位
        return (i + 2 < len ? i + 2 : 0);
    }

  说明:此函数用于发生冲突时,取下一个位置进行判断。

  5. put函数  

public V put(K key, V value) {
        // 保证null的key会转化为Object(NULL_KEY)
        final Object k = maskNull(key);

        retryAfterResize: for (;;) {
            final Object[] tab = table;
            final int len = tab.length;
            int i = hash(k, len);

            for (Object item; (item = tab[i]) != null;
                 i = nextKeyIndex(i, len)) {
                if (item == k) { // 经过hash计算的项与key相等
                    @SuppressWarnings("unchecked")
                        // 取得值
                        V oldValue = (V) tab[i + 1];
                    // 将value存入
                    tab[i + 1] = value;
                    // 返回旧值
                    return oldValue;
                }
            }
            
            // 大小加1
            final int s = size + 1;
            // Use optimized form of 3 * s.
            // Next capacity is len, 2 * current capacity.
            // 如果3 * size大于length,则会进行扩容操作
            if (s + (s << 1) > len && resize(len))
                // 扩容后重新计算元素的值,寻找合适的位置进行存放
                continue retryAfterResize;
            // 结构性修改加1
            modCount++;
            // 存放key与value
            tab[i] = k;
            tab[i + 1] = value;
            // 更新size
            size = s;
            return null;
        }
    }

  说明:若传入的key在表中已经存在了(强调:是同一个引用),则会用新值代替旧值并返回旧值;如果元素个数达到阈值,则扩容,然后再寻找合适的位置存放key和value。

  6. resize函数 

private boolean resize(int newCapacity) {
        // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
        int newLength = newCapacity * 2;
        // 保存原来的table
        Object[] oldTable = table;
        int oldLength = oldTable.length;
        // 旧表是否为最大容量的2倍
        if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
            // 之前元素个数为最大容量,抛出异常
            if (size == MAXIMUM_CAPACITY - 1)
                throw new IllegalStateException("Capacity exhausted.");
            return false;
        }
        // 旧表长度大于新表长度,返回false
        if (oldLength >= newLength)
            return false;
        // 生成新表
        Object[] newTable = new Object[newLength];
        // 将旧表中的所有元素重新hash到新表中
        for (int j = 0; j < oldLength; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                Object value = oldTable[j+1];
                oldTable[j] = null;
                oldTable[j+1] = null;
                int i = hash(key, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = key;
                newTable[i + 1] = value;
            }
        }
        // 新表赋值给table
        table = newTable;
        return true;
    }

  说明:当表中元素达到阈值时,会进行扩容处理,扩容后会旧表中的元素重新hash到新表中。

  7. remove函数  

public V remove(Object key) {
        // 保证null的key会转化为Object(NULL_KEY)
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        // 计算hash值
        int i = hash(k, len);

        while (true) {
            Object item = tab[i];
            // 找到key相等的项
            if (item == k) {
                modCount++;
                size--;
                @SuppressWarnings("unchecked")
                    V oldValue = (V) tab[i + 1];
                tab[i + 1] = null;
                tab[i] = null;
                // 删除后需要进行后续处理,把之前由于冲突往后挪的元素移到前面来
                closeDeletion(i);
                return oldValue;
            }
            // 该项为空
            if (item == null)
                return null;
            // 下一项
            i = nextKeyIndex(i, len);
        }
    }

  8. closeDeletion函数 

private void closeDeletion(int d) {
        // Adapted from Knuth Section 6.4 Algorithm R
        Object[] tab = table;
        int len = tab.length;

        // Look for items to swap into newly vacated slot
        // starting at index immediately following deletion,
        // and continuing until a null slot is seen, indicating
        // the end of a run of possibly-colliding keys.
        Object item;
        // 把该元素后面符合移动规定的元素往前面移动
        for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
             i = nextKeyIndex(i, len) ) {
            // The following test triggers if the item at slot i (which
            // hashes to be at slot r) should take the spot vacated by d.
            // If so, we swap it in, and then continue with d now at the
            // newly vacated i.  This process will terminate when we hit
            // the null slot at the end of this run.
            // The test is messy because we are using a circular table.
            int r = hash(item, len);
            if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
                tab[d] = item;
                tab[d + 1] = tab[i + 1];
                tab[i] = null;
                tab[i + 1] = null;
                d = i;
            }
        }
    }

  说明:在删除一个元素后会进行一次closeDeletion处理,重新分配元素的位置。

  下图表示在closeDeletion前和closeDeletion后的示意图

  

  说明:假设:其中,(”aa” -> “aa”)经过hash后在第0项,(“bb” -> “bb”)经过hash后也应该在0项,发生冲突,往后移到第2项,(“cc” -> “cc”)经过hash后在第2项,发生冲突,往后面移动到第4项,(“gg” -> “gg”)经过hash在第2项,发生冲突,往后移动到第6项,(“dd” -> “dd”)在第8项,(“ee” -> “ee”)在第12项。当删除(“bb” -> “bb”)后,进行处理后的元素布局如右图所示。

五、总结

  IdentityHashMap与HashMap在数据结构上很不相同,并且处理hash冲突的方法也不相同。其中,IdentityHashMap只有当key为同一个引用时才认为是相同的,而HashMap还包括equals相等,即内容相同。

集合框架源码分析框架目录如下

PS:如果您觉得阅读本文对您有帮助,请点一下“推荐”按钮,您的“推荐”,将会是我不竭的动力!

作者:leesf    掌控之中,才会成功;掌控之外,注定失败。

出处:http://www.cnblogs.com/leesf456/

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。


如果觉得本文对您有帮助,您可以请我喝杯咖啡!