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

2024-05-13 9356阅读

登神长阶

第十神装 HashSet

第十一神装 HashMap

👔一.哈希

🧥1.概念

🩳2.Object类的hashCode()方法:

👚3.String类的哈希码:

👠4.注意事项:

🎷二.哈希桶

🪗1.哈希桶原理

🎸2.哈希桶的实现细节

🪘3.总结

📲三.解决哈希冲突的常用方法*

💰四.HashSet

🪙1.定义

💵2.操作

💶3.特性

💷4.内部实现

💳5.应用场景

✏️五.HashMap

✒️1.定义

🖋️2.操作

🖊️3.特性

🖍️4.内部实现

🖌️5.应用场景

📝六.对比

💼七.总结与反思

👔一.哈希

🧥1.概念

在Java中，哈希（Hash）是一个广泛应用于数据结构和算法中的概念，主要用于快速查找、存储和比较数据。哈希的核心在于哈希函数（Hash Function），它将输入（通常称为键，key）映射到一个固定范围的输出值，这个输出值称为哈希值（Hash Value）或哈希码（HashCode）。哈希的目的在于将原本复杂、不规则的数据转化为简洁的、固定长度的值，使得数据的存储和检索更加高效。

🩳2.Object类的hashCode()方法:

Java中的每个对象都继承自Object类，而Object类有一个hashCode()方法，这个方法被设计用来返回对象的哈希码。默认的hashCode()实现通常基于对象的内存地址，但子类通常会重写此方法，以便根据对象的实际内容生成更有意义的哈希值，这对于使用对象作为键的哈希表操作尤为重要。

作用：
- hashCode()方法返回对象的哈希码值（哈希码），是一个int类型的整数。
- 哈希码是根据对象的内存地址或者根据对象的内容计算得到的一个唯一标识符。
- 在Java中，hashCode()方法通常与equals()方法一起使用，用于判断两个对象是否相等。
默认实现：
- 在Object类中，hashCode()方法的默认实现是根据对象的内存地址计算得到的哈希码。
- 换句话说，如果两个对象在内存中的地址不同，那么它们的哈希码也会不同。
重写规则：
- 在自定义类中，通常需要重写hashCode()方法，以便根据对象的内容来生成哈希码，而不是依赖于默认的内存地址。
- 如果重写了equals()方法，就应该同时重写hashCode()方法，保证相等的对象拥有相等的哈希码。
- 重写hashCode()方法时，应该遵循以下规则：
  1. 相等的对象必须具有相等的哈希码。
  2. 不相等的对象尽量产生不同的哈希码，以减少哈希冲突的发生。
使用场景：
- 在集合类中，如HashMap、HashSet等，hashCode()方法被用于确定对象在集合中的存储位置，加快数据的查找速度。
- 当我们需要比较自定义类的对象是否相等时，通常会重写equals()和hashCode()方法。

总之，Object类的hashCode()方法是用于获取对象的哈希码的方法，可以通过重写该方法来根据对象的内容生成哈希码，以便在集合中进行快速查找和比较。

👚3.String类的哈希码:

String类是一个典型重写了hashCode()方法的类，它根据字符串的内容计算哈希值，这意味着内容相同的字符串将拥有相同的哈希值，这有助于在哈希表中快速定位和比较字符串。

👠4.注意事项:

哈希函数应该是高效的，即计算速度快。
哈希函数应该尽量均匀分布，以减少哈希冲突。
哈希值虽然可以用于快速比较，但不保证绝对唯一，因此在判断对象相等时，除了比较哈希值外，还需要比较对象的实际内容（通过equals()方法）。

在实现自定义类的hashCode()时，应当遵守与equals()方法的一致性原则，即如果两个对象通过equals()判断为相等，它们的哈希码也必须相等。反之，哈希码相等的对象不一定通过equals()判断相等。

🎷二.哈希桶

哈希桶（Hash Bucket）是哈希表（Hash Table）中用于解决哈希冲突的一种常用方法，它是哈希表数据结构的一个重要组成部分。哈希桶是哈希表中存储元素的地方，通常是一个数组。每个桶都有一个索引，通过哈希函数计算得到的哈希值会决定元素被放置在哪个桶中。

🪗1.哈希桶原理

哈希桶解决哈希冲突的方法是，将哈希表的每个槽（或索引）扩展为一个“桶”（Bucket），这个桶本质上是一个数据结构（通常是链表、数组或其他容器），可以存储多个具有相同哈希值的元素。具体来说，当一个键通过哈希函数计算得到的索引已经有其他元素时，新的元素会被添加到这个索引对应的桶中，而不是覆盖原有的元素。

🎸2.哈希桶的实现细节

哈希函数：用于将键转换成索引。好的哈希函数能够尽量均匀地分布元素，减少冲突。
桶的实现：常用的桶实现是链表，因为链表插入和删除操作的时间复杂度较低。但在Java 8以后的HashMap中，当桶中的元素数量达到一定阈值时，会将链表转换为红黑树，以进一步优化查询性能。
负载因子：表示哈希表中已填入元素的数量与哈希表长度的比例，用于衡量哈希表的填充程度。当负载因子超过某个预设值时，哈希表会进行扩容，重新调整大小，以减少冲突，保持高效性能。
扩容：扩容通常涉及创建一个新的、更大容量的哈希表，并将原哈希表中的所有元素重新哈希到新表中。这个过程可以确保桶的平均长度减少，从而减少冲突。
冲突处理：当多个键映射到同一索引时，桶中的链表（或红黑树）结构用于存储这些冲突的键值对，并通过遍历链表（或树）来查找具体的元素。

