【哈希表】深入理解哈希表

2024-09-08 11:36
文章标签 深入 理解 哈希

本文主要是介绍【哈希表】深入理解哈希表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1、哈希表简介
  • 2、哈希函数
    • 2.1、概念
    • 2.2、常用的哈希函数
      • 2.2.1、直接定址法
      • 2.2.2、除留余数法
      • 2.2.3、平方取中法
      • 2.2.4、基数转换法
  • 3、哈希冲突
    • 3.1、概念
    • 3.2、开放地址法【闭散列:key存放到冲突位置的“下一个”空位置】
    • 3.3、链地址法【开散列:冲突位置变为链表】
    • 3.4、开散列下冲突严重时(导致链表过长)的优化
      • 3.4.1、整个哈希表进行扩容
      • 3.4.2、单个链表转为哈希表或者变为搜索树
  • 4、负载因子

1、哈希表简介

哈希表(Hash Table):也叫做散列表,是根据关键码值(Key Value)直接进行访问的数据结构,可快速查找

实现思想:

哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
这个映射函数叫做「哈希函数(散列函数)」,存放记录的数组叫做「哈希表(散列表)」

可以将算法思想分为两个部分:

  • 向哈希表中插入一个关键码值:哈希函数决定该关键字的对应值应该存放到表中的哪个区块,并将对应值存放到该区块中
  • 在哈希表中搜索一个关键码值:使用相同的哈希函数从哈希表中查找对应的区块,并在特定的区块搜索该关键字对应的值

案例:使用 value = Hash(key) = key // 1000 作为哈希函数【// 整除】

在这里插入图片描述

  • 向哈希表中插入一个关键码值:通过哈希函数解析关键字,并将对应值存放到该区块中
    • 如:0138 通过哈希函数 Hash(key) = 0138 // 100 = 0,得出应将 0138 分配到 0 所在的区块中
  • 在哈希表中搜索一个关键码值:通过哈希函数解析关键字,并在特定的区块搜索该关键字对应的值
    • 如:查找 2321,通过哈希函数,得出 2321 应该在 2 所对应的区块中。然后我们从 2 对应的区块中继续搜索,并在 2 对应的区块中成功找到了 2321

哈希表的优势:

在顺序结构和平衡树中,元素关键码与它的存储位置之间没有对应映射关系,在查找时需要多次比较,而哈希表可以通过哈希函数建立元素关键码与存储位置之间的对应关系,查找时经过哈希函数的计算,可以算出元素对应的存储位置,直接到存储位置取出要查找的元素,不需要像顺序结构或者平衡树那样多次比较

2、哈希函数

2.1、概念

哈希函数(Hash Function):将哈希表中元素的关键键值映射为元素存储位置的函数

一般来说,哈希函数会满足以下几个条件:

  • 哈希函数应该易于计算,并且尽量使计算出来的索引值均匀分布
  • 哈希函数计算得到的哈希值是一个固定长度的输出值
  • 如果 Hash(key1) 不等于 Hash(key2),那么 key1、key2 一定不相等
  • 如果 Hash(key1) 等于 Hash(key2)那么 key1、key2 可能相等,也可能不相等(会发生哈希碰撞)

在哈希表的实际应用中,关键字的类型除了数字类,还有可能是字符串类型、浮点数类型、大整数类型,甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型,再通过哈希函数,将其映射到哈希表中

关于整数类型的关键字,通常用到的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等

2.2、常用的哈希函数

2.2.1、直接定址法

直接定址法:取 关键字本身 / 关键字的某个线性函数值 作为哈希地址。即:Hash(key) = key 或者 Hash(key) = a * key + b,其中 a 和 b 为常数

这种方法计算最简单,且不会产生冲突。适合于关键字分布基本连续的情况,如果关键字分布不连续,空位较多,则会造成存储空间的浪费

案例:我们有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字,哈希函数取关键字自身,如下表所示

年龄1299100
人数200030005000

2.2.2、除留余数法

除留余数法:假设哈希表的表长为 m,取一个不大于 m 但接近或等于 m 的质数 p,利用取模运算,将关键字转换为哈希地址。即:Hash(key) = key % p,其中 p 为不大于 m 的质数

这是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言,一般 p 取素数或者 m,这样可以尽可能的减少冲突

