【JAVA基础】集合类之Hash的原理及应用

近期几期内容都是围绕该体系进行知识讲解，以便于同学们学习Java集合篇知识能够系统化而不零散。

本文将介绍HashSet的基本概念，功能特点，使用方法，以及优缺点分析和应用场景案例。

一、概念

HashSet是 Java 集合框架中的一个重要成员，它实现了Set接口。Set接口的主要特点是不允许包含重复元素，而HashSet以哈希表的方式来存储元素，这使得它在存储和检索元素时具有高效的性能。

与LinkedHashSet 的区别：

HashSet 底层是由HashMap实现的，通过对象的hashCode方法与equals方法来保证插入元素的唯一性，无序(存储顺序和取出顺序不一致)，。
LinkedHashSet 底层数据结构由哈希表和链表组成。哈希表保证元素的唯一性，链表保证元素有序。(存储和取出是一致)

二、存储方式

哈希函数

（1）HashSet使用哈希函数来计算元素的哈希值。哈希函数是一种将任意长度的数据映射为固定长度哈希值的函数。对于要存储的每个元素，HashSet会调用其哈希函数来获取一个哈希值。
（2）例如，对于整数类型，哈希函数可能会简单地对整数进行一些计算来得到哈希值；对于对象类型，默认会使用对象的hashCode()方法来计算哈希值。

哈希表结构

（1）HashSet内部使用哈希表来存储元素。哈希表是一个数组，每个数组元素称为一个 “桶”（bucket）。
（2）当一个元素被添加到HashSet时，首先通过哈希函数计算出该元素的哈希值，然后根据哈希值确定它应该存储在哪个桶中。
（3）如果多个元素的哈希值相同，它们会被存储在同一个桶中。在这种情况下，HashSet会通过比较元素的equals()方法来确保集合中不包含重复元素。只有当两个元素的哈希值相同且equals()方法返回true时，才被认为是重复元素。

三、源码分析

构造方法

HashSet()
构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。
HashSet(Collection<? extends E> c)
构造一个包含指定 collection 中的元素的新 set。
HashSet(int initialCapacity)
构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
HashSet(int initialCapacity, float loadFactor)
构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子。放

实现原理

（1）往Haset添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值，然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置。见下面2种情况：
情况1：如果算出元素存储的位置目前没有任何元素存储，那么该元素可以直接存储到该位置上。
情况2：如果算出该元素的存储位置目前已经存在有其他的元素了，那么会调用该元素的equals方法与该位置的元素再比较一次，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素运行添加。

HashSet 中 hashCode () 与 equals () 方法的调用时机

添加元素时

哈希值计算与哈希冲突判断
当向HashSet中添加一个元素时，首先会调用该元素的hashCode()方法来获取其哈希值。这个哈希值用于确定元素在HashSet内部哈希表中的存储位置（桶的位置）。
例如，有一个自定义类Person的实例要添加到HashSet中：

public class Person {int id;String name;public Person(int id, String name) {super();this.id = id;this.name = name;}@Override public String toString() {return "{ 编号:" + this.id + " 姓名：" + this.name + "}";}@Override public int hashCode() {System.out.println("=======hashCode方法被调用了=====");return this.id;}@Override public boolean equals(Object obj) {System.out.println("======equals方法被调用了======");Person p = (Person) obj;return this.id == p.id;}
}

原始的判断是否能添加的逻辑：
当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该HashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals()方法比较返回true，但它们的hashCode()方法返回值不相等，HashSet将会把它们存储在不同的位置，依然可以添加成功。即，HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。

当执行 set.add(new Person(110, “Alice”));时，会先调用Person类的hashCode()方法计算哈希值
在上面HashCode是自己重写过的，将ID直接当做Hash值；
同时重写了equals方法，因为add的时候先调用HashCode方法判断Hash值是否一致，如果一致，则通过判断equals的结果是否为true，如果为true则代表元素重复，拒绝添加！
重写的equals方法：如果ID相同则元素相同

如果不同元素计算出的哈希值相同（哈希冲突），此时HashSet会进一步调用这些元素的equals()方法来判断它们是否真正相等。只有当两个元素的哈希值相同且equals()方法返回true时，才认为这两个元素是重复的，不会将新元素添加到HashSet中。
假设在HashSet中已经存在一个Person对象p1（ id= 25，name = “Alice”），现在要添加另一个Person对象p2【new Person(220, “GOD”)】 p3对象【new Person(330, “LiMing1”)】、p4对象【new Person(110, “LiMing2”)】；

