- HashSet集合底层是HashMap
public HashSet() {
this.map = new HashMap();
}
- HashSet添加步骤:添加元素时,先得到这个元素的hash值(并不止是直接取hashcode()方法的值,还会进行异或和无符号右移运算,如下图一),并转化索引值(并不等于实际放的位置的索引,真正的索引值还会进行下图二运算(var9)),这里我注意到了一点,当添加进集合的值是null时,该算法计算出来的索引值为0,所以null放进去的位置始终在集合第一位。
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
}
- 随后判断当前table的大小,如果是第一次添加,则扩容table容量为16,并根据加载因子(默认0.75),算出临界值12,这个临界值意味着当table中已存在元素超过12(并不只是table数组容量的被占用量超过12,而是table数组+所有链表的被占用量超过12,可以理解为向HashSet中正确的添加了12个元素),即添加13个元素时,便进行扩容,扩容为原来的两倍,即32,以此类推。
} else {
var4 = 16;
var5 = 12;
}
- 随后找到存储数据表table,看这个索引位置是否已经存放了元素;若没有,则直接加入。
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
}
- 如果有,调用equals方法跟现链表上的节点逐一比较,如果相同,就放弃添加;如果不同,就添加到当前链表的末尾,在java8中,如果一条链表的元素个数到达xxx(默认8,没算上第一个节点P,算上就是到达9),并且table数组的大小>=xxx(默认64),该链表就会转变为红黑树(红黑树效率比链表更高);如果table数组的大小不足64,则扩容table数组,新的元素则继续放在该链表末尾,直到table数组容量到达64。
if (((HashMap.Node)var7).hash == var1 && ((var11 = ((HashMap.Node)var7).key) == var2 || var2 != null && var2.equals(var11))) {
var10 = var7;
} else if (var7 instanceof HashMap.TreeNode) {
var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3);
} else {
int var12 = 0;
while(true) {
if ((var10 = ((HashMap.Node)var7).next) == null) {
((HashMap.Node)var7).next = this.newNode(var1, var2, var3, (HashMap.Node)null);
if (var12 >= 7) {
this.treeifyBin(var6, var1);
}
break;
}
- HashSet的table数组节点(即HashMap的节点)Node对象,其有四个属性,分别是hash、key、value、next(Node对象)。hash即key的hash值,key即存放的元素值;value是一个空对象(new Object()),所有节点共用一个它;next是一个新的Node对象,以便实现链表(可以理解为套娃)。
static class Node<K, V> implements Entry<K, V> {
final int hash;
final K key;
V value;
HashMap.Node<K, V> next;
Node(int var1, K var2, V var3, HashMap.Node<K, V> var4) {
this.hash = var1;
this.key = var2;
this.value = var3;
this.next = var4;
}
}
- 强调一点:元素超过第8个(到达第9个)时,判断子链表是否转化为红黑树;元素超过第12个(到达第13个)时,table数组开始扩容
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)