哈希冲突_算法与数据结构中哈希冲突是什么意思-程序员宅基地

技术标签: 算法  拉链法  哈希冲突  开放地址法  

哈希冲突概念及解决方案

哈希冲突的概念

哈希算法的目的就是将一串很大的数据根据一定的规则转换为较小的数据。在这个从大到小的转换过程中,不可避免的会出现两个不同的数据在经过哈希算法的计算后生成了相同的哈希值。这个过程我们称之为哈希冲突。
哈希冲突会带来很多问题,例如在哈希表中,两个不同的key值的哈希值相同,那么当这两个key值所表示的数据中的第一个存放到指定的位置后,第二个就没有地方可以存放了。所以我们在设计使用哈希算法的时候一定不能忽略掉哈希冲突。

哈希冲突的解决方法

常用的解决哈希冲突的方法有以下几种:

拉链法

拉链法是指当出现哈希冲突时,将具有相同哈希值的key值放进一个链表之中。当进行查找的时候可以通过遍历这个链表中的数据来寻找是否存在和被查找的key值相等的值。这种方法适用于处理冲突比较严重的情况。
在这里插入图片描述

再哈希法

首先构造多个哈希算法Di = H1 (keyi), Di = H2 (keyi)…
当发生哈希冲突时,将key值通过第二个哈希算法计算哈希值,若还冲突,就继续下去,直到找到不发生冲突的值。

开放地址法

开放地址法思想:当发生哈希冲突时,将这个哈希值加上一个增量d,来获取新的哈希值。即:
Di = (H(key) + d) mod m。这里的m是空间大小,以防止哈希值超出规定范围。
根据d的取值不同,开放地址法分为以下四种:

线形勘测再散列

d的取值为1,2,3,…
即当发生哈希冲突时,判断当前哈希值H+1这个位置是否会发生哈希冲突,即当前H+1的位置上是否存在数据,如果不存在就将值放在这个位置上,如果存在数据,就判断hH+2。以此类推,直到找到不发生哈希冲突的位置。

二次勘测再散列

d的取值为1,-1,22,-(22)…

双散列法

