从根到叶：深度理解哈希表

冷不防 2024-04-26 01:39 6阅读 0赞

### ![7ae07e55483d4f3d9caf69c991145bf3.png][] ###

###  ###

### 一.哈希表的概念 ###

**关于查找元素时：**

**在顺序结构以及平衡树** 中，元素关键码与其存储位置之间没有对应的关系，因此在 **查找一个元素时，必须要经过关键** **码的多次比较** 。 **顺序查找时间复杂度为** **O(N)** **，平衡树中为树的高度，即** **O( log2 N** **)** ，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以 **不经过任何比较，一次直接从表中得到要搜索的元素** 。  **如果构造一种存储结构，通过某种函**  **数** **(hashFunc)** **使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快** **找到该元素** 。

**哈希表（Hash Table:**哈希表是一种使用哈希函数进行键值映射的数据结构，它将键（key）和值（value）存储在一起。它的内部实现是一个固定大小的数组，数组的每个位置被称为存储桶（bucket）或槽（slot）,以实现高效的数据查找和插入操作。

**在哈希表的用途**：

哈希表是一种常见且广泛应用的数据结构，它在许多领域和应用中发挥着重要作用。以下是哈希表的一些常见用途：

1.  **查找和检索**：哈希表能够提供快速的查找和检索操作。通过将键映射到哈希表的存储桶中，可以在常数时间复杂度内找到所需的数据。这使得哈希表非常适用于需要快速查找和检索数据的场景。
2.  **字典和关联数组**：哈希表常被用作字典或关联数组的实现。通过将键值对存储在哈希表中，可以根据键快速查找对应的值。这在许多编程语言中的字典数据结构中得到广泛应用。
3.  **数据索引**：哈希表可以用于构建快速的数据索引。将索引关键字映射到哈希表的存储桶中，可以在索引数据集时快速定位和检索数据。
4.  **数据唯一性检查**：哈希表可以用于快速检查数据的唯一性。通过将数据的哈希值作为键存储在哈希表中，可以快速判断数据是否已存在。

### 二.了解哈希函数 ###

**哈希函数**是一种将输入数据（例如字符串、数字等）映射为固定长度的哈希值（hash value）的函数。哈希函数将任意大小的输入转换为固定大小的输出，通常是一个整数或固定长度的字符串。不同的哈希函数在设计和实现上可能会有一些区别。

#### 2.1直接定址法 ####

直接定址法是一种简单的哈希函数，它将输入数据直接映射到哈希值的范围。具体来说，对于给定的输入，直接定址法使用输入值作为哈希值，不经过其他复杂的计算。

**使用公式**：**hash(key) = (A \* key + B) % M**

其中

*  hash(key) 是输入数据 x 的哈希值
 *  A和B是常数，用于调整哈希函数的映射方式
 *  M 是哈希表的大小，用于取模运算，确保哈希值在合适的范围内

举例子解释：

假设我们有一个哈希表，大小为10，我们希望将输入的整数映射到该哈希表中。

输入的整数：5，12，21

使用了常数 A= 3 和 B = 2 来说明直接定址法的哈希函数。这些常数的选择是任意的，可以根据具体的需求和情况进行调整。

如下图所示：

![21a04c866642433d9d06e29fd72b9b8f.png][]

**直接定址法作为一种哈希函数，具有以下优点和缺点**：

**优点：**

*  **简单快速**：直接定址法的计算过程非常简单，只需将输入数据直接转换为哈希值，没有复杂的计算步骤，因此计算速度非常快。
 *  **低冲突率**：由于每个输入数据都有唯一的哈希值，冲突的概率非常低。在哈希表大小和输入数据范围匹配的情况下，冲突几乎是不会发生的。

**缺点：**

*   **依赖数据范围**：直接定址法要求输入数据的范围与哈希表的大小相匹配，如果数据范围过大或过小，可能会导致哈希冲突或者浪费存储空间。
 *  **分布不均匀**：如果输入数据的分布不均匀，某些哈希值可能会被频繁使用，而其他哈希值很少使用，导致哈希表的性能下降。
 *  **冲突解决困难**：直接定址法在处理冲突时比较困难，因为不同的输入可能会映射到相同的哈希值。当出现冲突时，需要采取额外的措施解决，如链地址法或开放定址法。

