Java面试重点--HashSet底层代码全面解析（2）

蔚落 2024-04-06 12:38 29阅读 0赞

### 上期：[Java面试重点–HashSet底层代码全面解析（1）][Java_HashSet_1] ###

### 上期的例子： ###

import java.util.HashSet;
    
    public class HashSet_ {
        
        public static void main(String[] args) {
        
            HashSet hashSet = new HashSet();
            hashSet.add("jack");
            hashSet.add("tom");
            hashSet.add("jack");
            hashSet.add(null);
            hashSet.add(null);
            System.out.println(hashSet);
        }
    }

加入"tom"的过程与"jack"相同，所以跳过，继续加入"jack"。

### 解析HashSet的底层机制 ###

1、使用Debug进入第三句add：hashSet.add(“jack”);我们得到了下面的代码：  
e就是传入的字符串"jack"，PRESENT是一个常量。

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

2、进入put方法：  
key就是传入的字符串"jack"，value就是PRESENT是一个常量。

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

3、进入putVal方法：  
hash表示 key 对应的 hash 值，key就是传入的字符串"jack"，value就是PRESENT是一个常量。  
因为之前已经添加了两个字符串，table数组不为空，所以第一个if条件不满足，因为"jack"与"jack"的hash值相同，所以在table数组的索引相同，所以p不等于null，所以第二个if条件不满足，进入else，因为"jack"与"jack"的hash值相同且内容相同，所以满足第一个if条件，将p赋给e。

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;
                }
            }

然后直接跳到 if (e != null)，满足条件，进入if语句，执行V oldValue = e.value，因为onlyIfAbsent为false，所以 !onlyIfAbsent 为 true，所以进入if语句，执行 e.value = value，意思是进行了value的替换，但是因为HashSet是单列表，value都是常量，所以看不出替换。 最后一步步返回，添加失败。验证了HashSet不能存放重复的元素。  
4、执行 hashSet.add(null)；  
前面几乎一样，重点计算hash值，key就是null，因为key == null，所以返回0。

static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

返回到put方法，hash(key) = 0。

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

进入putVal方法，hash = 0  
table不为空，第一个if条件不满足，因为hash = 0，所以(n - 1) & hash = 0，i = 0。  
因为tab\[0\] = null，所以满足第二个if条件，所以null被加入到tab\[0\]，所以如果null可以被加入，那么一般存放在数组下标0的位置上。

第二个null，不可加入的原因与上面相同，所以跳过。证明HashSet可以存放null，但是只能存放一个。  
输出的顺序按照数组索引的顺序输出，所以HashSet存放元素的顺序与取出元素的顺序不一致。  
未完待续。。。。。。

[Java_HashSet_1]: https://blog.csdn.net/programmerchiu/article/details/126907825?spm=1001.2014.3001.5501