哈希值介绍

创建一个实体类

public class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

使用测试

public static void main(String[] args) {
    Student s1 = new Student("zhangsan", 12);
    Student s2 = new Student("zhangsan", 12);

    System.out.println(s1.hashCode());
    System.out.println(s2.hashCode());
}

• 打印结果不同

重写hashCode 和 equals方法后

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Student student = (Student) o;
    return age == student.age && Objects.equals(name, student.name);
}

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

• 运行结果相同--自定义类型对象，因为在没有重写hashCode和equals方法前的哈希值是通过地址值来进行计算的。

System.out.println("123".hashCode());
System.out.println("123".hashCode());

• 测试自定义的String对象时，哈希值相同，说明它重写了hashCode和equals方法。

注意事项：因为哈希值是采用int类型存储，所以哈希值是有限的数据，所以就有可能存在哈希冲突，如下例：

System.out.println("abc".hashCode());
System.out.println("acD".hashCode());

HashSet 的底层原理

HashSet 的底层构成

注意事项：

1. 默认情况下会 new 一个哈希表

2. 在HashMap中就是采用的内部定义的Node来存放每一个元素

   

• 所以在HashSet中其实主要存的就是HashMap对象，像知道底层的原理，可以看后面的HashMap底层原理介绍。

• 在调用HashSet的很多方法的时候，其实底层就是去掉了HashMap的方法。

HashSet 的元素添加过程

1. 首先获取当前需要添加的元素的Hash值

2. 然后判断当前需要存放的位置是否已经有元素了

3. 要是没有元素，那就直接将当前添加的元素放到这个位置

4. 要是有元素了，那就需要对当前存放的数据进行比较判断

5. 当现在加入的元素在里面的时候，就直接不进行操作，返回false添加失败

6. 当里面没有时

   • 在Jdk8以前是需要将当前的元素作为头节点，然后将后面的节点连接到当前的节点的下方
   • 在Jdk8及以后是直接将当前元素的尾节点位置，并且当当前的元素数量到达一个阈值后（链表的长度超过8，而且数组的长度大于等于64时），就会自动的将当前的链表转为一颗红黑树来进行存储，而Jdk8以前没有当前的这一步转成红黑树的操作。

7. 成功将当前数据存储后直接返回true添加元素成功。

HashSet 的三个特点介绍

HashSet 无序的特点

• 因为HashSet底层还是使用的数组来进行数据存储的，在取数据的时候，它是从小标为0的数组位置依次进行取数据
• 而我们在存数据的时候，我们是通过计算出的Hash值来判断具体存在那个下标位置的
• 所以导致我们先存的数据可能存储的下标位置在后面,然后就导致HashSet是无序的

public static void main(String[] args) {
    HashSet<String> set = new HashSet<>();

    set.add("123");
    set.add("456");
    set.add("444");

    System.out.println(set);
}

HashSet 没有索引

• 因为在底层存储的数据中，每一个下标位置存的是一串链表，或者是一颗红黑树，所以通过下标访问，就不能够有效的取出某一个数据

HashSet 的去重机制

• 主要其实就是通过HashCode方法和equals方法来进行的
• 当计算出添加的元素的Hash地址后就可以知道当前需要添加的元素需要存放的位置
• 然后在通过equals方法来判断当前的元素值是否一样，要是也想通，那么就说明当前的数据重复，从而达到去重效果

扩展 LinkedHashSet 介绍

特点

• 和HashSet的不同之处---LinkedHashSet在做取的时候，得到的属于是有序的。

有序的原理

• 它是在底层的HashSet基础之上添加一个指针来记录当前添加进来的第一个元素，作为当前链表的头节点
• 然后在第二个元素进来后，就会将第二个元素和第一个元素之间相互连接，并且第二个元素会被链表的尾指针指向
• 在实际调用遍历方法的时候，和HashSet的区别就是，前者是遍历每一个列表元素，而LinkedHashSet是通过头指针，找到第一个元素，然后直接遍历整个链表来实现遍历的。

使用测试

public static void main(String[] args) {
    HashSet<String> set = new HashSet<>();

    set.add("123");
    set.add("456");
    set.add("444");

    System.out.println(set);
}		

• 使用HashSet的输出结果

public static void main(String[] args) {
    LinkedHashSet<String> set = new LinkedHashSet<>();

    set.add("123");
    set.add("456");
    set.add("444");

    System.out.println(set);
}

• 通过同样的例子，可以明显看出二者之间的区别

LinkedHashSet 总结

使用场景