--------------------

#### 2.2**除留余数法** ####

除留余数法（Modulo Division Method）是一种常用的哈希函数方法，用于将输入数据映射到哈希表中的位置。**它基于取模运算的性质，将输入数据除以哈希表的大小（通常为素数），并取余数作为最终的哈希值。**

**公式：hash(key) = key % capacity**; capacity为存储元素底层空间总的大小。

例子如下：

![10047b54b9764c739641ebf1cd7b04e7.png][]

除留余数法作为一种哈希函数方法，具有以下优点和缺点：

**优点：**

*  **简单高效**：除留余数法的计算过程非常简单，只需进行一次取模运算即可得到哈希值，计算速度非常快。
 *  **均匀分布**：当哈希表大小 M 为素数时，除留余数法可以获得较好的哈希值分布。素数的选择可以降低冲突的概率，使得哈希值在哈希表中更均匀地分布。

**缺点：**

*  **冲突率受限**：除留余数法在处理冲突时的灵活性有限。由于哈希值的范围受限于哈希表的大小，当输入数据之间存在关联性或者哈希表大小较小的情况下，冲突的概率可能会增加。
 *  **数据分布依赖**：除留余数法对输入数据的分布敏感。如果输入数据集的分布不均匀，一些哈希值可能会频繁出现，而其他哈希值则很少使用，导致哈希表的性能下降。
 *  **限制于素数**：为了获得较好的哈希值分布，除留余数法通常建议选择素数作为哈希表的大小。然而，素数的选择可能会受到限制，特别是在某些特定的应用环境中。

--------------------

#### 2.3平方取中法（了解） ####

平方取中法（Mid-square Method）是一种哈希函数方法，用于将输入数据映射到哈希表中的位置。它基于对输入数据的平方运算，并提取中间部分作为最终的哈希值。

使用以下步骤：

1.  将输入数据 x 平方：y = x^2
2.  提取中间部分作为哈希值：取 y 的中间部分作为最终的哈希值。

具体提取中间部分的方式可以根据需求和数据范围进行选择。常见的方法包括：

*  取中间 k 位：如果 y 是一个多位数，可以取 y 中间的 k 位作为哈希值。
 *  取中间 k 位后再取模：可以先取 y 中间的 k 位，然后再对其进行取模运算，以确保哈希值在合适的范围内。

例如，假设我们有一个三位数的输入数据 x = 123，我们可以使用平方取中法来计算其哈希值：

1. 平方：y = 123^2 = 15129  
2. 提取中间两位：哈希值为 51

平方取中法作为一种哈希函数方法，具有以下优点和缺点：

**优点：**

*  **简单易实现**：平方取中法的实现较为简单，只需进行平方运算和提取中间部分的操作。
 *  **较好的分布性**：当输入数据分布均匀时，平方取中法可以获得较好的哈希值分布，减少冲突的概率。

**缺点：**

*  **数据分布依赖**：平方取中法对输入数据的分布敏感。如果输入数据集的分布不均匀，一些哈希值可能会频繁出现，而其他哈希值则很少使用，导致哈希表的性能下降。
 *  **冲突率受限**：平方取中法的冲突率受限于平方操作和中间部分的提取方式。在某些情况下，平方取中法可能会导致较高的冲突率，特别是在数据范围较大时。
 *  **哈希值范围限制**：平方取中法的哈希值范围受限于输入数据的位数和中间部分的提取方式。如果哈希表的大小超过了哈希值的范围，可能会导致哈希值无法充分覆盖哈希表的索引。

--------------------

#### 2.4折叠法（了解） ####

折叠法（Folding Method）是一种哈希函数方法，用于将输入数据划分为固定大小的块，然后对这些块进行相加或位运算，以获得最终的哈希值，**折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况**

折叠法的使用步骤：

1.  **划分块**：将输入数据分成固定大小的块，例如每个块包含4位。
2.  **相加或位运算**：对每个块进行相加或位运算操作，例如将每个块的位相加。
3.  **最终哈希值**：将所有中间结果组合在一起，得到最终的哈希值。

例子如下：

