Set集合的用法及源码解析

Posted on 2022-04-23 Edited on 2023-09-04 In Collection Views: Waline: Word count in article: 13k

前言

本章内容为Java集合中的Set集合的常见用法和源码解析~

Set接口和常用方法
HashSet全面说明
1. 思考
2. HashSet底层解析
3. HashSet底层添加元素源码分析
4. HashSet扩容机制和转换红黑树机制源码解析
5. threshold补充说明
LinkedHashSet说明及源码分析
1. LinkedHashSet全面说明
2. LinkedHashSet底层机制示意图
3. LinkedHashSet底层源码分析

Set接口和常用方法

Set接口基本介绍
1. 无序（添加和取出的顺序不一致），没有索引
2. 不允许重复元素，所以最多包含一个null
3. JDK API中Set接口常用的实现类有：HashSet、TreeSet等
Set接口的常用方法
- 和List接口一样，Set接口也是Collection的子接口，因此，常用方法和Collection接口一样。（详情见Java集合类(一)）

以Set接口的实现类HashSet来讲解Set接口的方法

package com.conllection_.sets;

import java.util.HashSet;
import java.util.Set;

public class SetMethod {
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add("john");
        set.add("jack");
        set.add("tom");
        set.add("john");
        set.add(null);
        set.add(null);
        System.out.println("set = " + set);
    }
}

运行结果：

结论：

set接口的实现类的对象（set接口对象），不能存放重复的元素，可以添加null
set接口对象存放数据是无序（即添加的顺序和取出的顺序不一致）
取出的顺序虽然不是添加的属性，但是顺序是固定的！

Set接口的遍历方式

同Collection的便利方式一样，因为Set接口是Collection接口的子接口。

使用迭代器

System.out.println("===迭代器遍历===");
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
    Object next =  iterator.next();
    System.out.println("set = "+next);
}

增强for

System.out.println("增强for遍历");
for (Object o: set) {
    System.out.println("set = "+o);
}

不能使用索引的方式来获取

HashSet全面说明

HashSet实现了Set接口

HashSet实际上是HashMap

1
2
3

public HashSet() {
    map = new HashMap<>();
}

可以存放null值，但是只能有一个
HashSet不保证元素是有序的，取决于hash后，再确定索引的结果（即不保证存放元素的顺序与取出顺序一致）

不能有重复元素或对象

package com.conllection_.sets;

import java.util.HashSet;
import java.util.Set;

public class HashSet01 {
    public static void main(String[] args) {
        Set hashSet = new HashSet();
        /*说明
        * 1. 在执行add方法后，会返回一个Boolean值
        * 2. 如果添加成功，返回true，否则返回false
        * 3. 可以通过remove指定删除哪个对象
        * */
        System.out.println(hashSet.add("mary"));//T
        System.out.println(hashSet.add("mary"));//F

        hashSet.add("jack");//可以添加
        hashSet.add("jack");//添加失败
        //由于下面每一次add都新建了一个Dog对象
        //所以下面两个Dog对象都会添加成功
        hashSet.add(new Dog("tom"));
        hashSet.add(new Dog("tom"));
        System.out.println("HashSet = "+ hashSet);
        hashSet.remove("mary");//删除mary

        System.out.println("HashSet = "+ hashSet);
    }
}

思考

下面两个String对象都会被添加到HashSet集合里面去吗？
1
2
hashSet.add(new String("czh"));
hashSet.add(new String("czh"));
运行的结果是仅有一个数据被添加，为什么呢？
1
2
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
因为此时String类型重写的equals()方法是比较其字符串内容是否相同，所以此时添加的两个“czh”数据只有一个能被添加进去。

而上述Dog对象的添加原理也是类似。

下面我们通过解读HashSet的底层结构解决这个问题！

HashSet底层解析

因为HashSet的底层是HashMap，所以分析HashMap底层是（数组+链表+红黑树）即可

为了更好理解HashMap的底层，下面模拟一个简单的数组+链表结构

