Collection(三)

¶Collection(三)

¶一.概述

接下来了解一下 Collection 的重要实现之一Set 接口，可能听得最多的Set 的实现特点就是不存储重复元素和元素存取无序，接下来会解释那这些是如何实现的.

¶二. Set: 无序集合

先看一下继承关系图
和List 的实现最大的区别是没有新增任何自定义的方法，都是直接从 Collection 接口继承的方法也看不出它的一些特点
现在从最常用的实现 HashSet 开始了解它的实现细节

¶三.HashSet: 存取无序，不可存储重复元素的集合

先看一下继承图
HashSet 实现了 Set 接口，继承了 AbstractSet抽象类
从属性可以猜测一下 HashSet 实现内部元素存储的容器会不会是个 HashMap 映射？

HashSet 类属性和方法：

属性：
- map : HashMap<E,Object> : HashSet 存储内部元素的容器，所有对元素的操作都是类似的一个代理方法实现，没有自己额外的逻辑
- PRESENT : Object [=new Object()] : 和内部的 map 集合中key相关联的虚假值，其实每次存储的都是key，而不是value

方法：

构造方法：

无参构造：
1
2
3
public HashSet() {
map = new HashMap<>();
}
- 简单直白地 new 了一个 HashMap，调用的也是HashMap 的无參构造

Collection 参数构造:

 public HashSet(Collection<? extends E> c) {
     //这个构造有学问，先来看看调用了HashMap 的哪个构造
     map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
     addAll(c);
 }

//HashMap 构造
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//指向了这个构造
//initialCapacity ：初始化容量 ； 
//loadFactor : HashMap 内部存储结构HashTable 的负载因子，表示已经存储的键值对比例，扩容的依据
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    //和允许的最大容量 1<<30 进行对比
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //这里最后调用了 tableSizeFor(initialCapacity)初始化 HashMap 内部容器 hashTable 的容量
    this.threshold = tableSizeFor(initialCapacity);
}

//tableSizeFor(initialCapacity)， 会返回参数cap 最大的2的幂值
static final int tableSizeFor(int cap) {
    //以 7 为例，0111
    int n = cap - 1; // n=6, 0110
    // 把 n 和 n 无符号右移 1 位之后做或运算，
    n |= n >>> 1; //  0110 ^ 0011 = 0111
    // 把 n 和 n 无符号右移 2 位之后做或运算
    n |= n >>> 2; // 0111 ^ 0011 = 0111
    // 把 n 和 n 无符号右移 4 位之后做或运算
    n |= n >>> 4; // 0111 ^ 0000 = 0111,从这里开始或运算已经只返回原值了，因为无符号位移之后低位都是0
    // 把 n 和 n 无符号右移 8 位之后做或运算
    n |= n >>> 8; //0111 ^ 0000 = 0111
    // 把 n 和 n 无符号右移 16 位之后做或运算
    n |= n >>> 16; //0111 ^ 0000 = 0111 = 7
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; //n=8,2^3，刚好是7为基础的2最小幂
}

看到最后，初始化的是一个指定容量的HashMap

指定容量和负载因子的初始化

public HashSet(int initialCapacity, float loadFactor) {
    //和前文一样的初始化方法
    map = new HashMap<>(initialCapacity, loadFactor);
}

包级别私有的构造：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    //实例化的是一个 LinkedHasMap ，也是和之前的构造不一样的地方
    //不过这个方法是包级别私有的，仅供 HashSet 的子类 LinkedHashSet 使用
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

总结:
- 已经可以确定HashSet 内部使用一个 HashMap 来存储元素，而 HashMap 具备Key 唯一的特点，是否是通过key值判断是否存在元素？

主要方法:

add(E e)：

public boolean add(E e) {
    //调用了HashMap 的put 方法来添加元素，是个代理没跑了，确切地说是存储了一个新的key
    //而且map的put方法会进行key排重，存储已有key会不进行任何操作，这也是实现HashSet不存储重复元素
    return map.put(e, PRESENT)==null;
}

//HashMap 的 put 方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//put方法调用的putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //tab赋值为 HashMap 的内部 table对象， n 赋值为 table length ,也就是键值对的数量
    //判断当前的HashMap是否为空
    if ((tab = table) == null || (n = tab.length) == 0)
        //为空的话使用扩容方法初始化一个HashMap
        n = (tab = resize()).length;
    //获取最后一个键值对进行判断是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        //为空的话，将参数hash, key,value 构造为链表的尾节点插入，注意这里是链表结构 
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果存在相同的hash和key 值，不做操作
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //重点来了，如果当前插入的不是链表节点，而是一个红黑树节点
        else if (p instanceof TreeNode)
            //调用红黑树的 putTreeVal()方法进行节点添加，这个方法也留在 HashMap里面了解
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //当链表结构存储了一定数量(TREEIFY_THRESHOLD)的键值对之后，将链表转二叉树存储数据
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表转二叉树，这个方法也留在 HashMap 里面了解
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //插入节点之后，需要检查平衡红黑二叉树结构是否被破坏
            //如果树结构被破坏需要旋转树来重新平衡树，详细留在 HashMap 了解
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        //扩容
        resize();
    //检查树结构是否被破坏以及是否需要需要重新平衡树
    afterNodeInsertion(evict);
    return null;
}