假设我们有一个输入数据为 987654321，我们可以使用折叠法来计算其哈希值。

1. 划分块：将输入数据分成固定大小的块，例如每个块包含3位。  
输入数据：987654321  
分块结果：987 654 321

2. 相加或位运算：对每个块进行相加或位运算操作，例如将每个块的位相加。  
分块结果：987 654 321  
相加结果：9 + 8 + 7 = 24，6 + 5 + 4 = 15，3 + 2 + 1 = 6

3. 最终哈希值：将所有中间结果组合在一起，得到最终的哈希值。  
中间结果：24 15 6  
最终哈希值：24156

通过折叠法，我们将输入数据 987654321 映射到了哈希值 24156。

**优点：**

1.  **简单易实现**：折叠法的实现相对简单，只需要将输入数据划分为块并进行相加或位运算。
2.  **适用性广泛**：折叠法可以适用于不同长度的输入数据，通过划分块和操作方式的灵活选择，可以处理各种数据类型和大小的输入。

**缺点：**

1.  **块的选择问题**：折叠法的效果受到块的大小和选择方式的影响。选择不合适的块大小可能导致冲突率增加或哈希值分布不均匀。
2.  **数据依赖性**：折叠法对输入数据的分布敏感，如果输入数据的分布不均匀，可能会导致一些哈希值频繁出现，而其他哈希值很少使用，降低哈希表的性能。
3.  **哈希值范围限制**：折叠法的哈希值范围受到块的大小和操作方式的限制。如果哈希表的大小超过了哈希值的范围，可能会导致哈希值无法充分覆盖哈希表的索引。

#### 2.5**随机数法**(了解)  ####

随机数法（Randomized Hashing）是一种哈希函数方法，通过使用随机数来计算哈希值。在随机数法中，每个输入数据都会与一个随机数进行组合，并通过某种哈希函数来计算最终的哈希值，**随机数法常用于加密和安全领域，以及需要高度随机性和分布均匀的哈希值的场景。**

随机数法的使用步骤：

1. **选择随机数**：从一个随机数生成器中选择一个随机数。  
2. **输入数据与随机数组合**：将输入数据与随机数进行组合，可以简单地将它们连接在一起，形成一个新的字符串。  
3. **哈希函数计算**：使用某种哈希函数对组合后的字符串进行计算，得到最终的哈希值

举例子如下：

假设我们有一个输入数据为 "Hello, World!"，我们可以使用随机数法来计算其哈希值。

1. 选择随机数：从一个随机数生成器中选择一个随机数，例如选择随机数为 987654321。  
2. 输入数据与随机数组合：将输入数据与随机数进行组合，形成一个新的字符串。  
输入数据：Hello, World!  
随机数：987654321  
组合结果：Hello, World!987654321

3. 哈希函数计算：使用某种哈希函数对组合后的字符串进行计算，得到最终的哈希值。  
哈希函数：SHA-256（安全哈希算法-256位）  
哈希值：d0e8c2e3f1b9a27a8e2b26a410baea6f4a6e8a4d9b3c6e9e4c8a1b7c8a3d6b7

通过随机数法，我们将输入数据 "Hello, World!" 映射到了哈希值 "d0e8c2e3f1b9a27a8e2b26a410baea6f4a6e8a4d9b3c6e9e4c8a1b7c8a3d6b7"。每次使用不同的随机数，都会得到不同的哈希值，增加了哈希值的随机性和分布性。

**优点**：

1.  **高度随机性**：使用随机数可以增加哈希值的随机性，降低冲突的概率。
2.  **哈希值分布均匀**：通过随机数的引入，可以获得更均匀的哈希值分布。

**缺点**：

1.  **随机数生成开销**：每次计算哈希值都需要生成一个随机数，这可能会带来一定的计算开销。
2.  **难以重现哈希值**：由于使用的随机数是不可预测的，难以在重现哈希值的场景中使用。

--------------------

#### 2.6数字分析法（了解） ####

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某 些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：

![1821f08da9934cd0970ec43edbf98d85.png][]

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前 7 位都是 相同的，那么我们可以 选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转( 如 1234改成 4321) 、右环位移 ( 如 1234 改成 4123) 、左环移位、前两数与后两数叠加 ( 如 1234 改成 12+34=46) 等方法。

