Java 【数据结构】 哈希（Hash超详解）HashSet&HashMap【神装】

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以此来加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫散列表。

哈希表有多种不同的实现方式，但是在所有的实现中，都需要解决以下两个核心问题：

1. 哈希码的计算：如何为一个对象计算其哈希码？
2. 碰撞处理：如果两个对象的哈希码相同，该如何处理？

在Java中，每个对象都有自己的hashCode()方法，用于返回该对象的哈希码。哈希码是一个用于表示对象身份的整数，在哈希表中，相同对象的哈希码应该是相同的。

HashMap和HashSet都是基于哈希表的数据结构，HashMap用于存储键值对，HashSet用于存储不重复的元素。

1. HashMap

   HashMap内部是用一个数组来存放元素，元素存放的位置由键值对的键的哈希码决定。如果两个键的哈希码相同，那么它们会被放在数组的同一个位置，并形成一个链表。

HashMap<Integer, String> map = new HashMap<>();
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");

2. HashSet

   HashSet内部也是用一个数组来存放元素，元素存放的位置由元素自身的哈希码决定。如果两个元素的哈希码相同，那么它们会被放在数组的同一个位置，并形成一个链表。

HashSet<String> set = new HashSet<>();
set.add("One");
set.add("Two");
set.add("Three");

在Java中，对象的equals方法和hashCode方法都是配套使用的。当我们重写一个对象的equals方法时，通常需要重写其hashCode方法，以保证当两个对象通过equals方法比较返回true时，它们的hashCode值也应该相同。

public class Person {
    private int id;
    private String name;
 
    // 构造方法、getter和setter省略
 
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id &&
               Objects.equals(name, person.name);
    }
 
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

在上述的Person类中，我们重写了equals方法，用于比较两个Person对象是否相等，同时我们还重写了hashCode方法，用于返回该对象的哈希码。在hashCode方法中，我们使用了Objects类的hash方法，它可以为多个字段生成一个哈希码，这样可以确保当两个Person对象的id和name都相等时，它们的哈希码也是相等的。这样一来，当我们将Person对象放入HashSet或者作为HashMap的键时，可以更加高效地存储和检索数据。