验证：


class Demo2 {public static void main(String[] args) {HashSet set = new HashSet();boolean alice = set.add(new Person(110, "Alice"));boolean god = set.add(new Person(220, "GOD"));boolean liMing1 = set.add(new Person(330, "LiMing1"));boolean liMing2 = set.add(new Person(110, "LiMing2"));//在现实生活中只要编号一致就为同一个人.System.out.println("添加成功吗？" +liMing1);System.out.println("添加成功吗？" +liMing2 );System.out.println("集合的元素：" + set);}
}

可见结果如下：
解释：
因为add了四次，所以有调用四次hashCode方法，来计算HashCode，在我们的代码里面重写了HashCode方法，id当做了HashCode的值，如果HashCode的值一致，则调用equals方法，判断id是否一致，如果一致则判断元素重复，添加失败。因为有两个110的id，所以第一个添加成功，第二个添加失败
在这里插入图片描述
如果id改完不一致的，则添加成功。即使name一致（因为重写的equals是通过判断ID是否一致来判断元素重复与否的。）

四、使用场景

去重

当需要去除一个集合中的重复元素时，HashSet是一个很好的选择。例如，在处理一组用户输入的数据时，如果不希望有重复的数据，可以将数据存储在HashSet中。


class Demo2 {public static void main(String[] args) {System.out.println("=======================================");
//      LinkedHashSet去重  去重后保持原有顺序（重复数据只保留一条）String[] arr = new String[] {"i", "think", "i", "am", "the", "best"};Collection<String> noDups = new LinkedHashSet<String>(Arrays.asList(arr));System.out.println("(LinkedHashSet) distinct words:    " + noDups);System.out.println("=======================================");
//       去重后顺序打乱（重复数据只保留一条）String[] arr2 = new String[] {"i", "think", "i", "am", "the", "best"};Collection<String> noDups2 = new HashSet<String>(Arrays.asList(arr2));System.out.println("(HashSet) distinct words:    " + noDups2);System.out.println("=======================================");
//      去重后顺序打乱（重复数据只保留一条）String[] arr3 = new String[] {"i", "think", "i", "am", "the", "best"};Set<String> s = new HashSet<String>();for (String a : arr3){if (!s.add(a)){System.out.println("Duplicate detected: " + a);}}System.out.println(s.size() + " not distinct words: " + s);
//        去重后顺序打乱(相同的数据一条都不保留，取唯一) ,能把重复的元素剔除出去；同时把哪些元素重复过滤出来System.out.println("=======================================");String[] arr4 = new String[] {"i", "think", "i", "am", "the", "best"};Set<String> uniques = new HashSet<String>();Set<String> dups = new HashSet<String>();for (String a : arr4){{if (!uniques.add(a))dups.add(a);}}uniques.removeAll(dups);System.out.println("Unique words:    " + uniques);System.out.println("Duplicate words: " + dups);}
}

结果：
在这里插入图片描述

快速查找

由于哈希表的特性，HashSet在查找元素时具有非常高的效率。平均时间复杂度接近常数时间。
比如在一个大型数据集中快速判断某个元素是否存在

集合运算

在进行一些集合相关的运算时，HashSet也很有用。例如，可以使用HashSet来计算两个集合的交集、并集和差集等。

假设有两个集合set1和set2，计算它们的交集：

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));Set<Integer> intersectionSet = new HashSet<>(set1);
intersectionSet.retainAll(set2);
System.out.println("Intersection set: " + intersectionSet); // 输出 [4, 5]

在多线程环境下的使用示例（注意需要适当的同步措施）

import java.util.HashSet;
import java.util.Set;public class HashSetInMultiThreadExample {public static void main(String[] args) {Set<Integer> sharedSet = new HashSet<>();// 创建多个线程并向集合中添加元素Thread thread1 = new Thread(() -> {for (int i = 0; i < 1000; i++) {sharedSet.add(i);}});Thread thread2 = new Thread(() -> {for (int i = 1000; i < 2000; i++) {sharedSet.add(i);}});// 启动线程thread1.start();thread2.start();// 等待线程完成try {thread1.join();thread2.join();} catch (InterruptedException e) {e.printStackTrace();}// 输出集合中的元素数量System.out.println("Size of the set after multi-threaded operations: " + sharedSet.size());}
}