Java 中 HashSet 的底层基本原理实现

一：HashSet集合的特点

1. 底层数据结构是哈希表
2. 不能保证存储和取出的顺序完全一致
3. 它没有索引，无法使用for循环进行遍历，可以使用迭代器和增强for
4. 由于它是Set集合，所以元素唯一。

下面通过代码可以看出上面的特点：

package com.wt.hashset;

import java.util.HashSet;
import java.util.Iterator;

public class HashSetDemo1 {
    /*
    HashSet集合的特点：
        1.底层数据结构是Hash表
        2.不能保证存储数据的顺序和取出的顺序一致
        3.HashSet是和TreeSet一样是无索引的,不能使用普通for进行遍历
        4.由于是Set集合所以元素唯一
     */
    public static void main(String[] args) {
        HashSet<String> hs = new HashSet();
        hs.add("1");
        hs.add("1");
        hs.add("3");
        hs.add("2");
        hs.add("4");
        //使用迭代器
        Iterator<String> iterator = hs.iterator();
        while (iterator.hasNext()){
            String i = iterator.next();
            System.out.println(i);
        }
        //使用增强for循环
        System.out.println("------------------------------------------");
        for (String s : hs){
            System.out.println(s);
        }

    }
}

二：哈希值介绍

        哈希值是JDK根据对象的地址值或者属性值计算出来的一个int类型的整数

哈希值的特点：

1. 如果我们没有重写hashCode和equals方法的话，那么就默认调用对象的地址值，来计算哈希值的。同一个对象调用的哈希值，得到的值都是一样的，不同对象不一样
2. 如果在标准类中重写了hashCode和equals方法，那么我们就是根据对象的属性来计算的哈希值 。如果不同对象的属性值是一样的，那么我们计算出来的哈希值也是一样的。

哈希冲突：

1. 由于int类型的取值范围有限，不同对象属性 计算出来的哈希值也有可能相同，所以我们就需要通过equals方法来比较属性是否相同。

package com.wt.hashset;

import com.wt.hashset.domain.Student;

public class HashSetDemo2 {
    /*
    创建对象并计算Hash值
    同一个对象被调用两次都是一样的哈希值
    哈希值的特点：
        一：.如果我们没有重写hashCode方法的话，那么就默认调用对象的地址值，来计算哈希值的
            1.同一个对象调用的哈希值，得到的值都是一样的，不同对象不一样
        二：.如果在标准类中重写了hashCode 方法，那么我们就是根据对象的属性来计算的哈希值
            1.如果不同对象的属性值是一样的，那么我们计算出来的哈希值也是一样的
        三.哈希值为int类型的整数
     */
    public static void main(String[] args) {
        Student s1 = new Student("小猪",21);
        Student s2 = new Student("小牛",11);
        //在object中，是根据对象的地址值计算出来的哈希值是int类型的整数
        System.out.println(s1.hashCode());//356573597
        System.out.println(s1.hashCode());//356573597


        System.out.println(s2.hashCode());//1735600054

    }
}

三：哈希表

哈希表：

1. Jdk8（不包括8）之前，底层采用数组+链表结构
2. Jdk8开始，进行了优化，由数组+链表+红黑树来实现的

四：HashSet底层原理：

• Jdk 1.7 中 HashSet 原理

HashSet<String> hs = new HashSet();

1. 创建了一个默认长度为16，默认加载因子为0.75的数组，数组名为table。
2. 根据元素的哈希值和数组的长度计算出存入的位置（索引）值。
3. 判断当前位置是否为null，如果是null，则直接存入
4. 如果应存入的位置不是null，表示该位置有元素，则调用equals方法比较属性值。
5. 如果属性值一样，则不存入，如果属性值不一样，则存入数组，老元素挂载在新元素下面，形成链表结构。每次存入一个数据都和链表中的元素进行equals比较属性，属性值一样，则不存，不一样则存，重复以上操作。
6. 当存满了16个长度的元素怎么办呢？这是一个问题，这个问题就交给了加载因子，我们默认的加载因子是0.75。当数组中存满了 16*0.75 = 12 个元素的时候，数组就会自动扩容为当前数组长度的两倍。

上面就是jdk1.7版本的HashSet集合的底层原理。

如果链表中的元素过多会照成查询效率低下，每一次进行存储都会在链表中一个一个去比较，浪费时间。所以在这里我们要引入Jdk1.8更新的内容。

• Jdk 1.8 中 HashSet 底层原理

在上文中我们说到了，jdk1.7中底层的实现原理，还是有一些缺点的，所以我们java在jdk1.8中就进行了改进。

若我们这个链表上挂载了很多元素，每一次进行存储都会在链表中一个一个去比较，对判断的效率影响太大。所以在jdk 1.8 中我们采用了 红黑树的结构。当链表的长度超过8的时候，自动给我们转化成了红黑树。小的元素在右边，大的元素在左边，这样我们进行查询判断的效率就大大的提高了。

 如果HashSet集合要存储自定义对象，那么必须重写hashCode和equals方法

以上就是我对HashSet底层原理的基本理解，希望可以帮助大家，若有不正确的地方，还希望大家指出。