1. HashSet 集合存储数据的结构 (哈希表)
1.1 什么是哈希表?
哈希表底层使用的也是数组机制, 数组中也存放对象, 而这些对象往数组中存放时的位置比较特殊, 当需要把这些对象给数组中存放时, 那么会根据这些对象的特有数据结合相应的算法, 计算出这个对象在数组中的位置, 然后把这个对象存放在数组中而这样的数组就称为哈希数组, 即就是哈希表
1.2 哈希表存储数据结构原理
当向哈希表中存放元素时, 需要根据元素的特有数据结合相应的算法, 这个算法其实就是 Object 类中的 hashCode 方法由于任何对象都是 Object 类的子类, 所以任何对象也拥有这个方法即就是在给哈希表中存放对象时, 会调用对象的 hashCode 方法, 算出对象在表中的存放位置, 这里需要注意, 如果两个对象 hashCode 方法算出结果一样, 这样现象称为哈希冲突, 这时会调用对象的 equals 方法, 比较这两个对象是不是同一个对象, 如果 equals 方法返回的是 true, 那么就不会把第二个对象存放在哈希表中, 如果返回的是 false, 就会把这个值存放在哈希表中
1.3 哈希表存储数据结构原理图
2. hash
hash 是散列的意思, 就是把任意长度的输入, 通过散列算法变换成固定长度的输出, 该输出就是散列值关于散列值, 有以下几个关键结论:
如果散列表中存在和散列原始输入 K 相等的记录, 那么 K 必定在 f(K) 的存储位置上
不同关键字经过散列算法变换后可能得到同一个散列地址, 这种现象称为碰撞
如果两个 hash 值不同 (前提是同一 hash 算法), 那么这两个 hash 值对应的原始输入必定不同
3. hashCode
hashCode 的存在主要是为了查找的快捷性, hashCode 是用来在散列存储结构中确定对象的存储地址的
如果两个对象 equals 相等, 那么这两个对象的 hashCode 一定也相同
如果对象的 equals 方法被重写, 那么对象的 hashCode 方法也尽量重写
如果两个对象的 hashCode 相同, 不代表两个对象就相同, 只能说明这两个对象在散列存储结构中, 存放于同一个位置
如果根据 equals 方法, 两个对象不相等, 那么对这两个对象中的任一对象上调用 hashCode 方法不一定生成不同的整数结果但是, 程序员应该意识到, 为不相等的对象生成不同整数结果可以提高哈希表的性能
4. hashCode 作用
我们知道 Set 里面的元素是不可以重复的, 那么如何做到?
Set 是根据 equals() 方法来判断两个元素是否相等的比方说 Set 里面已经有 1000 个元素了, 那么第 1001 个元素进来的时候, 最多可能调用 1000 次 equals 方法, 如果 equals 方法写得复杂, 对比的东西特别多, 那么效率会大大降低使用 HashCode 就不一样了, 比方说 HashSet, 底层是基于 HashMap 实现的, 先通过 HashCode 取一个模, 这样一下子就固定到某个位置了, 如果这个位置上没有元素, 那么就可以肯定 HashSet 中必定没有和新添加的元素 equals 的元素, 就可以直接存放了, 都不需要比较; 如果这个位置上有元素了, 逐一比较, 比较的时候先比较 HashCode,HashCode 都不同接下去都不用比了, 肯定不一样, HashCode 相等, 再 equals 比较, 没有相同的元素就存, 有相同的元素就不存如果原来的 Set 里面有相同的元素, 只要 HashCode 的生成方式定义得好 (不重复), 不管 Set 里面原来有多少元素, 只需要执行一次的 equals 就可以了这样一来, 实际调用 equals 方法的次数大大降低, 提高了效率
5. HashSet 存储 JavaAPI 中的类型元素
给 HashSet 中存储 JavaAPI 中提供的类型元素时, 不需要重写元素的 hashCode 和 equals 方法, 因为这两个方法, 在 JavaAPI 的每个类中已经重写完毕, 如 String 类 Integer 类等
举个栗子:
- public class HashSetDemo {
- public static void main(String[] args) {
- // 创建 HashSet 对象
- HashSet<String> hs = new HashSet<String>();
- // 给集合中添加自定义对象
- hs.add("zhangsan");
- hs.add("lisi");
- hs.add("wangwu");
- hs.add("zhangsan");
- // 取出集合中的每个元素
- Iterator<String> it = hs.iterator();
- while(it.hasNext()){
- String s = it.next();
- System.out.println(s);
- }
- }
- }
输出结果:
- wangwu
- lisi
- zhangsan
6. HashSet 存储自定义类型元素
给 HashSet 中存放自定义类型元素时, 需要重写对象中的 hashCode 和 equals 方法, 建立自己的比较方式, 才能保证 HashSet 集合中的对象唯一
举个栗子:
自定义 Student 类
- public class Student {
- private String name;
- private int age;
- public Student(String name, int age) {
- super();
- this.name = name;
- this.age = age;
- }
- public String getName() {
- return name;
- }
- public void setName(String name) {
- this.name = name;
- }
- public int getAge() {
- return age;
- }
- public void setAge(int age) {
- this.age = age;
- }
- @Override
- public String toString() {
- return "Student [name=" + name + ", age=" + age + "]";
- }
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + age;
- result = prime * result + ((name == null) ? 0 : name.hashCode());
- return result;
- }
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if(!(obj instanceof Student)){
- System.out.println("类型错误");
- return false;
- }
- Student other = (Student) obj;
- return this.age == other.age && this.name.equals(other.name);
- }
- }
创建 HashSet 集合, 存储 Student 对象
- public class HashSetDemo {
- public static void main(String[] args) {
- // 创建 HashSet 对象
- HashSet<Student> hs = new<Student> HashSet();
- // 给集合中添加自定义对象
- hs.add(new Student("zhangsan",21));
- hs.add(new Student("lisi",22));
- hs.add(new Student("wangwu",23));
- hs.add(new Student("zhangsan",21));
- // 取出集合中的每个元素
- Iterator it = hs.iterator();
- while(it.hasNext()){
- Student s = (Student)it.next();
- System.out.println(s);
- }
- }
- }
输出结果:
- Student [name=lisi, age=22]
- Student [name=zhangsan, age=21]
- Student [name=wangwu, age=23]
7. 写在后面
保证 HashSet 集合元素的唯一, 其实就是根据对象的 hashCode 和 equals 方法来决定的如果我们往集合中存放自定义的对象, 那么保证其唯一, 就必须重写 hashCode 和 equals 方法建立属于当前对象的比较方式
来源: https://www.cnblogs.com/echoing/p/8683761.html