**数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均** **匀的情况。**

**注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突**

--------------------

### 三.哈希冲突 ###

#### 3.1了解哈希冲突 ####

哈希冲突是指在使用哈希函数时，两个或多个不同的输入值产生了相同的哈希值。换句话说，哈希函数将不同的输入映射到了相同的输出。

如下例子：

![23a842b2faa64821b507753a6c443265.png][]

我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，**冲突的发生是必然的** ，但我们能做的应该是尽量的 **降低冲突率** 。

引起哈希冲突的一个原因可能是： **哈希函数设计不够合理** 。

**哈希函数设计原则** ：

*  **哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间** 
 *  **哈希函数计算出来的地址能均匀分布在整个空间中** 
 *  **哈希函数应该比较简单**

**冲突-避免-负载因子调节**

负载因子（Load Factor）是指哈希表中已存储元素数量与哈希表总容量之间的比率关系。**它用来衡量哈希表的填充程度。**

负载因子通常用公式表示为：负载因子 = 已存储元素数量 / 哈希表总容量

例如，如果哈希表中已存储了100个元素，而哈希表的总容量为200，那么负载因子为 100/200 = 0.5。

![dacb646ee059467f88230e65e92eb10a.png][]

**负载因子和冲突率的关系粗略演示：**

![2575ba183df04e4fb9557fcedf410c23.png][]

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。

**已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。**

--------------------

#### 3.2 线性探测-解决哈希冲突 ####

线性探测一种解决哈希冲突的开放寻址法方法之一。当发生哈希冲突时，线性探测会尝试在哈希表中的下一个空槽中查找可用的位置。

具体来说，当要插入一个元素到哈希表中，并且发现目标槽已经被占用时，线性探测会按照一定的规则依次检查下一个槽，直到找到一个空槽或者遍历了整个哈希表。通常，线性探测的规则是顺序地检查下一个槽，即向后移动一个位置。

例子如下：

哈希冲突-线性探测法

**优点：**  
1. **实现简单**：线性探测是一种简单直观的解决哈希冲突的方法，易于实现和理解。  
2**. 内存局部性**：线性探测具有较好的内存局部性，即相邻的元素在哈希表中也会相邻存储。这在一定程度上可以提高缓存的命中率，减少内存访问的开销。

**缺点：**  
1. **聚集性问题**：线性探测可能导致聚集性问题，即连续的哈希冲突会导致连续的元素聚集在一起。这会导致哈希表中出现长串的连续占用的槽位，称为"聚集"。聚集会降低查找、插入和删除操作的效率，因为需要线性地探测较长的距离才能找到空槽。  
2. **高负载因子敏感**：线性探测对于高负载因子（填充程度高）敏感。当哈希表的负载因子接近或超过1时，发生冲突的概率会增加，导致线性探测的效率下降，聚集性问题更加明显。  
3. **删除操作复杂**：线性探测中的删除操作相对复杂，因为删除一个元素后，后续的元素可能会被移动到前面的位置以填补空缺。这会导致查找操作更加复杂，需要额外的逻辑来处理元素的迁移。

--------------------

#### 3.3 二次探测-解决哈希冲突 ####

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，而找到下次探测的方法是：

![ed81b4324f12442a91fc69e1365fadc0.png][]

举例子如下：

哈希冲突-二次探测法

**优点：**  
1. **减少聚集性问题**：相比于线性探测，二次探测能够更均匀地分布元素，减少聚集性问题。这意味着元素在哈希表中的分布更加均匀，减少了长串连续占用的槽位，提高了查找和插入操作的效率。  
2. **较简单的实现**：相对于其他开放寻址法方法（如双重哈希），二次探测的实现较为简单，不需要额外的哈希函数。

**缺点：**  
1. **探测序列不完整**：二次探测可能导致探测序列不完整，即某些槽位永远不会被访问到。这是因为二次探测使用的二次函数只能探测到特定的位置，可能无法遍历整个哈希表，导致某些槽位永远不会被使用。  
2. **聚集性问题仍可能存在**：尽管相对于线性探测，二次探测能够减少聚集性问题，但在高负载因子下仍可能出现聚集。当哈希表填充程度较高时，依然存在连续的哈希冲突，导致元素聚集在一起，影响操作的效率

