【Java 集合】这次真的从0到1彻底吃透HashSet底层实现源码！

0、HashSet 简介

HashSet 是 Java 集合 Set 的一个实现类，Set 是一个接口，其实现类除 HashSet 之外，还有 TreeSet，并继承了 Collection，HashSet 集合很常用，同时也是程序员面试时经常会被问到的知识点，下面是结构图：

HashSet是Set接口的典型实现，HashSet按照Hash算法来存储集合中的元素。存在以下特点：

• 不能保证元素的顺序，元素是无序的

• HashSet不是同步的，需要外部保持线程之间的同步问题

• 集合元素值允许为null

1、HashSet底层数据结构

通过观察源代码可以看到HashSet底层是基于HashMap实现的，在JDK1.8之后，HashMap底层数据结构是基于数组+链表+红黑树实现的。

1. 特点

• 既保存了数组查询和修改元素效率快的优点，也保存了链表在添加和删除元素时效率快的特点。

• 存储的元素是无序的，不允许重复的，存储的元素最多只能有一个为null值，这是因为HashSet底层存储元素时只是利用了HashMap的key来存储元素，而HashMap的value都是存储的 一个new Object() 对象。所以说HashSet只是利用了HashMap的key，并没有利用HashMap的value。

2. 底层结构图

因为HashSet底层是使用的HashMap，所以下图实际上是HashMap的底层数据结构。当存储一个元素时，首先会给这个元素计算一个hash值。然后根据计算出来的hash值决定将元素存储到哈希表中的那个位置。

3. 优点

• 存取效率高，可以动态扩容

4. 缺点

• 每次存储新的元素都需要计算一次hashCode值，如果计算hash值的算法设计的不好，哈希碰撞产生过多，就可能造成一个节点小存储了多个元素，而哈希表中相邻的元素的位置没有存储任何元素。

• HashSet线程不安全，在多线程情况下会出现线程安全问题。

5.适用场景

• 需要存储不重复的值，要求存取效率高，适合在单线程情况下使用。

• 如果需要在多线程情况下使用，需要使用Collections集合工具类，创建一个线程安全的HashSet集合

   Set<Integer> hashSet = Collections.synchronizedSet(new HashSet<Integer>())

2、底层源码分析

0.成员变量

// 序列化相关，Java序列化的机制是通过判断类的serialVersionUID来验证的版本一致的
static final long serialVersionUID = -5024744406713321676L;

// 底层使用HashMap来保存HashSet中所有元素。 
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。 
private static final Object PRESENT = new Object();

1.构造方法

// 无参构造方法，完成map的创建
// 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75
public HashSet() {
    map = new HashMap<>();
}
// 指定集合转化为HashSet, 完成map的创建
// 实际底层使用默认的加载因子0.75和足以包含指定collection中所有元素的初始容量来创建一个HashMap。
public HashSet(Collection<? extends E> c) {
   map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
   addAll(c);
}
// 指定初始化大小，和负载因子
// 实际底层以相应的参数构造一个空的HashMap。
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
// 指定初始化大小
// 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
// 指定初始化大小和负载因子，dummy 无实际意义
// 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 
// 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

2.添加元素原理分析

示例源码

public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add(2);
        set.add("java");
        set.add("php");
        set.add("java");
        System.out.println("set=" + set);
    }

初始化HashSet

HashSet set = new HashSet();执行后，会自动调用HashSet 的无参构造方法。

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

调用add() 方法

在每次添加数据时，如果数据是基本数据类型，会先将基本数据类型进行装箱操作，把基本数据类型转换成对应的包装类型（引用数据类型）

/**
 * 将基本数据类转换为引用数据类型
 * @param  i 	传入的参数为一个基本型数据类型
 * @return 		返回的参数是一个基本数据类型的包装类（引用数据类型）
 */
public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

如果是引用数据类型的话会直接去调用HashSet的add()方法，源码如下：

/**
 * HashSet的添加方法
 * @param  i 	传入需要添加的元素
 * @return 		添加成功返回true，失败返回false
 */
public boolean add(E e) {
    // 直接调用已经创建好的HashMap集合，调用HashMap中的put()方法进行添加，key为元素值，value为常量对象
    return map.put(e, PRESENT)==null;
}

调用put()方法

然后执行的是HashMap集合的put方法，源码如下：

/**
 * HashMap的put添加方法
 * @param key    对应的是HashSet要添加的元素
 * @param value  对应的是一个常量对象 new Object()
 * @return       添加成功返回null，添加失败返回value值
 */
public V put(K key, V value) {
    // 调用putVal()方法，对元素进行添加
    return putVal(hash(key), key, value, false, true);
}

通过观察源码发现，在执行putVal()方法之前，会首先执行hash()方法，也就是对key值进行求哈希值，源码如下：

/**
 * HashMap的hash方法，用于计算每个key的hash值，这个hash值将决定key在哈希表中的具体位置
 * @param key    对应的是HashSet要添加的元素
 * @return       返回根据key计算出来的hash值
 */
