Java – 集合Set – HashSet哈希集合

简介

HashSet集合是Set集合下的子类，为无序、不重复、无索引的集合

HashCode 相关

在讲解HashSet之前，我们先了解一下Hash在Java中的定义与原理。

Java中，hash值可通过 对象.hashCode() 方法取得，哈希值为一个 int 类型的值，所以取值范围在 -21亿 ~ 21亿 之间，因此，有可能会出现相同哈希的情况（比较少见但存在），这种现象我们称为【哈希碰撞】

因为 hashCode() 方法在 Object 中定义，所以每一个实例都有对应的hash值。

Java中，计算哈希值的算法是利用对象的内存地址计算得出，不同的对象实例哈希值会不一样。

System.out.println("abc".hashCode());  // => 96354
System.out.println(Integer.valueOf(123).hashCode());  // => 123

我们可以通过重写 hashCode() 方法来自定义哈希值

@Override
public int hashCode() {
    return Objects.hash();
}

HashSet底层原理

1.HashSet集合底层采用哈希表存储数据

2.哈希表是一种对于增删改查数据性能都较好的结构

3.在JDK8之前，哈希表采用 数组 + 链表 进行存储

4.在JDK8之后，哈希表采用 数组 + 链表 + 红黑树 进行存储

哈希表原理

哈希表初始化时，会默认创建一个 16 个成员的数组，加载【因子为0.75】，数组名为 table，默认数据为 null。

当存入一个数据时，数据应存数组的索引值由如下方式计算得出

int index = (数组长度 - 1) & 成员哈希值;

对存入的成员进行哈希值计算，并与 数组长度-1 作【与】运算。

假设计算得出 index 索引为 4 的位置，会检查索引4的数组中是否有数据

当再次添加数据时，发现要存储的数据在数组中已有数据时的情况，会对用 equals 方法进行对比

当哈希表中的数据已被填满到总体数量的 75%时（加载因子），哈希表会被扩容一倍。即当12个索引都有数据时，数组被扩容为一个 32 个成员的数组。

JDK8之后，当链表长度大于8且数组长度大于64时，链表将被替换为红黑树存储结构