**注意：**

当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不

会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a 不超过 0.5，如果超出必须考虑增容。因此，**比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。**

--------------------

#### 3.4哈希桶-解决哈希冲突 ####

哈希桶：开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

如下图展示：

![c372f0494c1f4e1fa6658f37da805896.png][]

![e76e0f2cfc99414eb39187b268deed89.png][]

从上图可以看出，开散列中每个桶中 **开散列，可以认为是把一个在大集合。**

哈希桶（散列表）的代码的实现：

package HashBucket;
    
    public class hashBucket {
        static class Node{
            public int key;
            public int val;
            public Node next;
            public Node(int key,int val){
                this.key = key;
                this.val = val;
            }
    
        }
        public Node[]  array;//哈希链表
        public int usedSize;//存放多少个数据
        public float loadFactor = 0.75f;
    
        public hashBucket(){
            array = new Node[10];
        }
    
        public void put(int key,int val){
            int index = key % array.length; // 计算key在数组中的索引位置
            //遍历index下标的链表,是否存在key,存在就更新value,不存在就头插法
            Node cur = array[index];//array[index]是一个结点
            while (cur != null) { // 遍历链表
                if (cur.key == key) { // 如果当前节点的key与目标key相等
                    cur.val = val; // 更新节点的value值
                    return;
                }
                cur = cur.next; // 继续遍历下一个节点
            }
            // 链表遍历完成，未找到目标key，执行插入操作
    
            Node node = new Node(key, val); // 创建一个新的节点，存储目标key和value
            node.next = array[index]; // 将新节点的next指向当前索引位置的链表头节点
            array[index] = node; // 将新节点设为当前索引位置的链表头节点
            usedSize++; // 更新已使用的大小
            if(doLoadFactor()> 0.75){
                //进行扩容
                resize();
            }
        }
    
        private void resize(){
            Node[]  newArray =  new Node[2* array.length];
            //遍历原来的数组
            for (int i = 0; i < array.length; i++) {
                Node cur = array[i];
                while(cur!=null){
                    Node tmp = cur.next;
                    int newIndex = cur.key % newArray.length;
                    //采用头插法 插入到新数组的 newIndex下标
                    cur.next = newArray[newIndex];
                    newArray[newIndex] = cur;
                    cur = tmp;
                }
            }
        }
        private float doLoadFactor(){
            return usedSize * 1.0f/ array.length;
        }
    
        public int get(int key){
            int index = key % array.length;
            Node cur = array[index];
            while(cur!=null){
                if(cur.key == key){
                    return cur.val;
                }
                cur = cur.next;
            }
            return -1;
    
    
        }
    
    
    }

视频展示如下：

哈希散列表-put方法演示

--------------------

**补充知识点：当散列表扩容时需要注意的事项**

哈希散列表扩容时-注意点(tmp的存在)

**1.为什么要用到tmp存放cur.next  
因为党cur结点移动到新的索引址后,cur.next就存放的是在同一个索引值的下标的地址了,导致原来的就丢失了**

**2,扩容时需要注意什么:  
应当对当时的结点进行遍历,然后放到合适的数组下标,比如没扩容之前元素14放在4下标,扩容之后应当放到数组14下标的位置(往后放)**

--------------------

#### 3.5哈希桶<K,V>模型 ####

假设现在定义在`hashBucket2`类中，通过定义泛型 `<K, V>`，允许存储任意类型的键（Key）和值（Value）对象。

在`put`方法中，通过传入键（`K key`）和值（`V val`）的参数，可以将键值对存储到散列表中。在创建新的节点时，使用传入的键和值来构造一个`Node<K, V>`对象，并将其插入到对应桶的链表头部。

**hashBucket2类**实现的代码如下：