创建Node结点

//结点Node，item存储数据，next指向下一个结点，可以形成链表
class Node{
    Object item;
    Node next;

    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }
}

创建HashSetStructure类

package com.conllection_.sets;

public class HashSetStructure {
    public static void main(String[] args) {
        //1. 创建一个类型为Node的数组
        Node[] nodes = new Node[16];
        //2. 创建结点
        Node john = new Node("john", null);
        nodes[2] = john;
        Node jack = new Node("jack", null);
        john.next = jack;
        Node mary = new Node("mary", null);
        jack.next = mary;

        Node lucy = new Node("lucy", null);
        nodes[3] = lucy;

        System.out.println("node = "+nodes);

    }
}

运行结果：

HashSet底层添加元素源码分析

分析HashSet添加元素的底层是如何实现的（hash()+equals()）
1. HashSet底层就是HashMap
2. 添加一个元素时，先通过hash()得到hash值，然后转换成索引值
3. 找到存储数据表table，看这个索引位置是否已经存放了元素
  1. 如果没有，直接添加
  2. 如果有元素，调用equals比较，如果元素内容相同，就放弃添加，如果不相同，则添加到最后
4. 在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）。
5. 当元素个数到达TREEIFY_THRESHOLD但table的大小小于MIN_TREEIFY_CAPACITY(默认64)时，系统会把table表填扩容到64，然后进行树化。

HashSet添加元素的源码解读

创建HashSetSource类，用于debug

package com.conllection_.sets;

import java.util.HashSet;
import java.util.Set;

public class HashSetSource {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("jack");
        hashSet.add("tom");
        hashSet.add("jack");

        System.out.println("set = " + hashSet);
    }
}

执行构造器
1
2
3
public HashSet() {
map = new HashMap<>();
}
可以清晰地知道HashSet的底层就是HashMap

执行add()方法

1
2
3

public boolean add(E e) {//e="jack"
    return map.put(e, PRESENT)==null;
}

PRESENT是hashSet为了能使用hashMap而定义的一个常量（定值），无论添加了多少的元素它都不会变化

1	private static final Object PRESENT = new Object();

执行put()方法

1
2
3

public V put(K key, V value) {//key = "jack"
    return putVal(hash(key), key, value, false, true);
}

value为PRESENT,是共享的。

执行hash方法，计算key的hash值
1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果key != null，程序会执行Object类中的hashCode()方法来获取key的值，并将它进行无符号右移16位（为了防止key的hashCode值发生冲突），最后得到的h为key对应的hash值。

hash值并不是hashCode，因为(h = key.hashCode()) ^ (h >>> 16)

获取到hash值后，执行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;//定义了辅助变量
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        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)
            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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        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;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

在此方法中，因为辅助变量tab的初始值为null，所以进入到resize()方法，给tab表赋予初始大小。

1
2
3

if ((tab = table) == null || (n = tab.length) == 0){
    n = (tab = resize()).length;
}

上述代码中的table为hashMap的一个属性，类型为Node[]

因为初始的table为null，所以执行resize()方法

//下面代码为resize()方法的一些初始赋值
Node<K,V>[] oldTab = table;//结点oleTab表示原先的表
//oldCap表示初始表的容量大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr为当前表的一个临界值，当达到临界值时会扩容
int oldThr = threshold;
int newCap, newThr = 0;

因为初始的table为null，所以oldCap为0，所以进入到下述语句

