HashSet底层结构和源码分析_hashset底层数据结构

我在写这篇分享博客的时候，就在想这个HashSet的源码我应该讲解到什么程度呢？这里如果你想了解HashSet深入到最最最底层，像链表如何树化成红黑树的这个过程、为什么减少Hash碰撞要这么写等等这些问题，那只能抱歉了，这篇文章并不适合你。
如果你是个java初学者那么本篇文章可能也不太适合你。
其实作为源码学习的初学者，我们在查看源码时最大的困难不是说不理解底层源码这一行是赋了一个值还是创建了一个变量，而是说我们并不理解为什么它为什么这么写，这么写有什么高深的含义。
可能随着我们开发经验的增长、随着我们对java语言有了更加深入的理解或者说随着我们对设计模式的深入理解在未来的某一天就都明白了

老规矩这里我们先有一个总体的概述，再进行通过案例进行源码分析，以下分析使用的是JDK8

结论

底层结构

HashSet底层其实是一个HashMap，而HashMap是通过数组+链表+红黑树的方式实现的，如下图（示意图）

扩容机制

1. HashSet的底层的底层是HashMap，每当HashMap中的元素数量超过了临界值（阈值），那么数组就会进行扩容，扩容为原先数组长度的二倍；每当数组的大小发生改变，那么就重新计算它的临界值（阈值）。值得注意的是第一次添加时，table数组为null会先设置默认的初始长度为0，然后会先将数组长度扩容到16，最后再计算当前的临界值(threshold)是16*0.75(加载因子loadFactor)=12

2. 在Java8中，如果再次添加一个元素，此时一条链表的元素个数大于TREEIFY_THRESHOLD（默认是8），并且table（就是数组的大小）的大小大于MIN_TREEIFY_CAPACITY（默认是64），就会进行树化（红黑树）注意两个条件必须同时满足。如果数组的长度没达到64，但是链表上的元素个数达到了8个，table数组会继续扩容，长度超过8的链表暂时不会树化。
   注意树化的时候是不会扩容的

源码分析

分析第一次添加元素

第一次添加的案例代码如下

public class HashSetDemo {
    public static void main(String[] args) {
        Set hashSet = new HashSet();
        hashSet.add("a");
    }
}    
1
2
3
4
5
6

HashSet的无参构造源码如下

这证明了HashSet底层其实就是一个HashMap
HashMap的无参构造源码如下

• loadFacotr:负载因子，负载因子用于计算扩容的阈值（可以理解为一个扩容的倍数）
• DEFAULT_LOAD_FACTOR：默认负载因子大小为0.75
  源码如下
  

然后进入HashSet的add()方法，源码如下

这里的map就是实例化HashSet时创建的HashMap，可以看到这里调用了HashMap的put方法

• E e：元素e就是我们调用add方法添加进来的元素，当前案例指的就是字符串a
• PRESENT：因为HashMap是个双列集合，这里使用add方法key是我们新添加的元素，value用一个Object对象占位，所以这个参数其实就是一个占位用的对象，统一都是一个Object对象，不用关注
  

然后进入HashMap的put(K key, V value)方法，源码如下

• hash(key)：用来根据添加的对象计算它的hash值
  
  可以看到这里计算的hash值并不是我们调用hashCode方法获取到的哈希值，这里这么做是为了让后面计算下标的时候分布的更均匀，具体为啥均匀这里就不详细解释了

• key：就是我们添加的对象

• value：前面的那个占位用的Object对象

进入putVal方法该方法源码如下

可以看到这个方法的源码内容很多，这里我们用到什么说什么
最后在放一个该方法的整个有注释的内容

先说我们第一次添加元素会走的源码

• table：注意这个table属性是HashMap底层的那个数组，但是在我们第一次添加元素的时候是null

所以它会进到这个if当中

// 先将table赋值给tab变量，如果tab变量为null或者长度为0，那么会首先进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
1
2
3

• resize()：该方法就是用于对数组进行扩容的方法，源码如下

该扩容方法也很长，同样这里先说用的上的

// 将我们的数组赋值给oldTab
Node<K,V>[] oldTab = table;
// 计算数组的长度，因为我们是第一次添加table是null，
// 所以oldTab也是null，最终oldCap为0，这个oldCap代表的就是旧数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 将旧数组的扩容阈值赋值给oldThr变量
int oldThr = threshold;
// 新的数组长度和阈值大小初始化为0
int newCap, newThr = 0;
// 这里我将永不到的内容用...省略了
if (oldCap > 0) {
    ...
}
else if (oldThr > 0)
    ...