static final int hash(Object key) {
    // 用于接收计算好的hash值
    int h;
    // 返回根据key计算出来的hash值
    // key如果是null 新hashCode是0 否则 计算新的hashCode
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

值得注意的是，在这里它并没有直接返回调用该key的hashCode()方法得到的哈希值，而是在此基础上，进行了与该key的哈希值无符号右移16位之后再异或的操作。

调用putVal()方法

下面才算正式进入了真正进行往HashMap中添加元素的方法了，这个比较复杂，源代码如下：

/**
 * HashMap的hash方法，用于计算每个key的hash值，这个hash值将决定key在哈希表中的具体位置
 * @param hash    		计算好的hash值
 * @param value    		需要存储的key值
 * @param onlyIfAbsent   需要存储的value值
 * @param onlyIfAbsent   如果返回true说明添加的key是首次添加，false说明是修改了对应key的value
 * @param evict    		目前HashMap并没有使用改变了，留给了实现HashMap的子类
 * @return       		
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 创建一个类型为Node的数组，其实就是哈希表
    Node<K,V>[] tab; 
    // 辅助变量，用于保存当前元素计算hash值后对应位置的元素节点
    Node<K,V> p; 
    // 辅助变量n，记录tab的长度。辅助变量i，存储经过计算得到的tab表的下标值
    int n, i;
    
    // 判断tab表是否为空，或者长度为0，满足则说明是第一次创建tab表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;    	      // 为tab表创建初始大小16，赋给辅助变量n
    
    // 将tab表长度减一再和该元素的hash值进行按位与运算，得到一个tab表的下标值，赋给i，
    // 再将当前下标所指向的tab表的对象赋给p，判断当前位置上是否存储对象，即是否为null
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);  // 如果当前位置为null，直接添加一个新节点 
    
    // 如果当前位置已经存储过节点
    else {
        // 创建一个节点对象e
        Node<K,V> e; 
        // 创建一个与key相同类型的变量k
        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
        
        // 否则需要添加，然后首先判断当前p是不是红黑树的一个节点对象
        else if (p instanceof TreeNode)
            // 如果当前底层数据结构是红黑树，则采用红黑树的逻辑进行添加元素节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);	
        // 否则如果table对应索引位置，已经是一个链表,就使用for循环比较
        else {
            /*
            	1. 依次和该链表的每一个元素比较后，都不相同,则加入到该链表的最后
 	               注意在把元素添加到链表后，立即判断该链表是否已经达到8个结点,
 	               达到8个节点数就调用treeifyBin()对当前这个链表进行树化(转成红黑树)
 	               注意：
                       if(tab==null||(n=tab.length)<MIN_TREEIFY_CAPACITY(64))
                            resize();
 	               如果上面条件成立，先table扩容，只有上面条件不成立时，才进行转成红黑树
            */
            for (int binCount = 0; ; ++binCount) {
                // 如果当前是最后一个元素节点位置
                if ((e = p.next) == null) {
                    // 直接添加
                    p.next = newNode(hash, key, value, null);
                    // 判断是否需要转换为红黑树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 2. 否则依次和该链表的每一个元素比较过程中，如果有key相同情况,就直接break
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 将对应位置上的节点
                p = e;
            }
        }
        
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // 记录集合被修改的次数
    ++modCount;
    // 判断当前哈希表中实际存储的元素个数是否得到扩容条件，threshold的大小为哈希表长度的0.75（默认值）
    if (++size > threshold)
        resize();				// 调用扩容方法
    afterNodeInsertion(evict);   // 该方法在HashMap中没有实际作用，是留给HashMap的子类的
    return null;			    // 添加节点元素成功，返回null
}

到这里，元素就成功添加到HashSet集合中了。

3.扩容机制分析

首次扩容

HashMap的初始化工作，源码如下：

 public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

在第一次添加数据时，会将数组容量设置为16（JDK1.7默认初始容量为16，JDK1.8默认初始容量为0，第一次添加时变为16），并且计算出临界值为12:((int)16*0.75)

在超过hash表的临界值时，会先进行添加数据的操作，在进行扩容(扩容规则是原容量的2倍，新的临界值也是原来的2倍)

if (++size > threshold)
resize();

扩容完成后，会将旧数组中的数据，转移到新数组中(会重新根据hash值和新数组长度进行计算新的索引位置)

通过上边的分析可知在添加数据时，如果一个桶中的链表长度大于8，并且数组长度达到64，则将当前链表结构变为红黑树结构，如果当前桶内已经是树结构了，则按照树结构的方式去添加数据。

添加元素后扩容

 final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table; // 临时变量，用于暂存老的table
     int oldCap = (oldTab == null) ? 0 : oldTab.length;  // 获得老的table的容量
     int oldThr = threshold; // 临时变量，暂存老的阈值
     int newCap, newThr = 0;  // 初始化新的容量和阈值为0
     if (oldCap > 0) {// 只有第一次添加时，不进入if的，以后的每次扩容都会进入到if中
         if (oldCap >= MAXIMUM_CAPACITY) {// 如果老容量大于最大值，则采用int范围的最大值作为临界值
             threshold = Integer.MAX_VALUE;
             return oldTab;
         }
         //对旧容量进行2倍操作，并赋值给新容量
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             //将临界值也更新为原来的2倍
             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);
     }
 	if (newThr == 0) {
         float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);
     }
     threshold = newThr;//将新临界赋值给对象中的临界值属性
     @SuppressWarnings({"rawtypes","unchecked"})
     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//采用新容量创建hash表
     table = newTab;//将新创建的hash表赋值给table  (table就有容量了)
     if (oldTab != null) {
     	//主要是将旧数组中的数据，循环添加到新数组中,会重新分配空间
     	for (int j = 0; j < oldCap; ++j) {
     		// 省略...
     	}
     }

