腾讯面试:如何解决哈希冲突?

我们面试时经常被问到HashMap是怎么解决哈希冲突的,很多同学对其含糊其词、一知半解。因此小编对相关知识进行了总结,希望帮助读者加深对其理解。

哈希表就是通过散列函数将键映射到定值,简单来说就是一个键对应一个值。

而通过散列函数映射时将两个键映射到了同一个值,即这两个键将被哈希表映射到同一个位置,这种情况就被称为哈希冲突。

解决哈希冲突通过有四种方法:

  • 链接法
  • 开放寻址法
  • 再哈希法
  • 哈希桶扩容

1. 链接法

每个哈希表的槽位维护一个链表或其他数据结构,当多个元素被哈希到同一个槽位时,它们会被放在这个槽位的链表中。查找时会遍历链表,插入时也会直接加到链表中。

假设我们有一个哈希表,哈希函数将键值映射到以下槽位:

0: [5, 15]1: []2: [2]3: []4: [4]当我们插入键值 5 和 15 时,它们都被映射到槽位 0。因此,它们会形成一个链表:

槽位 0: [5 -> 15]槽位 1: []槽位 2: [2]槽位 3: []槽位 4: [4]

另外:
推荐一个程序员免费学习的编程网站:我爱编程网(www.love-coding.com)
涵盖 Java几乎覆盖了所有主流技术面试题,还有市面上最全的技术精品系列教程,免费提供。
在这里插入图片描述

2. 开放寻址法

当发生冲突时,算法会寻找下一个可用的槽位。常见的探查方式有线性探查、二次探查和双重哈希等。这种方法不使用额外的存储结构,而是在哈希表内部处理所有元素。开放寻址法的几种常见探测方法确实包括线性探测、二次探测和双重散列。以下是每种方法的详细说明和示例:

2.1. 线性探测

在发生冲突时,线性探测会逐个检查后续的槽位,直到找到一个空槽。例如:

假设哈希函数为 h(k) = k % 5

  • 插入 1 → 槽位 1(成功)
  • 插入 6 → 槽位 1(冲突),检查 2(成功)
  • 插入 11 → 槽位 1(冲突),2(冲突),3(成功)

最终哈希表:

槽位 0: []
槽位 1: [1]
槽位 2: [6]
槽位 3: [11]
槽位 4: []
2.2. 二次探测

二次探测在发生冲突时采用平方递增的方式查找空槽。例如:

哈希函数仍然假设是 h(k) = k % 5

  • 插入 1 → 槽位 1(成功)
  • 插入 6 → 槽位 1(冲突),检查 1^22(成功)
  • 插入 11 → 槽位 1(冲突),检查 1^2(冲突),2^24(成功)

最终哈希表:

槽位 0: []
槽位 1: [1]
槽位 2: []
槽位 3: []
槽位 4: [6]
2.3. 双重哈希

双重散列使用第二个哈希函数来决定步长,以解决冲突。例如:

假设第一个哈希函数 h1(k) = k % 5,第二个哈希函数 h2(k) = 1 + (k % 4)

插入 1 → 槽位 1(成功)插入 6 → 槽位 1(冲突),步长 h2(6) = 1 + (6 % 4) = 3,检查 1 + 3 = 4(成功)插入 11 → 槽位 1(冲突),步长 h2(11) = 1 + (11 % 4) = 3,检查 1 + 3 = 4(冲突),再检查 4 + 3 = 2(成功)

最终哈希表:

槽位 0: []
槽位 1: [1]
槽位 2: [11]
槽位 3: []
槽位 4: [6]

3. 再哈希法

在发生冲突后,可以使用另一个哈希函数对该元素进行再哈希,找到一个新的槽位。