package HashBucket;
    
    public class hashBucket2<K, V> {
        static class Node<K, V> {
            public K key; // 节点的键
            public V val; // 节点的值
            public Node<K, V> next; // 下一个节点的引用
    
            public Node(K key, V val) {
                this.key = key;
                this.val = val;
            }
        }
    
        public Node<K, V>[] array; // 桶数组
        public int usedSize; // 已使用的桶数量
        public static final float DEFAULT_LOAD_FACTOT = 0.75f; // 默认装载因子
    
        public hashBucket2() {
            array = (Node<K, V>[]) new Node[10]; // 初始化桶数组，初始大小为10
        }
    
        public void put(K key, V val) {
            int hash = key.hashCode() % array.length; // 计算键的哈希码，并对桶数组长度取模，得到桶的索引
            int index = hash % array.length; // 计算桶的索引
            Node<K, V> cur = array[index]; // 获取桶对应的链表头节点
            while (cur != null) {
                if (cur.key.equals(key)) {
                    // 键已存在，更新值
                    cur.val = val;
                    return;
                }
                cur = cur.next; // 继续遍历下一个节点
            }
            Node<K, V> node = new Node(key, val); // 创建新的节点
            node.next = array[index]; // 将新节点的next指向桶的原头节点
            array[index] = node; // 将新节点设为桶的头节点，实现头插法
            usedSize++; // 更新已使用的桶数量
        }
    
        public V get(K key) {
            int hash = key.hashCode(); // 计算键的哈希码
            int index = hash % array.length; // 计算桶的索引
            Node<K, V> cur = array[index]; // 获取桶对应的链表头节点
            while (cur != null) {
                if (cur.key.equals(key)) {
                    // 找到与键匹配的节点，返回对应的值
                    return cur.val;
                }
                cur = cur.next; // 继续遍历下一个节点
            }
            return null; // 未找到匹配的键，返回null
        }
    }

**提示**：Java中的泛型允许在运行时使用任意类型的对象，因此可以存储各种类型的对象

**Test类**的实现的代码如下：

package HashBucket;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Objects;
    
    class Student{
        String id;
        public  Student(String id){
            this.id = id;
        }
    
        //会根据id生产hashcode
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return Objects.equals(id, student.id);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(id);
        }
    }
    public class Test {
        public static void main(String[] args) {
            Student student1 = new Student("563342523");
            Student student2 = new Student("563342523");
            hashBucket2<Student,Integer> hashbucket2 = new hashBucket2<>();
            hashbucket2.put(student1,20);
            //通过存入student1对象，可以查看student2的val，因为在相同位置
            Integer val = hashbucket2.get(student2);
            System.out.println("Value for student2: " + val);
    
        }
    }

这里主要介绍的是(重点)：当需要自定义相等性比较和哈希码计算时，必须重写`equals`和`hashCode`方法，以确保对象在比较和存储时的一致性和正确性。重写这两个方法可以根据对象的内部状态来确定相等性，并为相等的对象生成相同的哈希码，使它们能够正确地在散列表中进行操作。

比如在给定的代码中，**Studentb重写了equals和hashCode方法**，根据id字段来判断对象的相等性和计算哈希码。由于student1和student2的id字段值相同，根据equals方法的逻辑，它们被认为是相等的对象。

当student1作为键存入散列表时，散列表会根据hashCode方法计算出哈希码，并将键值对存储在相应的桶位置。

接下来，当使用student2作为键调用散列表的get方法时，散列表会根据hashCod方法计算出student2的哈希码，并在相应的桶位置进行查找。由于student1和student2的哈希码相同，根据散列表的逻辑，它们会被认为是相等的键。

运行如下：

![b400cb118b5949299ad58b98334e69d6.png][]

如果**没有重写equals和hashCode方法：**

package HashBucket;
    
    import java.util.HashMap;
    
    class Student {
        String id;
    
        public Student(String id) {
            this.id = id;
        }
    }
    
    public class Test {
        public static void main(String[] args) {
            Student student1 = new Student("563342523");
            Student student2 = new Student("563342523");
    
            HashMap<Student, Integer> map = new HashMap<>();
            map.put(student1, 20);
    
            // 由于没有重写 hashCode() 和 equals() 方法，student1 和 student2 被视为不同的对象
            // 所以无法通过 student2 获取相应的值
            Integer val = map.get(student2);
            System.out.println(val);  // 输出: null
        }
    }

