Java面试重点–HashSet底层代码全面解析（1）

HashSet底层代码全面解析（1）

介绍HashSet

1.HashSet是Set接口的实现子类。
2.HashSet的底层其实是HashMap。
3.HashSet可以存放null，但是只能存放一个。
4.HashSet存放元素的顺序与取出元素的顺序不一致。
5.HashSet不能存放重复的元素。

举一个实例来证明上面的3，4，5观点

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

输出结果

[null, tom, jack]

先说明HashSet的底层存放元素结论

1、HashSet的底层是HashMap，HashMap的底层是数组+链表+红黑树。
2、添加元素时，先得到其hash值，然后转成索引值。
3、找到存储元素的数组table，看这个索引位置是否有元素。
4、如果没有，就直接加入。
5、如果有就需要调用equals方法，进行比较，如果相同就放弃添加，如果不同就添加到链表的最后。（注意：equals方法可以自己修改，如果加入的是字符串，就按字符串的equals方法比较内容是否相同，如果加入的是自定义对象，未重写equals方法，就按是否是同一对象进行比较）
6、如果其中一条链表的长度达到8，并且table的大小>= 64，数组+链表的结构就会树化，变成红黑树。
7、输出按索引值顺序，所以存放元素的顺序与取出元素的顺序不一致，null索引为0，tom索引为3,jack索引为14。

HashSet的底层示意图

说明HashSet的底层数组扩容结论

1、HashSet的底层是HashMap，第一次添加时table数组扩容至16，临界值（threshold）是16*加载因子（loadfactor）是0.75 = 12。
2、当table数组使用到12时，数组就会扩容2倍，到32，新的临界值就是32 * 0.75 = 24，以此类推。
3、如果其中一条链表的长度达到8，但是table数组的大小未达到64，就会以2为倍数进行数组扩容，直到大小>= 64，数组+链表的结构就会树化，变成红黑树。

解析HashSet的底层机制

疑问

1.为什么HashSet可以存放null，但是只能存放一个？
2.为什么HashSet存放元素的顺序与取出元素的顺序不一致？
3.为什么HashSet不能存放重复的元素，如何判断是否是重复的元素？

解析

1、HashSet的底层其实是HashMap，HashMap的底层是数组+链表+红黑树
使用Debug进入 HashSet hashSet = new HashSet();我们得到了下面的代码：

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

2、HashSet如何存放元素
（1）使用Debug进入 hashSet.add(“jack”);我们得到了下面的代码：
e就是传入的字符串”jack”，PRESENT是一个常量。

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

（2）再次Debug进入put方法：
key就是传入的字符串”jack”，value就是PRESENT是一个常量。

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

（3）hash(key)表示得到 key 对应的 hash 值，ctrl+B进入hash(key)：

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

从代码可以看出，先判断key是否为null，如果是null就返回0，所以上面的案例中null存放在数组下标0的位置，如果不是就调用key的hashCode()方法得到h，h再与无符号右移16位的自己进行异或运算，得到的结果返回hash(key）。
（4）返回put方法，进入putVal方法：
putVal方法很长，接下来分段分析。
hash表示 key 对应的 hash 值，key就是传入的字符串”jack”，value就是PRESENT是一个常量。

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;

table 就是 HashMap 底层数组，类型是 Node[]，因为还没有存放元素，所以是null，满足if条件，执行 n = (tab = resize()).length;
（5）进入resize()方法：
将table赋给oldTab，所以oldTab = null，oldCap = 0，threshold表示临界值为table数组长度的0.75倍，因为table数组长度为0，所以threshold = 0，oldThr = 0，所以会进入到else语句。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
        }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    return newTab;
}

DEFAULT_INITIAL_CAPACITY = 16是一个常量，所以 newCap = 16，表示table数组的新容量=16，DEFAULT_LOAD_FACTOR = 0.75是一个常量，表示加载因子，所以newThr = （int）(16 * 0.75) = 12，所以 threshold = 12，然后新建了一个长度16的Node数组 newTab，所以table就变成了一个长度16的Node数组，返回newTab。
小结：resize()方法是一个数组扩容方法，如果当前 table 是 null, 或者大小=0，就第一次扩容到 16 个空间，如果已经加入的元素占数组空间的0.75倍时，数组就准备扩容。
（6）返回putVal方法：
执行n = (tab = resize()).length; 所以n = 16。
继续执行putVal方法：
因为tab数组没有加入任何元素，p = null，满足if条件，就创建一个 Node (key=“java”,value=PRESENT) ，就放在该位置 tab[i] = newNode(hash, key, value, null)，经过计算 i = 14。说明”jack”这个字符串放在数组下标14的位置。

	if ((p = tab[i = (n - 1) & hash]) == null){
  	  tab[i] = newNode(hash, key, value, null);
    }
	++modCount;
	if (++size > threshold)
    	resize();
	afterNodeInsertion(evict);
	return null;
}