else {               // zero initial threshold signifies using defaults
    // 给新数组赋值为默认初始化的长度DEFAULT_INITIAL_CAPACITY为16
    newCap = DEFAULT_INITIAL_CAPACITY;
    // 计算新的扩容阈值计算的公式为   默认阈值*默认初始化数组的长度
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• DEFAULT_INITIAL_CAPACITY：默认的数组长度为16，源码如下
  
• DEFAULT_LOAD_FACTOR：默认的负载因子为0.75，源码如下
  
  这个就是我们在实例化HashMap时的赋值给loadFacotr的那个负载因子

然后继续分析还做了什么

// 此时我们的新的阈值为12，不为0，所以不会走该if条件
if (newThr == 0) {
    ...
}
// 将新的阈值大小保存在threshold变量中
threshold = newThr;
// 根据新的table长度newCap创建一个Node数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将新的newTab赋值给table，此时我们的table就是一个长度为16的Node类型的数组了
table = newTab;
// 因为我们原来的oldTab没有东西，是null，所以不会走如下内容
if (oldTab != null) {
    ...
}
// 然后返回这个新扩容的数组
return newTab;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

简单总结一下，在添加第一个元素的第一次扩容时候都做了什么事情呢？

1. 首先在创建HashMap的时候默认table这个代表数组的变量默认时null的
2. 所以当我们添加元素的时候由于table为null，需要进行扩容
3. 然后到扩容方法中因为当前的table为null，所以计算出旧的table的长度为0，又因为扩容阈值也是默认也是0，所以我们进入到了对table数组进行第一次扩容的if中，首先初始化了默认的table长度，这个长度是16，此时新的table的长度就是16了
4. 然后通过负载因子*默认table长度这个公式计算出了新的阈值大小
5. 然后根据新的数组的长度创建了一个newTab数组，类型为Node，然后将这个新的数组返回出去

结束之后回到了这里

此时我们的tabl就是我们扩容后的新数组
然后根据我们的hash值计算添加的元素应该存入那个下标中

// 通过(n - 1) & hash]计算出添加的元素应存入的数组中的下标，并判断该下标此时是否为null
// 如果为null说明还没有插入过元素，此时由于我们是第一次添加元素
// 新扩容的数组第一次用到，所以说会进这个if
if ((p = tab[i = (n - 1) & hash]) == null)
	// 根据我们当前要添加的元素key以及它的hash以及它的默认占位用的vlaue
	// 创建一个新的节点然后存入tab[i]
    tab[i] = newNode(hash, key, value, null);
else {
	 ... 
}
// 操作的次数加一
++modCount;
// HashMap中的元素个数size加一，判断添加新的元素后元素的个数是否超过阈值，如果超过就进行扩容
// 显然我们这里是没有超过的
if (++size > threshold)
	resize();
// 空方法什么都没做	
afterNodeInsertion(evict);
// 添加成功然后返回null
return null;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

至此我们添加第一个元素的源码就分析完成了
第一次添加元素时的putVal方法源码带注释

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // tab就是用于存放我们HashMap中的table的变量
    // p就是table数组中下标为新添加的元素的hash值计算出来的对应的值
    // n就是存放table数组的长度的变量
    // i就是存放根据hash计算出来的下标索引的变量
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 第一次添加table默认为null，所以会进入该if
    if ((tab = table) == null || (n = tab.length) == 0)
    	// 对table进行扩容操作，扩容完毕后tab的长度是16
        n = (tab = resize()).length;
    // 计算出新添加的元素应该放入的下标值，判断该下标的值是不是null
    // 这里因为我们是第一次添加，所以一定是null    
    if ((p = tab[i = (n - 1) & hash]) == null)
    	// 使用我们的元素和它的hash值和value这个占位用的参数创建了一个Node节点
    	// 将这个节点放到下标为i的位置
        tab[i] = newNode(hash, key, value, null);
    else {
        ...
    }
    // 操作次数加一
    ++modCount;
    // HashMap中的元素个数加一，然后判断加完一是否超过阈值，如果超过那么就进行扩容
    // 显然这里我们是没有超过的，因为经过第一次扩容后我们的新阈值为12，所以不会进入该if
    if (++size > threshold)
        resize();
    // 一个空的方法，HashMap没有实现这个方法的具体内容    
    afterNodeInsertion(evict);
    // 添加成功返回null
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第一次扩容时源码带注释

final Node<K,V>[] resize() {
	// 使用oldTab变量存放我们原先的数组，因为我们第一次添加元素，所以此时的table为null
    Node<K,V>[] oldTab = table;
    // 计算table的长度，如果table为null，那么长度为0，否则就是它本身的长度
    // 然后将这个长度存放到oldCap变量中
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 将table的阈值存放到oldThr中，因为第一次添加，默认的阈值为0
    int oldThr = threshold;
	// 新的数组长度和阈值大小初始化为0
	int newCap, newThr = 0;
	// 这里我将永不到的内容用...省略了
	if (oldCap > 0) {
	    ...
	}
	else if (oldThr > 0)
	    ...
	else {               // zero initial threshold signifies using defaults
	    // 给新数组赋值为默认初始化的长度DEFAULT_INITIAL_CAPACITY为16
	    newCap = DEFAULT_INITIAL_CAPACITY;
	    // 计算新的扩容阈值计算的公式为   默认阈值*默认初始化数组的长度
	    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
    // 此时我们的新的阈值为12，不为0，所以不会走该if条件
	if (newThr == 0) {
	    ...
	}
	// 将新的阈值大小保存在threshold变量中
	threshold = newThr;
	// 根据新的table长度newCap创建一个Node数组
	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	// 将新的newTab赋值给table，此时我们的table就是一个长度为16的Node类型的数组了
	table = newTab;
	// 因为我们原来的oldTab没有东西，是null，所以不会走如下内容
	if (oldTab != null) {
	    ...
	}
	// 然后返回这个新扩容的数组
	return newTab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

分析第二次添加元素

第二次添加的案例代码如下

public class HashSetDemo {
    public static void main(String[] args) {
        Set hashSet = new HashSet();
        hashSet.add("a");
        hashSet.add("b");
    }
}    
1
2
3
4
5
6
7

我们的debug从第二个添加的元素位置进入add方法

这个add方法就是HashSet调用了HashMap中的put方法put的key为我们HashSet添加的元素，Value为一个占位的Object对象
然后进入到我们的HashMap中的put方法中

进入putVal方法

因为方法比较长我们依旧是用到什么说什么

// 这几个变量前面说过了就不具体说了
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 因为第一次添加过后我们的table数组就不为null了，并且table的长度也不是0
// 所以不会进入该if，省略里面的内容
if ((tab = table) == null || (n = tab.length) == 0)
    ...
// 根据key的hash值计算出当前这个节点应该存放到table数组的哪个索引上
// 如果该索引为null 那么使用当前的hash值、添加的元素key、占位用的value创建一个新的节点并添加    
if ((p = tab[i = (n - 1) & hash]) == null)
	// 对计算出来的索引位置进行赋值
    tab[i] = newNode(hash, key, value, null);
else {
    ...
}
// 操作次数加1
++modCount;
// 先给HashMap中的元素总个数加1，然后判断元素的个数是否超过阈值，如果超过就进行扩容
// 显然没超过，所以不走该if
if (++size > threshold)
    resize();
// HashMap未定义该方法    
afterNodeInsertion(evict);
// 添加成功返回null
return null;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

分析在同一链表上添加元素

案例代码如下

public class HashSetDemo {
    public static void main(String[] args) {
        Set hashSet = new HashSet();
        hashSet.add("a");
        hashSet.add("ab");
    }
}    
1
2
3
4
5
6
7

我们将断点打到添加ab元素的时候
首先进入HashSet的add方法

可以看到此时在table数组的下标为1的地方已经存在了一个节点，这个节点中的key就案例断点位置上一行添加的元素
然后我们进入map的put方法

它会先计算hash值然后传递进putVal方法
我们继续跟如putVal方法

那么此时就到了这个putVal中的else这部分内容了
else中的内容如下

Node<K,V> e; K k;
// 回顾p是啥：p是我们根据新添加的元素的hash值计算出来的下标对应的table中的那个元素
// 这点是去重的逻辑
// 1、table[i]的hash值如果跟当前传入进来的新的这个元素的hash值相同
// 2
//  （1）table[i]中的元素key跟我们的新添加的元素内存地址相同
//	（2）key不为null的前提下当前添加元素的key调用equals方法和table[i]中的key比较
// 满足1条件的同时满足2中的任意一个条件就说明，当前元素是一个重复元素
// 此时将这个p赋值给e，（p是原先HashMap中存在的元素）e是这个上面新创建的变量，用于返回的（因为如果添加重复的元素后需要返回添加失败的这个重复元素）
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
// 如果当前的这个p已经被树化过了，调用红黑树的添加方法添加元素即可
else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 否则说明当前元素能添加进来，并且当前table[i]这个位置的节点还是个链表，不是红黑树    
else {
	// binCount用于记录链表中没添加新的元素前的个数-1，当binCount达到8减1之后需要调用树化的方法，也就是说必须要在添加第9个元素才能进入树化的判断if
    for (int binCount = 0; ; ++binCount) {
    	// 链表添加的基本操作，判断当前节点的下一个是不是null，如果是就添加
        if ((e = p.next) == null) {
        	// 在链表的末端添加一个新的节点
            p.next = newNode(hash, key, value, null);
            // 判断如果链表上的元素个数-1大于等于7那么就调用树化的方法treeifyBin(tab, hash)
            // TREEIFY_THRESHOLD树化的阈值是8
            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;
    }
}
// 判断e是否不为null，如果为不为null说明是遍历链表的过程中遇到了重复的元素了
// 如果为null说明是到了最后才退出的上面的循环
if (e != null) { // existing mapping for key
	// 记录重复的元素
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    // HashMap未实现的空方法    
    afterNodeAccess(e);
    // 返回重复的元素
    return oldValue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

至此整个putVal方法都说过了

总结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;
        
        
        /*
        1、若哈希表的数组tab为空，则通过resize()进行初始化，所以，初始化哈希表的时机就是第1次
        调用put函数时，即调用resize() 初始化创建。
        */
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        /* if分支
        1、根据键值key计算的hash值，计算插入存储的数组索引i
    	2、插入时，需判断是否存在Hash冲突：
    	  2-1、若不存在（即当前table[i] == null），则直接在该数组位置新建节点，插入完毕。
    	  2-2、否则代表发生hash冲突，进入else分支
        */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        
        else {
            Node<K,V> e; K k;
           //判断 table[i]的元素的key是否与需插入的key一样，若相同则直接用新value覆盖旧value
            //【即更新操作】
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            
            //继续判断：需插入的数据结构是否为红黑树or链表。若是红黑树，则直接在树中插入or更新键值对     
            else if (p instanceof TreeNode)
                /*
                1、putTreeVal作用：向红黑树插入 or 更新数据（键值对）
      			2、过程：遍历红黑树判断该节点的key是否与需插入的key是否相同：
           		   2-1、若相同，则新value覆盖旧value
           		   2-2、若不相同，则插入
                */
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            
            //进入到这个分支说明是链表节点
            else {
                /*
                过程：
                1、遍历table[i]，判断Key是否已存在：采用equals()对比当前遍历节点的key 与
                需插入数据的key：若已存在，则直接用新value覆盖旧value
       		   2、遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据(尾插法)
       		   3、新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树
                */
                for (int binCount = 0; ; ++binCount) {
                    //对于2情况的操作  尾插法插入尾部
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //对于3情况的操作
                        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;
                }
            }
            // 对1情况的后续操作：发现key已存在，直接用新value 覆盖 旧value，返回旧value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 插入成功后，判断实际存在的键值对数量size > threshold
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

分析链表长度大于8并且table长度不够64的情况

案例代码如下

public static void main(String[] args) {
        Set hashSet = new HashSet();
        hashSet.add(new A(1));
        hashSet.add(new A(2));
        hashSet.add(new A(3));
        hashSet.add(new A(4));
        hashSet.add(new A(5));
        hashSet.add(new A(6));
        hashSet.add(new A(7));
        hashSet.add(new A(8));
        hashSet.add(new A(9));
        hashSet.add(new A(10));
        hashSet.add(new A(11));
}
// 我通过自定义类的然后重写hashCode的方法固定hash值，让每一次添加元素都添加到一个下标的位置
class A {
    private int n;

    public A(int n) {
        this.n = n;
    }


    @Override
    public int hashCode() {
        return 100;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

将断点打到添加第9个元素的时候，因为是链表的长度大于8才会树化
首先进入到HashSet的add方法

此时的元素个数为8，都在下标为4的位置

将新的元素添加到下标为4的末尾的时候就会达到树化的阈值进入treeifyBin方法，该方法源码如下

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
	// 如果当前的数组为null或者当前的数组的长度小于MIN_TREEIFY_CAPACITY那么就会先进行扩容
	// MIN_TREEIFY_CAPACITY就是table最小的的长度为64
	// 因为当前的数组的长度为16还没达到这个条件，所以进行先进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 如果通过新添加的元素的hash值计算出来的索引位置的元素不为null就进行树化
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        ...树化的过程
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

由此就不用继续分析了，经过第一次扩容后容量从16变为了32，如果下一个元素还是添加到了tbale[4]的位置那么会继续进行树化判断，必须达到了当前链表的长度大于8并且table数组的大小大于64才会进行树化

分析达到threshold阈值后扩容

此时在添加m前的状态为

table数组内的元素数量sizie达到12并且当前阈值也是12，所以当执行完当前这行的添加操作后table数组会进行扩容，注意这里说达到12个不是说数组占用达到阈值才会扩容，时元素个数size

可以看到添加完成后就进行了扩容

---

由此HashSet的底层源码就分析的差不多了，可以发现其实分析HashSet就是再分析HashMap

如有问题欢迎讨论