使用初始哈希函数 h1(k) = k % 5,当插入 10 时:

  • h1(10) = 0(槽位 0 已占用)

  • 使用新的哈希函数

    h2(k) = (k / 5) % 5
    

    ,计算:

    • h2(10) = 2(槽位 2 已占用)
  • 再次使用

    h1
    

    计算:

    • h1(10 + 1) = 1(槽位 1 已占用)
    • h1(10 + 2) = 3(放入槽位 3

最终哈希表如下:

槽位 0: [0]
槽位 1: [1]
槽位 2: [2]
槽位 3: [10]
槽位 4: [4]

4. 哈希桶扩容

如果哈希表的负载因子超过某个阈值,可以增加哈希表的大小,并重新计算所有元素的哈希值并重新分配到新的槽位。这有助于减少冲突并提高性能

哈希表的负载因子是一个衡量哈希表填充程度的重要指标,通常用公式表示为:负载因子 = 哈希表中的元素数量 / 哈希表的槽位总数负载因子的意义:高负载因子:当负载因子接近或超过 1 时,表示哈希表的槽位几乎被填满,可能导致更多的哈希冲突,从而影响查找、插入和删除的性能。
低负载因子:负载因子较低时,哈希表的空槽较多,冲突较少,性能较好,但会导致内存浪费。
负载因子的调整:通常,当负载因子超过某个设定的阈值(例如 0.7 或 0.75),就会进行扩容。扩容时,哈希表的槽位数量增加,所有元素需要重新哈希并放入新的槽位中。

假设哈希表的大小为 5,当前负载因子超过 0.7,我们决定扩容到 10。在扩容时,所有元素的哈希值需要重新计算:

  • 原哈希表:
槽位 0: [0]
槽位 1: [1]
槽位 2: [2]
槽位 3: [3]
槽位 4: [4]
  • 扩容后,哈希函数改为 h(k) = k % 10,插入后的哈希表:
槽位 0: []
槽位 1: [1]
槽位 2: [2]
槽位 3: [3]
槽位 4: [4]
槽位 5: [5]
槽位 6: []
槽位 7: []
槽位 8: []
槽位 9: []

5.方法比较

5.1. 链接法

优点:

  • 容易实现,简单明了。
  • 动态性好,可以存储任意数量的元素,只受限于内存。
  • 插入和删除操作较快,不需要重新哈希。

缺点:

  • 在某些情况下,链表可能会很长,导致查找性能下降。如果链表过长,可能导致性能接近于线性查找。
  • 需要额外的内存来存储链表节点。
5.2. 开放寻址法

优点:

  • 所有元素都存储在哈希表内部,节省了额外的内存。
  • 不需要额外的链表,查找时不需要遍历。

缺点:

  • 哈希表的负载因子需要控制在较低水平,通常小于 0.7,否则性能显著下降。
  • 在频繁冲突的情况下,查找效率会下降,且可能需要进行多次探测。
  • 删除操作复杂,可能导致“探测链”的问题,影响后续查找性能。
5.3. 再哈希法

优点:

  • 通过使用不同的哈希函数,能有效地减少冲突。
  • 可与其他方法结合使用,灵活性高。

缺点:

  • 需要额外的计算和存储开销,可能导致性能下降。
  • 在大量元素插入时,可能需要频繁地进行哈希计算。
5.4. 哈希桶扩容

优点:

  • 通过扩容可以有效降低负载因子,从而减少冲突。
  • 能够保持较高的性能,特别是在处理大量数据时。

缺点:

  • 扩容过程可能需要遍历整个哈希表,重新计算哈希值,导致短时间内性能下降。
  • 增加了内存的使用和管理复杂度。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

数组中的四个函数(数组实现)

strlen&#xff08;输出长度&#xff09; #include <stdio.h> #include <string.h> #include <stdlib.h> int main(int argc, const char *argv[]) { char str[100]; int count 0; // 提示用户输入字符串 printf("请输入一个字符串: &qu…

大数据-241 离线数仓 - 电商核心交易 业务数据表结构 订单、产品、分类、店铺、支付表

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; Java篇开始了&#xff01; 目前开始更新 MyBatis&#xff0c;一起深入浅出&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff0…

Linux-命令

文章目录 一. Linux的目录1. Linux的目录结构2. Linux的路径的描述方式3. home目录,当前工作目录4. 栗子 二. Linux命令入门1. 什么是命令,命令行2. Linux命令基础格式 三. 目录相关命令1. ls:展示当前工作目录下的内容2. cd:切换工作目录3. pwd:输出当前所在的工作目录4. 相对…

SpringBoot该怎么使用Neo4j - 优化篇

文章目录 前言实体工具使用 前言 上一篇中&#xff0c;我们的Cypher都用的是字符串&#xff0c;字符串拼接简单&#xff0c;但存在写错的风险&#xff0c;对于一些比较懒的开发者&#xff0c;甚至觉得之间写字符串还更自在快速&#xff0c;也确实&#xff0c;但如果在后期需要…

旋转图像

旋转图像 ​ 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 ​ 你必须在** 原地** 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,…

3D数据大屏实现过程,使用echarts、Next.js

&#x1f4dc; 本文主要内容 数据大屏自适应方案动效 echarts&#xff1a; 3D 立体柱状图动态流光折线图 3D 地球&#xff08;飞线、柱状图&#xff09;无限滚动列表 &#x1f50d; 大屏效果 数据大屏&#xff1a; 点击预览 &#x1f579; 运行条件 next 12.3.4echarts 5.4…

长文 | RAG的实战指南及探索之路

今天给大家带来一篇知乎孙鹏飞 的关于RAG实战的文章。 作者&#xff1a;孙鹏飞 知乎&#xff1a;https://zhuanlan.zhihu.com/p/6822534961. 背景介绍 RAG&#xff08;Retrieval Augmented Generation&#xff0c;检索增强生成 &#xff09;方法是指结合了基于检索的模型和生…

LeetCode—11. 盛最多水的容器(中等)

题目描述&#xff1a; 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff1a;…

leetcode 63.不同路径||

1.题目要求: 2.题目代码: class Solution { public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {//创建dp数组的含义vector<vector<int>> dp;dp.resize(obstacleGrid.size());for(int i 0;i < dp.size();i){dp[i].…

C++:std::deque简介

std::deque 是 C 标准模板库&#xff08;STL&#xff09;中的一个双端队列&#xff08;Double-ended Queue&#xff09;容器。它是一种动态数组&#xff0c;允许快速地在序列的两端插入和删除元素&#xff0c;同时支持随机访问。 特点 双端操作 支持在队列头部和尾部快速插入和…

【Linux】基础IO_文件系统IO_“一切皆文件”_缓冲区

目录 1. 理解"⽂件" 1-1 狭义理解 1-2 ⼴义理解 1-3 ⽂件操作的归类认知 1-4 系统⻆度 访问文件&#xff0c;需要先打开文件&#xff01;那么是由谁打开文件&#xff1f;&#xff1f;&#xff1f; 操作系统要不要把被打开的文件管理起来&#xff1f; 2. 回顾…

nginx防盗链原理与实践

nginx防盗链的原理是基于http请求头中的referer来限制对资源的访问&#xff08;referer是用来告知浏览器该网页时从哪个页面链接来的&#xff09;&#xff0c;从而防止其他网站胃经授权直接链接资源。 nginx防盗链的作用是节省带宽和资源消耗&#xff0c;保护数据安全&#xf…

UG NX二次开发(Python)-UIStyler-选取点

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、设计一个UI界面3、创建长方体的代码4、需要引入的库5、测试验证1、前言 采用Python语言进行UG NX二次开发的资料比较少,我本来不是很认可采用Python进行二次开发的,但是近期有读者咨询…

linux环境中后台运行java程序

在生产环境&#xff0c;我们通常需要让java进程后台运行&#xff0c;并且即使会话关闭&#xff0c;进程也依然存在。 使用的命令&#xff1a; nohup java -jar xxx.jar -> aaa.log 2>&1 & 详细介绍下上面这条命令 &#xff08;1&#xff09;nohup&#xff1a;…

算法笔记:力扣15、三数之和

思路&#xff1a; 实现代码 class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result new ArrayList<>(); Arrays.sort(nums); // 先对数组进行排序 for (int i 0; i < nums.length - 2; i) { /…

java基础语法光速入门

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文整理Java的基础语法部分 适合有编程基础的人快点掌握语法使用 没学过一两门语言的话。。还是不建议看了 极致的浓缩没有一点解释 注释 单行注释 // 多行注释 /**/ 数据类型 布尔型:true false 整型:int,lon…

karmada-descheduler

descheduler规则 karmada-descheduler 定期检测所有部署&#xff0c;通常是每2分钟一次&#xff0c;并确定目标调度集群中无法调度的副本数量。它通过调用 karmada-scheduler-estimator 来完成这个过程。如果发现无法调度的副本&#xff0c;它将通过减少 spec.clusters 的配…

LeetCode 力扣 热题 100道(十四)二叉树的中序遍历(C++)

给定一个二叉树的根节点 root &#xff0c;返回 它的 中序 遍历 。 如下为代码&#xff1a; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullpt…

STM32之ADC采集和DMA传输(八)

STM32F407 系列文章 -内部ADC采集和DMA传输&#xff08;八&#xff09; 目录 前言 一、ADC特性 二、DMA特性 三、ADC采集 1.单通道ADC采集 1.头文件定义 2.函数adc_init() 3.函数HAL_ADC_MspInit() 4.函数adc_channel_set() 5.函数adc_get_result() 6.函数adc_get_r…

三菱人机界面GOT SIMPLE 系列 GS2107\GS2110\GS2512

以客户需求为核心的全面升级!GOT SIMPLE系列新功能 GOT SIMPLE升级版重磅更新&#xff0c;增添了许多期待已久的新功能&#xff0c;帮助用户实现远程维护! 扩充用户存储器容量至15MB&#xff0c;并支持轮廓字体&#xff0c;以实现平滑、靓丽的字体显示。此外&#xff0c;可使用…