Saul's blog
SaulJWu
2020-12-27

HashSet

# 前言

Java 集合可分为Collection 和Map 两种体系:

  • Collection接口：单列数据，定义了存取一组对象的方法的集合
    • List：元素有序、可重复的集合
      • ArrayList、LinkedList、Vector
    • Set：元素无序、不可重复的集合
      • HashSet、LinkedHashSet、TreeSet
  • Map接口：双列数据，保存具有映射关系“key-value对”的集合，也称为键值对。
    • HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

接下来学习Set接口的实现类HashSet

# 概述

  • HashSet是Set 接口的典型实现，大多数时候使用Set 集合时都使用这个实现类。

  • HashSet按Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。

# 特点

HashSet具有以下特点：

  • 不能保证元素的排列顺序
  • HashSet不是线程安全的
  • 集合元素可以是null

**HashSet 集合判断两个元素相等的标准：**两个对象通过hashCode() 方法比较相等，并且两个对象的equals() 方法返回值也相等。

对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

# 无序性

如何体现无序性？

@Test
public void test1() {
    HashSet set = new HashSet();
    set.add(456);
    set.add(123);
    set.add("AA");
    set.add("CC");
    set.add(129);
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

无序性不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。

至于哈希值等下再说。

# 不可重复性

@Test
public void test1() {
    HashSet set = new HashSet();
    set.add(456);
    set.add(123);
    //相同元素
    set.add(123);
    set.add("AA");
    set.add("CC");
    set.add(129);
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当你尝试添加相同元素，输出时发现相同元素并没有添加成功。

为什么了更深入提现不可重复性，接下来我们用一个对象来说明。

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

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

    public Person() {
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

注意这时我并没有重写equals方法，接下来测试一下，到底有几个对象：

@Test
public void test2() {
    HashSet set = new HashSet();
    set.add(new Person("Tom", 12));
    set.add(new Person("Tom", 12));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10

你会发现，你居然成功在set中添加了2个对象，这是为什么？

因为我们确实都是在堆内存中新建2个对象，它们的内存地址不一样，Set自然是，那么我现在重写equals方法，再测试一下：

直接让idea生成，先注释掉hashCode方法

@Override
public boolean equals(Object o) {
    //为了更加直观，看看到底有没有调用equals方法
    System.out.println("equals方法被调用了……");
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    Person person = (Person) o;

    if (age != person.age) return false;
    return name != null ? name.equals(person.name) : person.name == null;
}
1
2
3
4
5
6
7
8
9
10
11
12

这时再运行一次测试案例：

@Test
public void test2() {
    HashSet set = new HashSet();
    set.add(new Person("Tom", 12));
    set.add(new Person("Tom", 12));
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
1
2
3
4
5
6
7
8
9
10

输出结果：

Person{name='Tom', age=12}
Person{name='Tom', age=12}
1
2

并没有调用equals方法，这是为什么？不急，先把hashCode方法取消注释，这时再测试一次。

@Override
public int hashCode() {
    //为了更加直观，看看到底有没有调用hashCode方法
    System.out.println("hashCode被调用了……");
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}
1
2
3
4
5
6
7
8

运行测试案例，输出结果：

hashCode被调用了……
hashCode被调用了……
equals方法被调用了……
Person{name='Tom', age=12}
1
2
3
4

这时发现hashCode方法被调用了2次，equals方法调用了一次，而且集合也提现了不可重复性，那么底层到底发生了什么事情？

如果你自己来设计一个HashSet，该怎么确保不可重复性？

比如第一次添加，什么元素都没有，直接添加。

第二次添加元素，跟第一个元素比较（调用equals方法），如果不相等，才添加。

第三次添加元素，跟第一和第二个元素比较（调用equals方法），如果都不相等，才添加。

……

第1000次添加元素，岂不是要跟前面999个元素比较？这样子效率未免太低了，接下来我们看看HashSet的底层源码。

# 底层原理

# 构造

当你点开HashSet的构造方法，发现底层是一个HashMap，而点开HashMap构造方法，而HashMap是由key和value键值对组成的Node类，其中key是我们指定的对象，value是HashSet自定义的一个类。

public HashSet() {
    map = new HashMap<>();
}
1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
1
2
3
static final float DEFAULT_LOAD_FACTOR = 0.75f;
1

节点由Node类实现，这是HashMap中的内部类，有以下四个参数：

  • final int hash; 节点hash值
  • final K key; 节点的key
  • V value; 节点的value
  • Node<K,V> next; 该节点的下一节点

当HashSet使用HashMap实现时，指定元素将保存在Node的key中，而value是HashSet自定义的一个对象。

# 添加元素

向HashSet中添加元素的过程：

  • 当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据hashCode值，通过某种散列函数决定该对象在HashSet底层数组中的存储位置。
    • （这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）
    • HashMap根据元素hash值决定元素在哪个链表，算法是：(n-1)&hash。其中n是数组长度，hash是元素Hash值，得到的结果就是HashMap中数组的下标，也就决定了元素属于哪个链表。这个算法说白了就是元素Hash值除以数组长度（注意不是除以数组长度减一）然后取余
  • 如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了（可能不止一个），那么会通过链表的方式继续链接。
    • JDK7往该数组的位置的最上面链接。
    • JDK8往该数组的位置的最下面链接。
    • 一句话：七上八下。

image-20201226200325496

# 注意：

如果两个元素的equals() 方法返回true，但它们的hashCode() 返回值不相等，hashSet将会把它们存储在不同的位置，但依然可以添加成功。因为hashSet是先调用hashCode()方法，后调用equals方法。

# 小结：

HashSet底层：数组+链表的结构。

# hashCode()

哈希值在这里就是为了不用一个个比较，只有2个对象的哈希值相等时，才会去调用equals方法，这样子效率大大提高了。

所以就算是哈希值相等的2个对象，不代表2个对象属性一定相等，具体是否相等，还需要equals方法来判断。

重写hashCode() 方法的基本原则

  • 在程序运行时，同一个对象多次调用hashCode() 方法应该返回相同的值。
  • 当两个对象的equals() 方法比较返回true 时，这两个对象的hashCode() 方法的返回值也应相等。
  • 对象中用作equals() 方法比较的Field，都应该用来计算hashCode 值。

以Eclipse/IDEA为例，在自定义类中可以调用工具自动重写equals和hashCode。问题：为什么用Eclipse/IDEA复写hashCode方法，有31这个数字？

  • 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）
  • 并且31只占用5bits,相乘造成数据溢出的概率较小。
  • 31可以由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。（提高算法效率）
  • 31是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有1来整除！(减少冲突)

不太明白？来举例子：

@Override
public int hashCode() {
    //为了更加直观，看看到底有没有调用hashCode方法
    System.out.println("hashCode被调用了……");
    int result = name != null ? name.hashCode() : 0;
    result = 31 * result + age;
    return result;
}
1
2
3
4
5
6
7
8

这是刚才idea生成的hashCode方法，假设将result = 31 * result + age;改为result = result + age;，会发生什么事情？

我们已经知道在HashSet中，hashCode只是决定存放位置，假设有一个对象的返回值是：20+24 = 44，第二个对象是：24 + 20 = 44，它们的哈希值相同，所以将会调用equals方法，所以31只是为了降低哈希值相等的概率，不用去调用equals方法，提高效率。

# equals()

重写equals() 方法的基本原则：

以自定义的Person类为例，何时需要重写equals()？

  • 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候，总是要改写hashCode()，根据一个类的equals方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法，它们仅仅是两个对象。
  • 因此，违反了“相等的对象必须具有相等的散列码”。
  • 结论：复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。
帮我改善此页面 (opens new window)
#HashSet
上次更新: 2020/12/27, 05:00:47
Set
LinkedHashSet

← LinkedHashSet→

最近更新
01
zabbix学习笔记二
02-28
02
zabbix学习笔记一
02-10
03
Linux访问不了github
12-08
更多文章>
Theme by Vdoing | Copyright © 2020-2022 Saul.J.Wu | MIT License