🎹源代码模拟实现

// key-value 模型
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node[] array;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 8;//默认桶的大小
    public int put(int key, int value) {
        int index = key % array.length;
        Node cur = array[index];
        //遍历当前列表，看是否存在当前值
        while (cur != null) {
            if (cur.key == key) {
                cur.value = value;
            }
            cur = cur.next;
        }
        //若无当前值，则进行头插法
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;
        size++;
        //判断是否超载
        if (loadFactor()>=LOAD_FACTOR){
            //扩容
            resize();
        }
        return 0;
    }
    private void resize() {
        Node[] newArr=new Node[array.length*2];
        for (int i = 0; i  
🪘3.总结 
        哈希桶机制通过将冲突的元素组织在一起，而非直接覆盖，保证了哈希表的灵活性和高效性。它允许哈希表在面对大量数据时仍能保持较好的性能，尤其是在冲突较多的情况下。通过调整哈希函数、负载因子和适时的扩容，可以进一步优化哈希表的效率。在Java中，HashMap和HashSet就是使用哈希桶来实现的，它们是Java集合框架中非常重要的组件。 
📲三.解决哈希冲突的常用方法* 
        解决哈希冲突是哈希表设计中的关键环节，目的是确保即使两个或多个键通过哈希函数计算出相同的索引，也能高效地存储和检索这些键值对。以下是几种常用的解决哈希冲突的方法： 
 
1. 开放定址法（Open Addressing）

线性探测法（Linear Probing）：当发生冲突时，从冲突位置开始，沿着数组线性地检查下一个位置，直到找到一个空位。这种方法简单，但容易造成“聚集”现象，影响查找效率。
二次探测法（Quadratic Probing）：在冲突发生后，按照某种探测序列（通常是二次的，如i^2 + c）寻找下一个空位，这可以减少聚集现象。

双重散列法（Double Hashing）：使用第二个哈希函数来计算步长，当发生冲突时，按步长跳跃寻找下一个可用位置，以减少探测的顺序性。

2. 再哈希法（Rehashing）

当第一个哈希函数导致冲突时，使用第二个、第三个不同的多个哈希函数继续尝试寻找空闲位置。这种方法减少了冲突的机会，但增加了计算开销。

再哈希法通过使用一系列哈希函数不断尝试新的位置，而双重散列法则通过一个固定的步长规则在哈希表中进行探测。

3. 链地址法（Separate Chaining）

每个哈希表的索引位置对应一个链表或其它动态数据结构（如红黑树，Java 8中HashMap的实现）。当发生冲突时，将新的元素添加到该索引位置的链表中。这种方法简单且灵活，但链表过长时会降低查找效率。

4. 建立公共溢出区（Overflow Area）

这种方法将哈希表分为两个部分：基本表和溢出表。当基本表中的位置已满时，冲突的元素被放置在溢出表中。这种方式实现简单，但效率不如链地址法。

5. 开散列法（Open Hashing）*

这是一种特殊的链地址法，哈希表本身是一个指针数组，每个元素指向一个链表的头节点。这种方法强调了链表的独立性，便于管理和扩展。

负载因子调整

无论采取哪种冲突解决策略，维护一个合理的负载因子（已用单元数与总单元数的比例）至关重要。当负载因子超过某个阈值时，通常会触发哈希表的扩容操作，通过增大哈希表的大小并重新分配所有元素来减少冲突，保持高效的查找性能。

每种方法都有其优势和劣势，实际应用时需根据具体需求和数据特点选择最适合的冲突解决策略。例如，对于内存充足的场景，链地址法因其实现简单且效果稳定而常用；而在内存受限或查找性能要求极高的场景下，开放定址法或再哈希法可能更为合适。

💰四.HashSet

此部分建议，对照上一篇来学习 Java 【数据结构】 TreeSet&TreeMap（二叉搜索树详解）【神装】

🪙1.定义

Java中的HashSet是一个实现了Set接口的集合类，它提供了一种存储不可重复元素的高效数据结构。HashSet的实现基于HashMap，这意味着它内部使用了哈希表来管理元素，这使得HashSet能够提供快速的插入、删除和查找操作。以下是关于HashSet的一些关键特性和内部工作原理的详细说明：

💵2.操作

方法	解释
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断 o 是否在集合中
Iterator iterator()	返回迭代器
boolean remove(Object o)	删除集合中的 o
int size()	返回set中元素的个数
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
Object[] toArray()	将set中的元素转换为数组返回
boolean containsAll(Collection c)	集合c中的元素是否在set中全部存在，是返回true，否则返回 false
boolean addAll(Collection

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

👔一.哈希

🧥1.概念

🩳2.Object类的hashCode()方法:

👚3.String类的哈希码:

👠4.注意事项:

🎷二.哈希桶

🪗1.哈希桶原理

🎸2.哈希桶的实现细节

💰四.HashSet

🪙1.定义

💵2.操作

相关阅读

美国顶级VPS下载体验，速度与稳定性惊艳之选！

FX VPS视频教程详解，轻松打造高效虚拟专用服务器！

VPS下行流量全解析，概念、作用与重要性，一文掌握！

斯蒂卡VPS品质深度解析，究竟有何过人之处？

目录[+]