HashSet底层原理简单详解
1、HashSet底层其实是一个HashMap容器，HashSet的无参构造方法是创建一个HashMap对象public HashSet() {this.map = new HashMap();}2、add方法添加数据实则是调用其成员变量map的put方法public boolean add(E var1) {return this.map.put(var1, PRESENT) == null;}
1、HashSet底层其实是一个HashMap容器，HashSet的无参构造方法是创建一个HashMap对象
private transient HashMap<E, Object> map;
public HashSet() {
this.map = new HashMap();
}
2、add方法添加数据实则是调用其成员变量map的put方法，PRESENT 就是一个Object类，目前还不太理解作用，把其作用当为占位
private static final Object PRESENT = new Object();
public boolean add(E var1) {
return this.map.put(var1, PRESENT) == null;
}
3、put方法调用putVal方法
public V put(K var1, V var2) {
return this.putVal(hash(var1), var1, var2, false, true);
}
4、hash方法通过要存储的数据的哈希值经过一些运算返回一个int型整数
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
transient HashMap.Node<K, V>[] table;
final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) {
HashMap.Node[] var6;
int var8;
if ((var6 = this.table) == null || (var8 = var6.length) == 0) {
var8 = (var6 = this.resize()).length;
}
Object var7;
int var9;
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
} else {
Object var10;
Object var11;
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;
}
if (((HashMap.Node)var10).hash == var1 && ((var11 = ((HashMap.Node)var10).key) == var2 || var2 != null && var2.equals(var11))) {
break;
}
var7 = var10;
++var12;
}
}
if (var10 != null) {
Object var13 = ((HashMap.Node)var10).value;
if (!var4 || var13 == null) {
((HashMap.Node)var10).value = var3;
}
this.afterNodeAccess((HashMap.Node)var10);
return var13;
}
}
++this.modCount;
if (++this.size > this.threshold) {
this.resize();
}
this.afterNodeInsertion(var5);
return null;
}
5、putVal方法首先声明一个节点型数组var6（Node是HashMap的内部类，Empty的实现类）,int型整数var8,table为HashMap的成员变量，一个跟var6相同类型的节点型数组，将table的地址赋给了var6并且进行判断是否为空或长度是否为0，如果是的话需要调用resize()方法来创建table。Object类var7其实是一个节点，Node类的对象。因为存储的时候是通过数据的hash值和table的长度运算得出存储位置，再通过判断是否为null(默认都是null),如果为空的话直接将数据打包成一个节点替换掉原来的null
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
}
（去重）如果不为空的话，判断存储位置var7的哈希值是否与数据传递过来的哈希值相等，然后再判断它的key地址是否相等，最后再用equals()方法判断，相同的话记住这个节点（其实这个地方不太理解）
if (((HashMap.Node)var7).hash == var1 && ((var11 = ((HashMap.Node)var7).key) == var2 || var2 != null && var2.equals(var11))) {
var10 = var7;
}
不相同的话再判断存储位置的这个节点是否是树形结构（红黑树结构），如果是的话调用putTreeVal()方法将其存储到红黑树
} else if (var7 instanceof HashMap.TreeNode) {
var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3);
}
因为jdk1.8之前的版本table中的节点结构是链表结构，但是由于一个节点上存储过多数据可能导致查询变慢，所以当节点中的链表长度为8时调用HashMap中的treeifyBin()方法将链表结构转为红黑树结构，提高查找效率var6为HashMap中要转变节点结构的节点数组，即table,var1是传递过来的存储位置哈希值，通过这两个参数找到要转变结构的节点（这个方法没有去深究了，不知道对不对，有错误请指出）
通过while循环节点中的链表中的数据，链表的最后一个也是有连接的，只不过是一个null,所以判断为null的话就直接将要存储的数据打包一个节点连接上去，在判断为null之前，节点中的数据都会遍历一遍，即判断一下是否与其中的数据相同，如果相同就会break退出循环
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;
}
if (((HashMap.Node)var10).hash == var1 && ((var11 = ((HashMap.Node)var10).key) == var2 || var2 != null && var2.equals(var11))) {
break;
}
var7 = var10;
++var12;
}
}
6、这个代码是用来替换Valued的，当var10不为空的情况只有上文中的去重时break才会发生，var4为固定的FALSE,((HashMap.Node)var10).value = var3;这样就替换了原来的Value
if (var10 != null) {
Object var13 = ((HashMap.Node)var10).value;
if (!var4 || var13 == null) {
((HashMap.Node)var10).value = var3;
}
this.afterNodeAccess((HashMap.Node)var10);
return var13;
}
7、resize方法
第一次调用会创建一个节点数组table,之后再调用的话就是为了扩容，table含有一个加载因子为0.75，当存储的节点长度为table长度*加载因子时就会扩容，长度变为当前的两倍
但是之前有一个困扰我很久的误区，因为存储位置是通过数据的哈希值和table的长度来计算的，如果长度变了是否就会影响存储位置从而产生相同对象存储进去。
后来才知道扩容后会重新计算table中节点的位置，会调用rehash（）方法重新计算地址
final HashMap.Node<K, V>[] resize() {
HashMap.Node[] var1 = this.table;
int var2 = var1 == null ? 0 : var1.length;
int var3 = this.threshold;
int var5 = 0;
int var4;
if (var2 > 0) {
if (var2 >= 1073741824) {
this.threshold = 2147483647;
return var1;
}
if ((var4 = var2 << 1) < 1073741824 && var2 >= 16) {
var5 = var3 << 1;
}
} else if (var3 > 0) {
var4 = var3;
} else {
var4 = 16;
var5 = 12;
}
if (var5 == 0) {
float var6 = (float)var4 * this.loadFactor;
var5 = var4 < 1073741824 && var6 < 1.07374182E9F ? (int)var6 : 2147483647;
}
this.threshold = var5;
HashMap.Node[] var14 = (HashMap.Node[])(new HashMap.Node[var4]);
this.table = var14;
if (var1 != null) {
for(int var7 = 0; var7 < var2; ++var7) {
HashMap.Node var8;
if ((var8 = var1[var7]) != null) {
var1[var7] = null;
if (var8.next == null) {
var14[var8.hash & var4 - 1] = var8;
} else if (var8 instanceof HashMap.TreeNode) {
((HashMap.TreeNode)var8).split(this, var14, var7, var2);
} else {
HashMap.Node var9 = null;
HashMap.Node var10 = null;
HashMap.Node var11 = null;
HashMap.Node var12 = null;
HashMap.Node var13;
do {
var13 = var8.next;
if ((var8.hash & var2) == 0) {
if (var10 == null) {
var9 = var8;
} else {
var10.next = var8;
}
var10 = var8;
} else {
if (var12 == null) {
var11 = var8;
} else {
var12.next = var8;
}
var12 = var8;
}
var8 = var13;
} while(var13 != null);
if (var10 != null) {
var10.next = null;
var14[var7] = var9;
}
if (var12 != null) {
var12.next = null;
var14[var7 + var2] = var11;
}
}
}
}
}
return var14;
}
初学者自己的理解，有不对的请指出
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)