else {        // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

DEFAULT_INITIAL_CAPACITY为hashMap定义的常量，大小为16

1	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

所以newCap= 16，即第一次扩容大小为16

newThr为表的一个临界值，是使用负载因子DEFAULT_LOAD_FACTOR乘以初始大小等到的一个值。

默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

使用newThr是为了减少冲突，增加一个缓冲区，避免在多线程向表中增加数据时，表的内存不够而导致死锁。

初始化tap的大小之后，会判断**(p = tab[i = (n - 1) & hash])**是否为null，(n - 1) & hash是位运算，详解见HashMap数学原理。计算出来的i为该key值在table表中的索引位置。

1
2
3

if ((p = tab[i = (n - 1) & hash]) == null){
    tab[i] = newNode(hash, key, value, null);
}

如果p=null，表示还没有存放元素，执行**tab[i] = newNode(hash, key, value, null);**创建一个Node（key=“jack”,value=PRESENT）把hash也放进Node是为了下次添加元素时比较。

执行完毕，此时我们可以发现此时table表中已经在刚刚计算出来的索引值上添加了“jack”。

到此为止，HashMap的第一次添加元素分析完毕。

当我们向HashMap集合表再次添加数据时，系统会计算其hash值，然后通过

1
2
3

if ((p = tab[i = (n - 1) & hash]) == null){
    tab[i] = newNode(hash, key, value, null);
}

方法判断该hash值对应的索引位置上是否已经存在值，如果不存在，即把新增的key添加到表中的该索引位置上。

此时可以发现，table表上多了一个数据

如果该hash值对应的索引位置上已经存在值，程序会跳到下面语句

//p为当前索引位置上对应的链表的第一个元素，即已经添加的值
//所以p.hash为已存在值得hash值，p.key为已存在值得key值
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k)))){
    e = p;
    }

如果当前索引位置上对应的链表的第一个元素的hash值与需要添加的key的hash值一样

且满足以下两个条件之一：

准备添加的key值与p指向的Node结点的key是同一个对象
p指向的Node结点的key的equals()和准备假如的key比较后相同。

需要注意的是，此时equals()方法不能理解为只比较字符串内容是否相同，因为每一个类都会有其对应的equals()方法，所以equals()方法的比较内容可以由程序员所重写的方法来决定！

此时说明新增加的key值已存在，所以该key值不会被添加到table中。

若不满足上述条件，程序会继续往下走，执行下面语句。

1
2
3

else if (p instanceof TreeNode){
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}

上述语句会判断p是否为红黑树，如果是红黑树，就调用putTreeVal进行添加。

如果p不是红黑树，执行以下代码

else {
    for (int binCount = 0; ; ++binCount) {
        //这是条件1
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        //这是条件2
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

因为在可以执行上述代码时，说明此时table表中是使用链表的方式来存储数据 。

此时进入一个死循环，退出的条件：

条件1：在要加入的位置i = (n - 1) & hash处所形成的链表没有一个结点与要加入的结点相同时，退出循环，此时就加在最末尾。添加成功
条件2 :在要加入的位置i = (n - 1) & hash处所形成的链表有结点与要加入的结点相同，此时退出循环，添加失败

两个条件结合起来使用

需要注意的是当我们把元素添加到聊表后，会进行以下判断

1
2
3

if (binCount >= TREEIFY_THRESHOLD - 1){ // -1 for 1st
	treeifyBin(tab, hash);
}

判断链表是否已经达到8个结点（TREEIFY_THRESHOLD=8）。如果到达，则调用treeifyBin(tab, hash)方法对当前链表进行树化（转换成红黑树）。

注意，在转换成红黑树时，treeifyBin(tab, hash)方法会进行判断

1
2
3

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY){
    resize();
}

判断table表大小是否<64，如果小于64，会先将table表进行扩容，再进行树化。

HashSet扩容机制和转换红黑树机制源码解析

HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）=16*负载因子（loadFactor）0.75 = 12
如果数组使用到了临界值12，就会扩容到16*2=32，新的临界值就是 32 * 0.75 = 24，依次类推

在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化（转换红黑树），否则任然采用数组扩容机制

创建测试类HashSetIncrement.java

package com.conllection_.sets;

import java.util.HashSet;
import java.util.Objects;

public class HashSetIncrement {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();

        for (int i = 1; i <=12; i++) {
            hashSet.add(new A(i));
        }
        System.out.println("hashSet = "+ hashSet);
    }
}