4.其他方法

/** 
    * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 
    *  
    * 底层实际调用底层HashMap的keySet来返回所有的key。 
    * 可见HashSet中的元素，只是存放在了底层HashMap的key上， 
    * value使用一个static final的Object对象标识。 
    * @return 对此set中元素进行迭代的Iterator。 
    */  
public Iterator<E> iterator() {  
    return map.keySet().iterator();  
}  

/** 
    * 返回此set中的元素的数量（set的容量）。 
    * 
    * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
    * @return 此set中的元素的数量（set的容量）。 
    */  
public int size() {  
    return map.size();  
}  

/** 
    * 如果此set不包含任何元素，则返回true。 
    * 
    * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 
    * @return 如果此set不包含任何元素，则返回true。 
    */  
public boolean isEmpty() {  
    return map.isEmpty();  
}  

/** 
    * 如果此set包含指定元素，则返回true。 
    * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) 
    * 的e元素时，返回true。 
    * 
    * 底层实际调用HashMap的containsKey判断是否包含指定key。 
    * @param o 在此set中的存在已得到测试的元素。 
    * @return 如果此set包含指定元素，则返回true。 
    */  
public boolean contains(Object o) {  
    return map.containsKey(o);  
}  

/** 
    * 如果此set中尚未包含指定元素，则添加指定元素。 
    * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2)) 
    * 的元素e2，则向此set 添加指定的元素e。 
    * 如果此set已包含该元素，则该调用不更改set并返回false。 
    * 
    * 底层实际将将该元素作为key放入HashMap。 
    * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key 
    * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true）， 
    * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变， 
    * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中， 
    * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。 
    * @param e 将添加到此set中的元素。 
    * @return 如果此set尚未包含指定元素，则返回true。 
    */  
public boolean add(E e) {  
    return map.put(e, PRESENT)==null;  
}  

/** 
    * 如果指定元素存在于此set中，则将其移除。 
    * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e， 
    * 则将其移除。如果此set已包含该元素，则返回true 
    * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。 
    * 
    * 底层实际调用HashMap的remove方法删除指定Entry。 
    * @param o 如果存在于此set中则需要将其移除的对象。 
    * @return 如果set包含指定元素，则返回true。 
    */  
public boolean remove(Object o) {  
    return map.remove(o)==PRESENT;  
}  

/** 
    * 从此set中移除所有元素。此调用返回后，该set将为空。 
    * 
    * 底层实际调用HashMap的clear方法清空Entry中所有元素。 
    */  
public void clear() {  
    map.clear();  
}  

/** 
    * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。 
    * 
    * 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到  HashSet中。 
    */  
public Object clone() {  
    try {  
        HashSet<E> newSet = (HashSet<E>) super.clone();  
        newSet.map = (HashMap<E, Object>) map.clone();  
        return newSet;  
    } catch (CloneNotSupportedException e) {  
        throw new InternalError();  
    }  
}  

3、常见面试题

1.HashMap 和 HashSet 区别

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

2.为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

3.HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？

作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。

4.描述一下Map put的过程

HashMap是最经典的Map实现，下面以它的视角介绍put的过程：

1. 首次扩容：

   先判断数组是否为空，若数组为空则进行第一次扩容（resize）；

2. 计算索引：

   通过hash算法，计算键值对在数组中的索引；

3. 插入数据：

   • 如果当前位置元素为空，则直接插入数据；

   • 如果当前位置元素非空，且key已存在，则直接覆盖其value；

   • 如果当前位置元素非空，且key不存在，则将数据链到链表末端；

   • 若链表长度达到8，则将链表转换成红黑树，并将数据插入树中；

4. 再次扩容

   如果数组中元素个数（size）超过threshold，则再次进行扩容操作。

5.说一说HashSet。

• HashSet 是基于 HashMap 实现的，底层采用 HashMap 来保存元素。

• HashMap 的 Key 即 HashSet 存储的元素，所有 Key 都使用相同的 Value ，一个名为 PRESENT 的 Object 类型常量。使用 Key 保证元素唯一性，但不保证有序性。

• 由于 HashSet 是 HashMap 实现的，因此线程不安全。

• HashSet 判断元素是否相同时，对于包装类型直接按值比较。对于引用类型先比较 hashCode 是否相同，元素的哈希值是通过元素的 hashCode 方法 来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法 如果 equls 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。

  首先比较hashCode 值不同则代表不是同一个对象，相同则继续比较 equals，都相同才是同一个对象。

微信关注