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

news/2024/5/26 20:00:22/文章来源:https://blog.csdn.net/LHY537200/article/details/136690617

​​​​​​​

一.哈希表的概念

关于查找元素时:

在顺序结构以及平衡树 中,元素关键码与其存储位置之间没有对应的关系,因此在 查找一个元素时,必须要经过关键 码的多次比较 顺序查找时间复杂度为 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 来说明直接定址法的哈希函数。这些常数的选择是任意的,可以根据具体的需求和情况进行调整。

如下图所示:

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

优点:

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

缺点:

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

2.2除留余数法

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

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

例子如下:

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

优点:

  • 简单高效:除留余数法的计算过程非常简单,只需进行一次取模运算即可得到哈希值,计算速度非常快。
  • 均匀分布:当哈希表大小 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数字分析法(了解)

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

假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前 7 位都是 相同的,那么我们可以 选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转( 如 1234改成 4321) 、右环位移 ( 1234 改成 4123) 、左环移位、前两数与后两数叠加 ( 1234 改成 12+34=46) 等方法。
数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均 匀的情况。
注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

 三.哈希冲突

3.1了解哈希冲突

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

如下例子:

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

引起哈希冲突的一个原因可能是: 哈希函数设计不够合理
哈希函数设计原则
  • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0m-1 之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单
冲突-避免-负载因子调节

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

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

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

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

 

所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。

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

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

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

例子如下:

哈希冲突-线性探测法

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

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


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

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

哈希冲突-二次探测法

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

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

注意:
当表的长度为质数且表装载因子 a 不超过 0.5 时,新的表项一定能够插入,而且任何一个位置都不
会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a 不超过 0.5,如果超出必须考虑增容。因此,比散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。


3.4哈希桶-解决哈希冲突 

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

 

从上图可以看出,开散列中每个桶中 开散列,可以认为是把一个在大集合。
哈希桶(散列表)的代码的实现:
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和valuenode.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@Overridepublic 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);}@Overridepublic 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);}
}

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

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

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

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

运行如下:

如果没有重写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.只出现一次的数字

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

力扣-只出现一次的数字



2.138. 随机链表的复制 - 力扣(LeetCode)

解题思路:

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

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


3.771. 宝石与石头 - 力扣(LeetCode)

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

力扣-石头与宝石


4. 旧键盘 (20)__牛客网 (nowcoder.com)

解题思路:

  1. 在循环体内,通过in.nextLine()分别获取两行输入字符串,分别赋值给string1string2
  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)

解题思路(这个较为复杂 ):

首先,通过遍历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

结语:

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1007521.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

安卓上架华为踩坑合集

1.如果是离线打包&#xff0c;注意在manifest那里修改&#xff1a; android:debuggablefalse2…您的应用targetsdk版本低于30&#xff0c;不符合华为应用市场审核标准。 修改建议&#xff1a;请您将应用targetsdk等级升级到30或30以上。 因为之前我升到30被打回来过&#xff…

Unreal发布Android在刘海屏手机上不能全屏显示问题

Unreal 4.27发布Android在刘海屏手机上不能全屏显示问题 Android设置全屏刘海屏全屏设置4.27设置刘海屏在部分手机不能显示问题 Android设置全屏 AndroidManifest.xml文件配置 ...<activity android:name"com.epicgames.ue4.GameActivity" android:label"st…

2024计算机二级Python

1. 栈是先进先出&#xff0c;队是后进后出 2. 代码输出长度为5并不是\不占用位置&#xff0c;而是\与其后边的数字共同占用一个字符 3. 首先要弄清range函数此时表示的范围是前闭后开&#xff0c;不包含后面的数字&#xff0c;%函数表示的是余数&#xff0c;只有4是被整除的…

想要自己制作一款游戏,需要掌握哪些基本技能?

你是否曾经沉浸在游戏的世界中&#xff0c;感受到游戏带来的无限乐趣&#xff1f;你是否曾经梦想能够亲手制作一款属于自己的游戏&#xff0c;为玩家带来独特的体验&#xff1f;然而&#xff0c;要实现自己的游戏创作梦想&#xff0c;并不是一件轻松的事情。需要掌握各种技能和…

Java八股文(Maven)

Java八股文のMaven Maven Maven 什么是Maven&#xff1f; Maven是一个项目管理工具&#xff0c;用于构建、发布和管理Java项目。 它提供了一种标准化的项目结构、依赖管理和构建过程。 Maven的核心概念是什么&#xff1f; Maven的核心概念包括POM文件、依赖管理、仓库、生命周…

Paraverse白皮书发布,打造面向3D数字资产的去中心化运行与交易平台

随着信息技术的不断演进&#xff0c;我们正迎来以“元宇宙”和“Web3.0”为代表的“数字平行世界”。近日Paraverse平行云联合3D/XR产业和Web3.0领域的行业机构、专家发布了《Paraverse&#xff1a;面向3D数字资产的去中心化运行与交易平台》&#xff08;以下简称“白皮书”&am…

基于单片机的电子琴设计

