集合_HashSet(HashMap)扩容机制源码简析

先说明一个问题：为什么说分析HashSet实际上是在分析HashMap？

        因为HashSet的构造方法，本质上都是调用HashMap的构造方法，对其内部维护的HashMap对象map进行初始化

    private transient HashMap map;
 
    
    public HashSet() {
        map = new HashMap<>();
    }
 
    
    public HashSet(Collection c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
 
   
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
 
    
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

        众所周知HashMap的存储方式为K-V键值对，而HashSet的存储方式从表面上来看为仅存储key，其原因是HashSet中存在PRESENT属性，该属性为Object类型，其作用为：作为K-V键值对中的value。所以实际上HashSet的存储方式也为K-V键值对，但value恒为PRESENT（通过HashMap实现，必然是存储键值对的）

        在HashMap中，value是可重复的，而key是不可重复的，该特性在HashSet上体现为"元素不可重复"（HashSet添加元素时只要求传入key）

private static final Object PRESENT = new Object();

扩容机制源码简析 

        调用HashSet的add方法，内部调用HashMap的put方法，put方法内部调用putVal方法

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
 
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

        为了可读性，对于代码的解读写在注释中

        关于putVal方法

    //元素重复指的是key重复 即传入的key与链表中的key存在重复 发生重复时将放弃添加
    //若遍历完链表都不存在重复的key 则将key与value作为参数（还有hash和next）创建结点 链接在链表尾结点（1.8之前是链接在头结点）
    //而value是允许重复的 如HashSet中value恒为PRESENT
    //size指的是HashSet(HashMap)集合中的元素个数 而不是集合内部维护的数组存放了元素的索引的个数
        //例如 table.length == 16 只在索引0处存在一个长度为4的链表 其他索引处为空 此时size == 4而不是1
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //定义辅助变量
            // tab指向table
            // n=table.length
            // p最初指向链表的头结点（此次准备添加的元素的hash对应的索引处的链表）
            // i=索引
        //table是HashMap中用于存储数据的数组 类型为Node 即数组中的元素都是链表（若有元素的话）
        HashMap.Node[] tab; HashMap.Node p; int n, i;
 
        //若table == null 或 table.length == 0 则进行第一次扩容（扩容为16）
        //扩容后用n重新记录扩容后的table长度
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //n-1按位与hash（该hash不是hashCode 是hashCode经过按位异或无符号右移十六位的结果）计算得出索引 将该索引对应的链表的头结点赋值给p
        //若n=16 即n=2^4 则(n-1)&hash表示取hash二进制数的后四位 而四位二进制数的表示范围为0-15 覆盖了数组当前的所有索引
        //若p == null 即头结点为空 则代表此处尚未存储元素 将在该索引下创建一个新的结点作为头结点（参数为hash、key、value（PRESENT）、next）
        if ((p = tab[i = (n - 1) & hash]) == null)
            //newNode方法的作用为返回一个新建结点
            tab[i] = newNode(hash, key, value, null);
        //hash对应的索引不为空时 即存在链表时
        else {
            //定义辅助变量
            HashMap.Node e; K k;
            //若头结点的key的hash与准备添加的元素（后简称元素）的key的hash相等（hashCode相等）
            //且头结点的key与元素的key相等或元素的key不为null且头结点的key与元素的key经equals判断相等
            //这边说明一点 虽然p.hash与hash经计算得出的索引相同 但是不能想当然地认为p.hash == hash 因为决定索引的是二者的二进制数的后n位（2^n == 容量）
            //该if语句等价于 重复元素无法添加 除非hash相等且equals判断为true
            //所以hashCode与equals的重写总是成双成对的（设计者设计的规则 或许有其深意 但具体是什么我不清楚）
                //此处举例String类 Sting类重写了hashCode方法与equals方法
                //对于String类而言 两个String对象只要内容相同 则计算得出的hashCode就相同 且equals判断为true 即使这两个对象都是通过new创建的（均不指向字符串常量池）
                //此时对于内容相同的两个String对象 同时符合一、三判断 故新元素不能被添加
                //若此时存在一个类 只重写了hashCode方法或equals方法 该类的两个对象就无法同时通过一、三判断 即可以被添加
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                //将p的引用赋值给e 此时e != null 将走放弃添加的方法
                e = p;
            //判断链表是否为一颗红黑树 若是则调用putTreeVal方法添加元素
            else if (p instanceof TreeNode)
                e = ((HashMap.TreeNode)p).putTreeVal(this, tab, hash, key, value);
            //进行元素添加
            else {
                //遍历链表
                for (int binCount = 0; ; ++binCount) {
                    //若一直遍历至尾结点都未找到相同元素 则进行添加 并break
                    //此时e == null
                    if ((e = p.next) == null) {
                        //newNode方法的作用为返回一个新建结点
                        p.next = newNode(hash, key, value, null);
                        //添加元素时 链表的长度>=8 将进行树化（即添加完元素后 链表长度为9时 将进行树化）
                        //但还需要满足一个条件 table.length >= MIN_TREEIFY_CAPACITY（默认为64） 否则不进行树化 而是进行扩容
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //若遍历时检测到存在相同元素 则放弃添加 并break
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //等价于 p = p.next
                    p = e;
                }
            }
            //若放弃添加 则e必然不等于null（元素重复） 即必然走该方法
            //该方法返回e.value e指向发生元素重复的结点（HashSet通过HashMap实现 其value恒为PRESENT）
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //HashMap中的putVal方法的onlyIfAbsent参数为false 故该判断恒成立
                //即使在HashSet中value != null恒成立（value != null恒成立代表key发生重复即放弃添加）
                //故重复元素中的新元素的value必将覆盖旧元素的value
                    //这代表着什么呢？
                    //HashMap中数据是以键值对的方式存在的
                    //key发生重复时不添加新的结点 但是新元素的value将覆盖旧元素的value
                    //此为"修改" 即修改指定key值对应的结点的value
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //该方法交由HashMap的子类实现 在HashMap中是一个空方法
                afterNodeAccess(e);
                //即使oldValue == null 但也与 return null 是不同的
                return oldValue;
            }
        }
        ++modCount;
        //判断添加该元素时（注意是++size 也就是说size不受此次添加的元素的影响）数组中存储的元素是否已经超越了临界值threshold
        //若超过临界值threshold将进行扩容
        if (++size > threshold)
            resize();
        //该方法交由HashMap的子类实现 在HashMap中是一个空方法
        afterNodeInsertion(evict);
        //返回null代表添加成功
        return null;
    }

         关于扩容函数resize

    //扩容
    //简而言之：数组容量在第一次扩容时将扩容至16 或通过构造函数指定的容量（会经过tableSizeFor方法处理 暂存于临界值threshold） 后续扩容将扩容至先前容量的两倍
    //加载因子DEFAULT_LOAD_FACTOR（默认为0.75） 加载因子可自定义 即通过构造函数为loadFactory赋值 加载因子*容量=临界值
    //临界值会随着数组的扩容而扩容 系数同样为2（大多数情况下）
    //size超过临界值时表示数组需要进行扩容的（size等于临界值时不会）
    @SuppressWarnings("ALL")
    final HashMap.Node[] resize() {
        HashMap.Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //数组存在容量 换言之数组不是初始态数组
        if (oldCap > 0) {
            //若数组容量达到MAXIMUM_CAPACITY 将临界值threshold赋值为Integer.MAX_VALUE 即不再扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //反之则二倍扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //此处标记 后文会用到
        //若数组是初始态数组 但通过构造函数指定了容量（经过tableSizeFor方法处理后暂存于临界值threshold） 则将容量初始化为临界值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //若数组是初始态数组 但未通过构造函数指定临界值 则将数组容量初始化为16 并通过DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY计算临界值
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //以上的情况中 只有走标记处分支的情况下 newThr == 0才会成立
        //该分支用于为临界值threshold赋真正的值做准备（暂存于newThr）
        //若经标记处分支初始化的容量
        //反之将Integer.MAX_VALUE作为新临界值赋值给newThr
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        //将新临界值newThr赋值给临界值变量threshold
        threshold = newThr;
        //开始扩容
        @SuppressWarnings({"rawtypes","unchecked"})
        HashMap.Node[] newTab = (HashMap.Node[])new HashMap.Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof HashMap.TreeNode)
                        ((HashMap.TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        HashMap.Node loHead = null, loTail = null;
                        HashMap.Node hiHead = null, hiTail = null;
                        HashMap.Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

        关于树化函数treeifyBin

    //树化
    final void treeifyBin(HashMap.Node[] tab, int hash) {
        int n, index; HashMap.Node e;
        //table == null 或 table.length < MIN_TREEIFY_CAPACITY（默认为64）时 将先进行扩容 而不是树化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            HashMap.TreeNode hd = null, tl = null;
            do {
                HashMap.TreeNode p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

        关于初始容量处理函数tableSizeFor

        该函数的作用为：返回大于或等于传入的初始容量的最小2的n次方数

        关于tableSizeFor可参照：

        集合_HashMap_tableSizeFor_Mudrock__的博客-CSDN博客

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