`Student` 类未重写 `hashCode()` 和 `equals()` 方法。因此，尽管 `student1` 和 `student2` 的ID相同，它们被视为不同的对象。当试图使用 `student2` 作为键来获取值时，由于哈希表中的键不匹配，返回的值为 `null`。

### 四.五道相关例题 ###

1.[只出现一次的数字][Link 1]

解题思路：判断元素是否存在于集合中，来找出只出现一次的元素。在第一次遍历时，将出现过的元素添加到集合中，如果遇到重复元素则移除。最后在第二次遍历时，找出集合中剩下的唯一元素并返回。

力扣-只出现一次的数字

--------------------

2.[138. 随机链表的复制 - 力扣（LeetCode）][138. _ - _LeetCode]

解题思路：

1.  创建一个 `HashMap`（哈希映射）用于存储原节点和复制节点的对应关系。键为原节点，值为复制节点。
2.  第一次遍历原链表，创建新的复制节点，并将原节点和复制节点的对应关系存储在 `map` 中。
3.  第二次遍历原链表，根据 `map` 中存储的对应关系，修改每个复制节点的 `next` 指针和 `random` 指针。
    
     *  通过 `map.get(cur)` 获取当前原节点对应的复制节点。
     *  将复制节点的 `next` 指针指向原节点的 `next` 节点的复制节点。
     *  将复制节点的 `random` 指针指向原节点的 `random` 节点的复制节点。
4.  返回复制链表的头节点，即 `map.get(head)`。

力扣-复制带随机指针的链表

--------------------

3.[771. 宝石与石头 - 力扣（LeetCode）][771. _ - _LeetCode]

解题思路：

1.  创建一个 `HashSet`（哈希集合）用于存储宝石的字符。
2.  遍历宝石字符串 `jewels` 的每个字符 `ch`，将其添加到 `hashset` 中。
3.  初始化一个计数器 `count` 为 0。
4.  遍历石头字符串 `stones` 的每个字符 `ch`，如果 `hashset` 包含字符 `ch`，则增加 `count` 的值。
5.  返回计数器 `count` 的值，即宝石字符串在石头字符串中出现的次数。

力扣-石头与宝石

--------------------

4. [旧键盘 (20)\_\_牛客网 (nowcoder.com)][_20_ _nowcoder.com]

解题思路：

1.  在循环体内，通过`in.nextLine()`分别获取两行输入字符串，分别赋值给`string1`和`string2`。
2.  调用`func(string1, string2)`方法，并将获取的两个字符串作为参数传递给该方法。
3.  `func`方法的作用是将`str1`中不在`str2`中出现的字符打印出来。
4.  首先创建一个`HashSet`集合`set`，用于存储`str2`中的字符（转换为大写形式）。
5.  然后创建另一个`HashSet`集合`set2`，用于存储已经打印过的字符。
6.  遍历`str1`中的每个字符（转换为大写形式），如果该字符既不在`set`中，也不在`set2`中，则打印该字符，并将其添加到`set2`集合中。
7.  循环结束后，程序继续等待下一组输入，直到没有更多的输入行。

--------------------

5.[692. 前K个高频单词 - 力扣（LeetCode）][692. _K_ - _LeetCode]

解题思路（这个较为复杂 ）：

首先，通过遍历words数组，使用HashMap统计每个单词出现的次数，并将其存储在map中，其中单词作为键，出现次数作为值。

接下来，创建一个小根堆minHeap来存储出现次数最高的k个单词。小根堆中的元素是Map.Entry<String, Integer>类型，表示单词和对应的出现次数。小根堆的大小始终保持在k以内。

通过自定义的比较器（Comparator），将minHeap构建为小根堆。在比较器中，首先比较单词出现次数，如果出现次数相同，则按照字典序进行比较，以满足题目要求。

遍历map的每个键值对，如果minHeap的大小小于k，则直接将当前键值对加入minHeap中。否则，取出堆顶元素（出现频率最小的单词），与当前键值对进行比较。如果当前键值对的出现频率比堆顶元素大，就将堆顶元素移除，并将当前键值对加入堆中。如果出现频率相同，根据字典序进行比较，如果当前单词字典序较小，也进行堆的更新。

最后，从小根堆中取出k个频率最高的单词，并按照它们在堆中的顺序存储在result列表中，返回结果。