基于单片机的电子琴设计 摘 要 读书、看电影、听音乐&#xff0c;都是最常见的丰富内心世界的良剂。听音乐&#xff0c;作为陶冶情操、提升境界最便捷的方式&#xff0c;正受到越来越多人们的欢迎。音乐可以很轻松的融入各种场合&#xff0c;给人们带来很轻松的氛围&#xff…

kakfa模拟仿真篇之spark-submit在linux运行 (更贴近真实场景)

源码在上篇 地址在这 &#xff1a;Kafka模拟器产生数据仿真-集成StructuredStreaming做到”毫秒“级实时响应StreamData落地到mysql-CSDN博客 这里分享一下一些新朋友不知道spark-submit 指令后 的参数怎么写 看这篇绝对包会 声明&#xff1a; 此项目是基于 maven 打包的说明…

ip广播智慧工地广播喊话号角 IP网络号角在塔吊中应用 通过寻呼话筒预案广播

ip广播智慧工地广播喊话号角 IP网络号角在塔吊中应用 通过寻呼话筒预案广播 SV-704XT是深圳锐科达电子有限公司的一款壁挂式网络有源号角&#xff0c;具有10/100M以太网接口&#xff0c;可将网络音源通过自带的功放和号角喇叭输出播放&#xff0c;可达到功率50W。SV-704XT内置有…

怎么避免电脑数据被拷贝?电脑如何禁用USB功能?

在无纸化办公的今天&#xff0c;很多重要数据都存放在电脑中。为了避免数据泄露&#xff0c;需要采用安全的方式保护电脑数据。那么&#xff0c;该如何避免电脑数据被拷贝呢&#xff1f;下面我们就来了解一下。 方法一&#xff1a;物理隔绝 物理隔绝是一种原始但有效的USB禁用…

KubeSphere 社区双周报|2024.02.29-03.14

KubeSphere 社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过 commit 的贡献者&#xff0c;并对近期重要的 PR 进行解析&#xff0c;同时还包含了线上/线下活动和布道推广等一系列社区动态。 本次双周报涵盖时间为&#xff1a;2024.02.29-03.14…

【深度学习笔记】9_8 区域卷积神经网络(R-CNN)系列

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 9.8 区域卷积神经网络&#xff08;R-CNN&#xff09;系列 区域卷积神经网络&#xff08;region-based CNN或regions with CNN feature…

叶顺舟:手机SoC音频趋势洞察与端侧AI技术探讨 | 演讲嘉宾公布

后续将陆续揭秘更多演讲嘉宾&#xff01; 请持续关注&#xff01; 2024中国国际音频产业大会(GAS)将于2024年3.27 - 28日在上海张江科学会堂举办。大会将以“音无界&#xff0c;未来&#xff08;Audio&#xff0c; Future&#xff09;”为主题。大会由中国电子音响行业协会、上…

L1-5 猜帽子游戏

宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子&#xff0c;有的是黑色的&#xff0c;有的是黄色的。每个人可以看到别人头上的帽子&#xff0c;但是看不到自己的。游戏开始后&#xff0c;每个人可以猜自己头上的帽子是什么颜色&#xff0c;或者可以弃权不猜。如果没有…

导出pdf

pom依赖 <dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.4.2</version></dependency><dependency><groupId>com.itextpdf</groupId><artifactId>itext-as…

PHP序列化基础知识储备

一、序列化与反序列化 1、概念 PHP中的序列化是指将复杂的数据类型转换为可存储或可传输的字符串&#xff0c;而反序列化则是将这些字符串重新转换回原来的数据类型。 序列化通常使用 serialize() 函数完成&#xff0c;它可以将数组、对象、字符串等复杂数据类型压缩到一个字…

高德 Android 地图SDK 绘制面不显示

问题 高德 Android 地图SDK 绘制面不显示 详细问题 笔者按照高德 Android 地图SDK 绘制面所给示例 绘制面后 绘制面不显示 具体代码 // 定义多边形的5个点点坐标 LatLng latLng1 new LatLng(42.742467, 79.842785); LatLng latLng2 new LatLng(43.893433, 98.124035); La…

Spring MVC(一)— DispatcherServlet

DispatcherServlet 是Spring MVC框架的HTTP 请求处理器的中央调度器。它具有以下的功能&#xff1a; 1&#xff09;基于IoC容器JavaBean配置机制。 2&#xff09;使用HandlerMappingl来实现请求到处理器的路由映射。 3&#xff09;使用HandlerAdapter 来处理不同的处理器。 …

OpenCASCADE开发指南<九>:OCC 数据结构分析之拓扑数据结构

数据结构,指的是数据元素之间的相互关系,尤其是数据的逻辑结构。选择数据结构的主要依据是数据的逻辑结构[6]。 因此&#xff0c; 本章将主要描述三种数据的逻辑结构。这三种数据包括&#xff1a;二维几何数据、三维几何数据和拓扑数据。 1 拓扑数据 拓扑数据结构定义了参数空…

BBS模型层搭建

BBS模型层搭建 目录 BBS模型层搭建建表思想配置文件模型层User应用&#xff1a;Blog应用&#xff1a;Article应用&#xff1a; 建表思想 配置文件 settings.py&#xff1a; # 默认用户模型指定 AUTH_USER_MODEL User.Userinfo底部添加即可&#xff0c;用于替换默认的Abstrac…