定义另一个哈希算法PI = H2(keyI),当发生哈希冲突时,哈希值为(H1(keyi) + H2(keyi) mod m。

伪随机法

d的取值为一个伪随机序列依次取值。

注意:使用开放地址法解决哈希冲突问题时,当删掉某个数据时,不能直接将其删除。因为这样会截断其他具有相同哈希值数据的位置。所以应该用一个标记标记下这个数据已经被删除。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44684427/article/details/103324928

智能推荐

记一次xxl_job中HttpJobHandler中的数据请求与存储-程序员宅基地

文章浏览阅读6.8k次。@JobHandler(value = "httpJobHandler")@Componentpublic class HttpJobHandler extends IJobHandler { @Resource private BankSynchronizationService bankSynchronizationService; @Override ..._httpjobhandler

css外层DIV半透明内层div不透明-弹出层效果的实现_div透明展示底部div-程序员宅基地

文章浏览阅读2.6k次。css外层DIV半透明内层div不透明-弹出层效果的实现<!DOCTYPE html><html> <head> <meta charset="utf-8" /> <title>css外层DIV半透明内层div不透明-弹出层效果的实现【_div透明展示底部div

Hadoop集群搭建(非高可用)_高可用集群hadoop-程序员宅基地

文章浏览阅读396次。非高可用集群搭建 第一部分环境准备 =============================================================================== 1. 安装好linux 2. *安装VMTools 3. 关闭防火墙 sudo service iptables stop sudo chkconfig ipt..._高可用集群hadoop

C语言system函数使用-程序员宅基地

文章浏览阅读10w+次,点赞270次,收藏1.4k次。函数原型包含在头文件 “stdlib.h” 中int system(const char * command)函数功能执行 dos(windows系统) 或 shell(Linux/Unix系统) 命令,参数字符串command为命令名。另,在windows系统下参数字符串不区分大小写。说明:在windows系统中,system函数直接在控制台调用一个command命令。在L..._system函数

第3课 计算机病毒的防治反思,《计算机病毒及其防治》说课稿 三篇.doc-程序员宅基地

文章浏览阅读230次。文档介绍:《计算机病毒及其防治》说课稿各位评委教师: 大家好! 我是来自荆门市石化中学的信息技术教师赵城,今天我说课是内容是《计算机病毒及其防治》,这是一节理论实践课, 下面具体阐述一下我设计这节课的具体设计思路,并希望能得到各位专家和老师的指导。第一部分:说教材一、教材分析《计算机病毒及其防治》是华中师范大学出版社全日制普通高级中学教科书《信息技术》第四册“信息安全”中的第四部分和第五部分内容,...

vue 移动端word、excel、pdf预览本地测试案例_vue移动端项目预览文件的插件-程序员宅基地

文章浏览阅读4.1k次。第一步新建一个vue项目。打开控制命令行程序(CMD),运行命令: vue init webpack “项目名称”。第二步安装依赖,在控制命令行程序(CMD),运行命令:npm install 或者 cnpm install.实现预览这里先以word为例。首先运行命令:npm install mammoth,这是预览word的一个插件,必须要安装;在static文件夹下放一个.docx为后缀的word文件:然后在页面引入即可:<template> <div cla_vue移动端项目预览文件的插件

随便推点

USB OTG(On-The-Go)技术概述_on-the-go otg-程序员宅基地

文章浏览阅读1.8k次。USB OTG(On-The-Go)技术概述[USB 2.0规范] 摘要:USB OTG(On-The-Go)是USB 2.0规范的补充,它使外设可以在无主机参与的情况下直接互连进行通信工程.本文讨论了USB OTG补充规范的新增特性,包括OTG事务请求协议SRP和主机流通协议HNP、连接器和电缆、两用OTG设备和外设式OTG设备、驱动程序以及数据流模型。关键词:USB 2.0_on-the-go otg

AES加密算法_aes256加密算法-程序员宅基地

文章浏览阅读2.1k次。密钥类型AES-128:128位比特(16字节) AES-192:192位比特(24字节) AES-256:256位比特(32字节)一般简短数据采用AES-128,也就是16字节,少部分采用AES-256。填充方式NoPadding:不填充,只能加密长度为16倍数的数据,一般不适用; Zeros:补0,如果原数据长度恰好是16的倍数,也要补16个0; ISO10126:最后一个字节是填充的字节数(包括最后一字节),其他全部填随机数1 2 3 4 5 6 7 8 9 10 –.._aes256加密算法

python oracle转mysql_python 取oracle数据转存至mysql-程序员宅基地

文章浏览阅读137次。由于grafana的oracle插件需要付费,所以只能想想办法,于是就用Oracle的数据转到mysql数据库里面。其实也很简单,需要提前安装好python和oracle数据库驱动cx_oracle 和MySQL 驱动,具体可以自己搜索。脚本如下#!/usr/bin/python# -*- coding: UTF-8 -*-import cx_Oracle #导入包import MySQLdbim..._str(len(list))

一定要学会的vsCode格式化整理代码的快捷键,再也不用手动调格式了_cscode格式化代码快捷键-程序员宅基地

文章浏览阅读2.7w次,点赞16次,收藏45次。开发过程中经常遇到代码杂乱的情况,每次手动排列都需要浪费大量时间,如果能配置自动整理代码既能让代码赏心悦目也就不用再浪费排列的时间1、在vscode编辑器中插件应用里找到vetur并安装点击左侧最后一个图片查看已有的插件,我这已经加了Vetur的插件,如果没有的同学直接在上面搜索自动添加就可以2、设置打开file(文件)----->preferences(首选项)------>settings(设置),搜索vetur.format.defaultFormatter.html会_cscode格式化代码快捷键

angular入门基本操作(node.js安装、angular安装、镜像源安装、visual studio code安装、git常用命令)_angular镜像安装-程序员宅基地

文章浏览阅读655次。angular入门基本操作一、下载并安装Node.js​ 安装步骤 下载链接​ 为什么安装Node.js​ Angular、Angular CLI 和 Angular 应用都依赖于 npm包(node.js package manage)中提供的特性和功能。要想 下载并安装 npm包,就必须拥有一个 npm 包管理器,而Node.js 已经默认安装了它。二、安装Angular CLI..._angular镜像安装

Android开发实用必备的几款插件,分析Android未来几年的发展前景,Android岗_android 2021 好用的插件-程序员宅基地

文章浏览阅读170次。前言近日,字节跳动正式启动了2021届秋季校园招聘,为应届毕业生开放超过6000个工作岗位。这一数字超过了该公司往年秋招规模,并与其今年春招规模持平。全年校招人数共计超过1万2千人,远高于同类型互联网公司,体现了字节跳动保持业务快速增长,重视对优秀人才的持续投入。字节跳动校园招聘负责人介绍,该项招聘主要面向2021届毕业生,即2020 年9月至2021年8月期间毕业的大学生群体。这批岗位覆盖字节跳动10多项产品和业务,既包括今日头条、抖音、西瓜视频等旗舰产品,也包括懂车帝、幸福里、番茄小说等垂类应用,以_android 2021 好用的插件

推荐文章

热门文章

相关标签