小根堆的使用是为了维护出现频率最高的k个单词，通过比较和堆的更新操作，保持堆中始终存储频率最高的k个单词。这样，在遍历完整个map后，堆中保留的就是出现频率最高的k个单词，而且按照题目要求的字典序排列。

### 五.总结 ###

1. HashMap  和  HashSet  即  java  中利用哈希表实现的  Map  和  Set

2. java  中使用的是哈希桶方式解决冲突的

3. java  会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

4. java  中计算哈希值实际上是调用的类的  hashCode  方法，进行  key  的相等性比较是调用  key  的  equals  方 法。所以如果要用自定义类作为 HashMap  的  key  或者  HashSet  的值， **必须覆写**  **hashCode**  **和**  **equals**  **方** **法** ，而且要做到  equals  相等的对象， hashCode  一定是一致的。

**学习笔记：**

**1.为什么HashMap打印时有时不是按顺序的  
因为key % 数组长度，根据关键字给算出对应的位置，而我们不知道。**

**2.为什么不用fori循环输出  
因为hash的放的位置并不是按数组的下标计算的**

**3.为什么Haspmap<Student,Interger> map = new Hash<>();(Student是自定义的类)不报错  
因为Haspmap是不会进行比较key，放null也是可以的**

**4.为什么HashSet存放相同的key，输出只有只有一个  
因为Hash的底层是一个HashMap，是可以去重的，每次存储元素的时候，默认的value其实就是一个Object对象**

**5.注意自定义类型比较要用equal而不是" == "，put方法和get方法中提到**

**6.建议以后在写自定义对象的时候，最好自己实现一下equals和hashcode，最好也把toString也写一下**

**7.hashBucket<V，K> -> 引用类型的hash桶**

**8.hashset的底层还是hashmap**

**结语：**

哈希函数是一种将输入数据映射为固定大小哈希值的算法，用于在哈希表中实现高效的数据查找、插入和删除。哈希冲突是指不同的输入数据经过哈希函数计算后得到相同的哈希值，这可能导致数据存储冲突和性能下降。为了解决哈希冲突，常用的方法包括开放寻址法和链表法，它们能够有效地处理冲突并保证哈希表的性能。哈希函数、哈希表和解决哈希冲突的方法在实现数据结构和算法中发挥着重要作用。

![146026246a6f408396d600cd45b08a7e.png][]

[7ae07e55483d4f3d9caf69c991145bf3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/d52225e5208c4fdeb9660925feb55f1c.png
[21a04c866642433d9d06e29fd72b9b8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2b0a7bef10094512b209082292346e41.png
[10047b54b9764c739641ebf1cd7b04e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/99579c16fc3b471480669b5476c2bce7.png
[1821f08da9934cd0970ec43edbf98d85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/bf9fe91ac1a0409cb3a1a2fd9d61125f.png
[23a842b2faa64821b507753a6c443265.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0960f6ff9a054542a367f05d41350159.png
[dacb646ee059467f88230e65e92eb10a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/4adaddf3277440f099fbe43cc492988b.png
[2575ba183df04e4fb9557fcedf410c23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8ed0521b095c48c7b85ffec10a86a9b2.png
[ed81b4324f12442a91fc69e1365fadc0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f126458c2cd34958beafdd817b82394b.png
[c372f0494c1f4e1fa6658f37da805896.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f48624da5b8146689eaddeaff795fe32.png
[e76e0f2cfc99414eb39187b268deed89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/932cf35938c24e4694ea407e721a7b95.png
[b400cb118b5949299ad58b98334e69d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6772522d69e041d999b125b4ad036cb0.png
[Link 1]: https://leetcode.cn/problems/single-number/description/
[138. _ - _LeetCode]: https://leetcode.cn/problems/copy-list-with-random-pointer/description/
[771. _ - _LeetCode]: https://leetcode.cn/problems/jewels-and-stones/description/
[_20_ _nowcoder.com]: https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
[692. _K_ - _LeetCode]: https://leetcode.cn/problems/top-k-frequent-words/description/
[146026246a6f408396d600cd45b08a7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/a5adb95673194a3f8afe340eedd171bf.png