案例:需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中(长度为 11 的数组),通过除留余数法将这 7 个数应分别位于如下地址:

第一个数计算出索引位置:432 % 11 = 3

数据88111432925193128
索引012345678910

2.2.3、平方取中法

平方取中法:先通过求关键字平方值的方式扩大相近数之间的差别,然后根据表长度取关键字平方值的中间几位数为哈希地址

如:Hash(key) = (key * key) // 100 % 1000,先计算平方,去除末尾的 2 位数,再取中间 3 位数作为哈希地址

这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关,所以产生的哈希地址也比较均匀,有利于减少冲突的发生

2.2.4、基数转换法

基数转换法:将关键字看成另一种进制的数再转换成原来进制的数,然后选其中几位作为哈希地址

如:将关键字看做是 13 进制的数,再将其转变为 10 进制的数,将其作为哈希地址。以 343246 为例:

34324613 = 3 * 13 5 + 4 * 13 4 + 3 * 13 3 + 2 * 13 2 + 4 * 13 1 + 6 * 13 0 = 123511010

3、哈希冲突

3.1、概念

哈希冲突:不同的关键字通过同一个哈希函数可能得到同一哈希地址,即 key1 ≠ key2,而 Hash(key1) = Hash(key2),这种现象称为哈希冲突

理想状态下,我们的哈希函数是完美的一对一映射,即一个关键字(key)对应一个值(value),不需要处理冲突。但是一般情况下,不同的关键字 key 可能对应了同一个值 value,这就发生了哈希冲突

设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。

常用的哈希冲突解决方法主要是两类:

  • 开放地址法
  • 链地址法

3.2、开放地址法【闭散列:key存放到冲突位置的“下一个”空位置】

开放地址法(Open Addressing):指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止

当发生冲突时,开放地址法按照下面的方法求得后继哈希地址:H(i) = (Hash(key) + F(i)) % m,i = 1, 2, 3, …, n (n ≤ m - 1)

  • H(i):在处理冲突中得到的地址序列。即在第 1 次冲突(i = 1)时经过处理得到一个新地址 H(1),如果在 H(1) 处仍然发生冲突(i = 2)时经过处理时得到另一个新地址 H(2) …… 如此下去,直到求得的 H(n) 不再发生冲突
  • Hash(key):哈希函数,m 是哈希表表长,对哈希表长取余的目的是为了使得到的下一个地址一定落在哈希表中
  • F(i) :冲突解决方法,取法可以有以下几种
    • 线性探测法: F ( i ) = 1 , 2 , 3 , . . . , m − 1 F(i) = 1, 2, 3, ..., m - 1 F(i)=1,2,3,...,m1
    • 二次探测法: F ( i ) = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , ± n 2 ( n ≤ m / 2 ) F(i) = 1^2, -1^2, 2^2, -2^2, ..., \pm n^2(n \le m / 2) F(i)=12,12,22,22,...,±n2(nm/2)。 【负数表示向前,正数表示向后】
    • 伪随机数序列: F ( i ) = 伪随机数序列 F(i) = 伪随机数序列 F(i)=伪随机数序列

案例:在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录(哈希函数为 Hash(key) = key % 11)。现在将插入关键字为 38 的新纪录。根据哈希函数得到的哈希地址为 5,产生冲突。

接下来分别使用这三种冲突解决方法处理冲突:

  • 线性探测法:得到下一个地址 H(1) = (5 + 1) % 11 = 6,仍然冲突;继续求出 H(2) = (5 + 2) % 11 = 7,仍然冲突;继续求出 H(3) = (5 + 3) % 11 = 8,8 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 8 的位置
  • 二次探测法:得到下一个地址 H(1) = (5 + 11) % 11 = 6,仍然冲突;继续求出 H(2) = (5 - 11) % 11 = 4,4 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 4 的位置
  • 伪随机数序列:假设伪随机数为 9,则得到下一个地址 H(1) = (9 + 5) % 11 = 3,3 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 3 的位置

如下图:

在这里插入图片描述

闭散列方式最大的问题就在于,若整个哈希表冲突比较严重,此时查找元素的过程就相当于遍历数组,查找效率退化为O(N)

3.3、链地址法【开散列:冲突位置变为链表】

链地址法(Chaining):将具有相同哈希地址的元素(或记录)存储在同一个线性链表中