Class A

class A {
    private int n ;

    public A(int n) {
        this.n = n;
    }
    
    @Override
    public int hashCode() {
        return 100;
    }
}

在HashSetIncrement类中的for循环处加一个断点，debug。可以发现，当i=9时，即满足一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，此时触发转换红黑树机制。

但是此时不满足table表大小>=64

1
2
3

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY){
    resize();
}

所以此时table表会进行扩容。

继续执行，可以发现table再次扩容。

再继续执行，可以发现此时链表已经发生树化（转换成红黑树）

树化过程的源码

else if ((e = tab[index = (n - 1) & hash]) != null) {
    TreeNode<K,V> hd = null, tl = null;
    do {
        TreeNode<K,V> 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);
}

详细解释见Jdk1.8集合框架之HashMap源码解析

threshold补充说明

在putVal方法中，有这么一行代码

++modCount;
if (++size > threshold){
    resize();
}
afterNodeInsertion(evict);

modCount代表我们对table表修改的次数。

其中size是每当我们加入一个结点Node(key,value,hash,next)，size++。

所以当我们想table表中加入指定数量的Node结点是，也会触发扩容机制。

代码演示HashSetIncrement类

package com.conllection_.sets;

import java.util.HashSet;
import java.util.Objects;

public class HashSetIncrement {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();

        for (int i = 1; i <=7; i++) {
            hashSet.add(new A(i));
        }
        for (int i = 1; i <=7; i++) {
            hashSet.add(new B(i));
        }
        System.out.println("hashSet = "+ hashSet);
    }
}

Class A 与 Class B

class B {
    private int n ;

    public B(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 200;
    }
}
class A {
    private int n ;

    public A(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 100;
    }
}

运行调试，可以发现，虽然我们在一条链表上增加了7个元素，然后第二条链表增加到第五个元素时size=12，也触发了扩容机制

所以触发扩容机制的前提是累积添加元素到达threshold。

LinkedHashSet说明及源码分析

LinkedHashSet全面说明

LinkedHashSet是HashSet的子类。
LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表。
LinkedHashSet根据元素的HashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是一插入顺序保存的。
LinkedHashSet不允许添加重复元素。

LinkedHashSet底层机制示意图

示意图
双向链表具体机制与LinkedList底层结构类似。

LinkedHashSet底层源码分析

说明

在LInkedHashSet中维护了一个hash表和双向链表（LinkedHashSet有head和tail）
每个节点有before和after属性，这样可以形成双向链表
在添加一个元素时，先求hash值，再求索引。确定该元素在hashtable的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加；原则跟hashset一样）

所以，我们遍历LinkedHash可以确定插入顺序和取出顺序一致

创建LinkedHashSetSource类，用于分析源码

package com.conllection_.sets;

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetSource {
    public static void main(String[] args) {
        Set set = new LinkedHashSet();

        set.add(new String("AA"));
        set.add(456);
        set.add(456);
        set.add(123);
        set.add("czh");

        System.out.println("LinkedHashSet = " + set);
    }
}

可以知道，添加第一次时，系统会将数组table扩容到16，存放的结点类型是LinkedHashMap$Entry

为什么数组时HashMap$Node[]类型，而存放的元素/数据却是LinkedHashMap$Entry呢？

下面我们查看LinkedHashMap底层源码来解决这个问题。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

我们可以发现上面这个在LinkedHashMap源码中的静态内部类Entry继承了HashMap.Node。即数组的多态。双向链表实现的关键也是在这里。

继续往下调试

此时的map与hashSet的不一样，多了几个属性。其中head表示双向链表中的头结点，tail表示尾结点。

而每一个结点又有before与after属性，指向上一个结点与下一个结点。

所以LinkedHashSet可以实现按顺序插入及取出。

进入add()方法

1
2
3

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以知道LinkedHashSet添加元素底层就是HashSet添加元素的底层（因为LinkedHashSet是HashSet的实现子类）