hashSet解析

什么是Set？

我们都知道，Set是一个接口，实现的也是Collection接口。也可以说Set是一个集合，与List不同的是，Set集合不允许数据重复，并且数据是无序的。

什么是HashSet？

hashSet是Set接口的典型实现类，我们使用Set集合的时候大多数情况下都是使用这个实现。它底层也是通过hash算法来实现数据存取的。

源码

创建

通过构造函数进去可以直接看到，HashSet底层就是一个HashMap数据结构，那么不用说了，肯定是数组+链表(红黑树)的结构。

• 初始容量16
• 扩容因子0.75
• 单个链表长度超过8则转为红黑树
  

添加数据

与Hash流程基本一致，先取出当前数据的hashCode，通过hashCode计算出该存储的位置。因为已经重写了hashCode，所以可以保证相同的数据得到的hashCode相等，也就是存储位置相等。在对比改存储位置上链表中的其他元素，如果有相等的数据则不需要添加了。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
		//key表示当前需要添加的 元素
		
        Node<K,V>[] tab; 
        Node<K,V> p; //表示链表中的 头节点
        int n, i;
       
        if ((tab = table) == null || (n = tab.length) == 0)
        	// 若 表为null或 表长为0,对表 进行初始化或扩容
            n = (tab = resize()).length;
            
        //&为异或符号，两个相应位相同,结果为0,否则为1。
        //判断当前索引下数组中是否为空（是否含有有链表）
        if ((p = tab[i = (n - 1) & hash]) == null)
        	///若当前索引下为空，则将存放 该元素的节点作为 链表头
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; 
            K k;
            
         //比较头节点p的hash值 与需要添加元素key的hash值，若哈希值相同则不能将元素添加到链表尾
         //比较头节点的元素值是否等于key
         //若添加的元素为对象时，比较的是哈希值，这里产生一个问题（见特别注意），需要重写equals，否则就会造成可以添加相同的对象，与Set的性质冲突。
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                
                //这里e ！= null,会直接跳转到最后if (e != null) 
                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);
                        
                        //若binCount >= 7,将链表进行树化
                        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;
            }
        }
        //记录 HashSet的修改次数
        ++modCount;
        //判断是否需要扩容
        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

移除元素

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //判断表中是否有所要删除的元素
        //直接根据哈希值索引到元素p = tab[index = (n - 1) & hash]
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            
            Node<K,V> node = null, e; 
            K k; 
            V v;
            
            //比较 哈希值等 条件是否满足
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将表中所要删除的元素赋予node
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    //while循环遍历到链表尾节点
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))){
                // 判断是否已经树化，若树化则在树中删除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                	//直接将node的下一个节点存入
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        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