HashSet添加元素源码分析

妖狐艹你老母 2022-10-16 13:26 175阅读 0赞

HashSet 其实底层还是用到的hashMap，讲hashset，其实本质就是在讲HashMap。

在执行HashSet（）时，会走HashSet的构造方法，详细步骤如下

1.执行hashSet()

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

2.执行add（）

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

PRESENT  其实就是为value 占位，在代码中表示为下图，就算这个map执行多少次，key是发生变化的，value始终不变。

![image.png][]

3.执行put（）

采用hash扰动算法，让key得到更多的值，减少碰撞。

public V put(K key,V value){  //该方法会执行hash(key) 得到key对应的hash值，算法h=key.hashCode())^(h>>>16)
    return putVal(hash(key),key,value,false,true);
        }

4.执行putVal（）

方法详解

![image.png][image.png 1]

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;   //定义了辅助变量
        //table就是HashMap的一个数组，类型是Node[]
        //if语句表示如果当前table是null，或者大小=0；
        //就是第一次扩容，到16个空间
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
        //(1)根据key，得到hash，去计算该key应该存放在到table表的那个索引位置.并且把这个位置的对象，赋给p
        //(2)判断p是否为null
        //(2.1)如果p为null，表示还没有存放元素，就创建要给Node
        //(2.2)就放在该位置 tab[i] = newNode(hash, key, value, null)
        //就不能加入
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                //一个开发技巧提示：在需要局部变量（辅助变量）的时候，再创建
                Node<K,V> e; K k;
                //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，
                //并且满足 下面两个条件之一：
                //(1)准备加入的key和p指向Node结点的key是同一个对象
                //(2)p指向的Node结点的key的equals()和准备加入的key比较后相同。
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //再判断p是不是一颗红黑树，
                //如果是一个颗红黑树，就调用putTreeVal,来添加
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {//如果table对应的索引位置，已经是一个链表，就是用for循环比较，
                    //(1)依此和该链表的每一个元素比较后，都不相同，则加入到该链表的最后
                    //注意：在把元素加入到链表后，都不相同，则加入到该链表的最后就调用treeifyBin(),对当前这个链表就行树化（转成红黑树）
                    //注意：在转成红黑树时，要进行判断，判断条件
                    // if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                    //如果上面条件成立，先table扩容
                    //只有上面条件不成立时，才进行转红黑树
                    //(2)依次和该链表的每一个元素比较过程中，如果有相同的情况，就直接break
                    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;
                        }
                        //遍历链表，看链表中是否存在hash和key与要插入进来的元素相同，如果相同，跳出循环。
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break; 
                        // 跟 e = p.next 组成用来遍历链表。
                        p = e;
                    }
                }
                //存在key值和hash值相等的，直接覆盖旧value
                if (e != null) { // existing mapping for key
                    //取出e的value
                    V oldValue = e.value;
                    //onlyIfAbsent  如果当前位置已存在一个值，是否替换，false是替换，true是不替换
                    if (!onlyIfAbsent || oldValue == null)
                        //覆盖
                        e.value = value;
                    //访问后回调
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
        //将记录修改次数加1，判断是否需要扩容，如果需要就扩容
            ++modCount;
            if (++size > threshold)
                resize();
        //插入后回调
            afterNodeInsertion(evict);
            return null;
        }

最后附上一张思维导图，按照自己理解画的，不对地方请见谅，指出相互学习，不胜感激。

![未命名文件.png][.png]

[image.png]: /images/20221014/cda3e88c93c24e29bd0be740d2725df6.png
[image.png 1]: /images/20221014/a173fc3d67cf4575ba1626e2e1008ff2.png
[.png]: /images/20221014/c70a2487d1e8481b9786e1f3552bd094.png