哈希冲突详解(拉链法,开放地址法)

2024-02-07 01:38

本文主要是介绍哈希冲突详解(拉链法,开放地址法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

哈希冲突详解


我喜欢用问答的形式来学习,这样可以明确许多不明朗的问题。

  1. 什么是哈希冲突?

比如我们要去买房子,本来已经看好的房子却被商家告知那间房子已经被其他客户买走了。这就是生活中实实在在的冲突问题。

同样的当数据插入到哈希表时,不同key值产生的h(key)却是相等的,这个时候就产生了冲突。这个时候就要解决这个问题。

  • 怎么解决哈希冲突?

    方法1:拉链法 
    方法2:开地址法

  • 何为拉链法?

    拉链法是解决哈希冲突的一种行之有效的方法,某些哈希地址可以被多个关键字值共享,这样可以针对每个哈希地址建立一个单链表。

    在拉链(单链表)的哈希表中搜索一个记录是容易的,首先计算哈希地址,然后搜索该地址的单链表。

    在插入时应保证表中不含有与该关键字值相同的记录,然后按在有序表中插入一个记录的方法进行。针对关键字值相同的情况,现行的处理方法是更新该关键字值中的内容。

    删除关键字值为k的记录,应先在该关键字值的哈希地址处的单链表中找到该记录,然后删除之。

  • 什么是开地址法?

    首先该方法并不建立链表。哈希表由M个元素组成,其地址从0到M-1。我们通过从空表开始,逐个向表中插入新记录的方式建立散列表。 
    插入关键字值为key的新纪录的方法是: 
    从h(key)开始,按照某种规定的次序探查插入新记录的空位置。h(key)被称为基位置。如果h(key)已经被占用,那么需要用一种解决冲突的策略来确定如何探查下一个空位置,所以这种方法又称为空缺编址法。 
    根据不同的解决冲突的策略,可以产生不同的需要被检查的位置序列,称为 探查序列。 
    根据生成的探查序列的不同规则,可以有 线性探查法伪随机探查法二次探查法 和 双散列法等开址方法。

  • 线性探查法详解

    缺点:线性探查法在情况不好的时候导致许多记录在散列表中连成一片,从而使探查次数增加,影响搜索效率。这种现象称为基本聚集

    线性探查法是一种简单的开地址方法,它使用下列循环探查序列:

    h(key),h(key)+1,...,M-1,0,...,h(key)-1

    从基位h(key)开始探查该位置是否被占用,即是否为空位置。 
    如果被占用,则继续探查位置h(key)+1,若该位置也已占用,再根据探查序列中的规定继续检查下一个位置。 
    因此,探查序列为:

    h(i) = (h(x)+i) % M (i=0,1,2,...,M-1)
  • 伪随机法详解

    伪随机法是为了消除线性探查的基本聚集而提出来的方法。其基本思想是建立一个伪随机数发生器。当发生冲突时,就利用伪随机数发生器计算下一个探查位置。伪随机数发生器有不同的构造。

    一个比较简单的伪随机数产生方法:

       y(0) = h(key)y(i+1) = (y(i)+p) % M  (i=0,1,2,...)
    式中,y(0)为伪随机数发生器的初值,M为哈希表的长度,
    P为与M接近的素数。
    
  • 二次探查法详解

    二次探查法也能够消除基本聚集,虽然伪随机数法和二次探查法都能够消除基本聚集。但是如果两个关键字值有相同的基本位置,那么它们就会有相同的探查序列。这是因为伪随机数法和二次探查产生的探查序列是基位置的函数,而不是原来关键字的函数,因此由产生了二次聚集的问题。

  • 双散列法详解 

    使用双散列方法可以避免二级聚集。双散列法使用两个散列函数,第一个散列函数计算探针序列的起始值,第二个散列函数计算下一个位置的探查步长。

这篇关于哈希冲突详解(拉链法,开放地址法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/686158

相关文章

Linux线程同步/互斥过程详解

《Linux线程同步/互斥过程详解》文章讲解多线程并发访问导致竞态条件,需通过互斥锁、原子操作和条件变量实现线程安全与同步,分析死锁条件及避免方法,并介绍RAII封装技术提升资源管理效率... 目录01. 资源共享问题1.1 多线程并发访问1.2 临界区与临界资源1.3 锁的引入02. 多线程案例2.1 为

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile:专业级归档工具2.zipfile:跨平台归档首选3.

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤:安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性:有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

SQL Server 中的 WITH (NOLOCK) 示例详解

《SQLServer中的WITH(NOLOCK)示例详解》SQLServer中的WITH(NOLOCK)是一种表提示,等同于READUNCOMMITTED隔离级别,允许查询在不获取共享锁的情... 目录SQL Server 中的 WITH (NOLOCK) 详解一、WITH (NOLOCK) 的本质二、工作

springboot自定义注解RateLimiter限流注解技术文档详解

《springboot自定义注解RateLimiter限流注解技术文档详解》文章介绍了限流技术的概念、作用及实现方式,通过SpringAOP拦截方法、缓存存储计数器,结合注解、枚举、异常类等核心组件,... 目录什么是限流系统架构核心组件详解1. 限流注解 (@RateLimiter)2. 限流类型枚举 (

Java Thread中join方法使用举例详解

《JavaThread中join方法使用举例详解》JavaThread中join()方法主要是让调用改方法的thread完成run方法里面的东西后,在执行join()方法后面的代码,这篇文章主要介绍... 目录前言1.join()方法的定义和作用2.join()方法的三个重载版本3.join()方法的工作原