假设哈希函数产生的哈希地址区间为 [0, m - 1],哈希表的表长为 m。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T:

  • 这样在插入关键字的时候,我们只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i,然后将其以链表节点的形式插入到以 T[i] 为头节点的单链表中。在链表中插入位置可以在表头或表尾,也可以在中间。如果每次插入位置为表头,则插入操作的时间复杂度为 O ( 1 ) O(1) O(1)
  • 而在在查询关键字的时候,我们只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i,然后将对应位置上的链表整个扫描一遍,比较链表中每个链节点的键值与查询的键值是否一致。查询操作的时间复杂度跟链表的长度 k 成正比,也就是 O ( k ) O(k) O(k)。对于哈希地址比较均匀的哈希函数来说,理论上讲,k = n // m,其中 n 为关键字的个数,m 为哈希表的表长

案例:现在要存入的关键字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]。再假定哈希函数为 Hash(key) = key % 13,哈希表的表长 m = 13,哈希地址范围为 [0, m - 1]。将这些关键字使用链地址法处理冲突,并按顺序加入哈希表中(图示为插入链表表尾位置),最终得到的哈希表如下图所示:

在这里插入图片描述

相对于开放地址法,采用链地址法处理冲突要多占用一些存储空间(主要是链节点占用空间)。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中,待比较的关键字都是具有相同哈希地址的元素,而在开放地址法中,待比较的关键字不仅包含具有相同哈希地址的元素,而且还包含哈希地址不相同的元素

3.4、开散列下冲突严重时(导致链表过长)的优化

3.4.1、整个哈希表进行扩容

假设以前%7(数组长度为7),现在就扩容为原数组的一倍,现在%14(数组长度变为14),就可以大大降低冲突的概率,减少链表长度

3.4.2、单个链表转为哈希表或者变为搜索树

单个链表长度过长,查询效率就会变为链表的遍历 O(N),就针对这单个链表进行转换处理:可以把单个链表转为哈希表或者变为搜索树(JDK8 的 HashMap 就采用此方案,当某个链表的长度 >8 且整个哈希表元素个数 >64,把此链表转为红黑树

4、负载因子

散列表的载荷因子定义为: a = 填入表中的元素个数 / 散列表的长度

  • 负载因子越大,发生哈希冲突的概率越大,数组长度就会偏小,但节省空间
  • 负载因子越小,发生哈希冲突的概率越小,数组长度就会偏大,但浪费空间

负载因子和冲突率是相互影响的,因此可以设定一个的负载因子阈值,负载因子超过阈值,就增加哈希桶,降低冲突率

在这里插入图片描述

由图中可以看到,负载因子的值增大,冲突率也随着增大,我们不能直接控制冲突率,可以通过影响负载因子来降低冲率,而控制负载因子,负载因子是哈希表的元素数量除哈希桶数量,我们认为哈希表要传入的数量是未知的,也可以看作无穷的,所以,通过不能降低减少哈希表元素的数量来降低负载因子的值,但我们可以通过增加哈希桶的值来降低负载因子的值,进而降低冲突率【HashMap 的哈希表长度为16,当元素个数超过 12 就会发生扩容】

【参考资料】
算法数据结构基础——哈希表(Hash Table)
数据结构之—哈希表

这篇关于【哈希表】深入理解哈希表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

深入理解RxJava:响应式编程的现代方式

在当今的软件开发世界中,异步编程和事件驱动的架构变得越来越重要。RxJava,作为响应式编程(Reactive Programming)的一个流行库,为Java和Android开发者提供了一种强大的方式来处理异步任务和事件流。本文将深入探讨RxJava的核心概念、优势以及如何在实际项目中应用它。 文章目录 💯 什么是RxJava?💯 响应式编程的优势💯 RxJava的核心概念

如何通俗理解注意力机制?

1、注意力机制(Attention Mechanism)是机器学习和深度学习中一种模拟人类注意力的方法,用于提高模型在处理大量信息时的效率和效果。通俗地理解,它就像是在一堆信息中找到最重要的部分,把注意力集中在这些关键点上,从而更好地完成任务。以下是几个简单的比喻来帮助理解注意力机制: 2、寻找重点:想象一下,你在阅读一篇文章的时候,有些段落特别重要,你会特别注意这些段落,反复阅读,而对其他部分