可以看到 add 进去的是 key ，而不是用来充数的 PRESENT 对象

remove(E e)*:

public boolean remove(Object o) {
    // hashMap 的 remove
    return map.remove(o)==PRESENT;
}

contains(Object o):

public boolean contains(Object o) {
    //这里判断是否包含元素使用的 HashMap 的 contaninsKey ，而不是 containsValue 方法
    //因为之前的 add(E e) 方法也只是存储了参数 E e 作为 key ，所以判断是否包含对象是判断key
    return map.containsKey(o);
}
//contaninsKey(o)
public boolean containsKey(Object key) {
    //查询是否存在以key生成的哈希值和key对象
    return getNode(hash(key), key) != null;
}
    
//getNode(int hashCode,Object key)
final Node<K,V> getNode(int hash, Object key) {
    //声明了Node数组，头节点，元素节点e
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        //这句判断通过 下标和hashCode 的与操作，获得该下标的元素判断是否是头节点
        (first = tab[(n - 1) & hash]) != null) {
        //匹配到头节点，判断hashCode并调用equals方法
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //HashMap 在存储了一定的键值对时，会使用 TreeNode 代替LinkedList 结构存储元素
            //这里判断头节点类型
             if (first instanceof TreeNode)
                //如果是TreeNode节点，转型并调用 getTreeNode(hash,key)方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //匹配hashCode和equals方法 
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
                //循环遍历
            } while ((e = e.next) != null);
        }
    }
    return null;
}

//getTreeNode(hash,key)
final TreeNode<K,V> getTreeNode(int h, Object k) {
    //因为 第26行 是从first节点开始查找，所以先判断了 first 是否是根节点，不是就调用 root()方法获得根节点
    //然后从根节点开始调用 find(int h,Object k,Class<?> kc) 查找当前 hashCode 和 key 代表的节点是否存在
    return ((parent != null) ? root() : this).find(h, k, null);
}

//查找红黑树的根节点
final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        // 遍历直到查找到父节点为空的节点，也就是根节点
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

//find(int h,Object k,Class<?> kc)
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    //this 代表调用find 方法的根节点
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        //pl :  p 节点的左子节点 ； pr: p 节点的右子节点
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        //通过hash值判断p节点位于左子树还是右子树
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        //匹配到hash值和key值，返回
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        //在右子树遍历
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            //在左子树遍历
            p = pl;
    } while (p != null);
    return null;
}

就像上面那句解释一样，这是判断key 是否存在，因此在HashMap 中查询了一系列的 hashCode和key 值，来确定是否存在该key

总结：
- 与其说底层是实现是个 HashMap 不如说这就代理模式实现的HashSet 结构，利用 HashMap key 排重的特点，存储不重复的元素
- 至于存取无序，就算直接迭代 HashSet ，返回的是 HashMap.keySet().iterator() ，KeySet 是一个Set集合，是无序的，原因在于存储元素的时候，树的结构是可能发生改变的，父节点，兄弟节点和子节点等都可能以为为了平衡二叉树维持红黑树的特性，而发生改变

¶四.LinkedHashMap: 链表实现的顺序Set 集合

还是先看一下继承关系图:
- 直接继承了HashSet 并实现了 Set 接口，我们记得HashSet 有一个构造 HashSet(int initialCapacity, float loadFactor, boolean dummy) 返回的是 LinkedHashMap ，这个构造就是为 LinkedHashSet 准备的

方法和属性:

属性:
- 只有一个序列化 ID ，没有其他任何属性

方法:

构造: 全都放在一起说，因为都是调用了父类的构造

//指定初始容量和负载因子的初始化
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}
//只指定了初始容量，使用默认的 0.75 作为负载因子
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

//没有指定任何参数，以 2^4 次方作为容量，0.75 作为负载因子
public LinkedHashSet() {
    super(16, .75f, true);
}

//比较参数 Collection 的size*2 和11，取较大的作为初始容量
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}


//调用的父类构造,构造本身具备 default 权限，子类可以调用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

构造方法都是直接super 调用会返回 LInedHashMap 的构造方法，这样会返回一个有序的Map 集，在同样保证了不存储重复元素的情况下，也保证了存储顺序

¶五.总结:

Set 接口没有提供通过下标存取元素的功能，而且从它的两个实现 HashSet 和 LinkedHashSet 中，可以发现HashSet的存取无序是因为，他每次是将元素作为 key 值存储到 HashMap 中，而 Map 的结构又可能是变化的，无法保证有序存储
不存储重复元素是因为 Map 的key 不重复特性，对于 Map 来说，key 是查找元素的依据，因此必须是唯一的