【Java 集合】这次真的从0到1彻底吃透HashSet底层实现源码！
0、HashSet 简介
-
Serializable接口，表明它支持序列化。 -
实现了
Cloneable接口，表明它支持克隆，可以调用超类的clone()方法进行浅拷贝。 -
继承了
AbstractSet抽象类，和 ArrayList 和 LinkedList 一样，在他们的抽象父类中，都提供了 equals() 方法和 hashCode() 方法。它们自身并不实现这两个方法。 -
实现了
Set
HashSet是Set接口的典型实现，HashSet按照Hash算法来存储集合中的元素。存在以下特点：
-
不能保证元素的顺序，元素是无序的
-
HashSet不是同步的，需要外部保持线程之间的同步问题
-
集合元素值允许为null
通过观察源代码可以看到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();
// 无参构造方法，完成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);
}
HashMap实现的。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位之后再异或的操作。
这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞
调用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
}将负载因子设置为0.75
table=null
临界值=0
在第一次添加数据时，会将数组容量设置为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) {
// 省略...
}
}
/**
* 返回对此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 中的方法。
HashMap |
HashSet |
|---|---|
实现了 Map 接口 |
实现 Set 接口 |
| 存储键值对 | 仅存储对象 |
调用 put()向 map 中添加元素 |
调用 add()方法向 Set 中添加元素 |
HashMap 使用键（Key）计算 hashcode |
HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性 |
2.为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?
因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。
3.HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？
作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。
4.描述一下Map put的过程
HashMap是最经典的Map实现，下面以它的视角介绍put的过程：
-
首次扩容：
先判断数组是否为空，若数组为空则进行第一次扩容（resize）；
-
计算索引：
通过hash算法，计算键值对在数组中的索引；
-
插入数据：
-
如果当前位置元素为空，则直接插入数据；
-
如果当前位置元素非空，且key已存在，则直接覆盖其value；
-
如果当前位置元素非空，且key不存在，则将数据链到链表末端；
-
若链表长度达到8，则将链表转换成红黑树，并将数据插入树中；
-
-
再次扩容
如果数组中元素个数（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，都相同才是同一个对象。
微信关注
