哈希表——我欲修仙(功法篇)

这篇具有很好参考价值的文章主要介绍了哈希表——我欲修仙(功法篇)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:【😊个人主页】
系列专栏:【❤️我欲修仙】
学习名言:莫等闲、白了少年头,空悲切。——岳飞


系列文章目录

第一章 ❤️ 学习前的必知知识
第二章 ❤️ 二分查找



什么是哈希表?

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数

 总的来说:
 - 哈希表是一种数据结构
 - 哈希表表示了关键码值和记录的映射关 
 - 哈希表可以加快查找速度
 - 任意哈希表,都满足有哈希函数f(key),代入任意key值都可以获取包含该key值的记录在表中的地址

使用哈希表的常用方法

哈希表有多种使用方式,通常我们选择何种方式需要通过以下几点进行分析:

· 计算哈希函数所需时间
· 关键字的长度
· 哈希表的大小
· 关键字的分布情况
· 记录的查找频率

直接寻址法

取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。

数字分析法

分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

平方取中法

当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址

折叠法

将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

随机数法

选择一随机函数,取关键字的随机值作为散列地址,即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p≤m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。


哈希碰撞

对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=(k2),这种现象称为冲突(英语:Collision)——我们也称之为哈希碰撞
我们有两种方式来解决这个问题:拉链法和线性探测法

拉链法

将发生碰撞的元素都存进哈希表中,我们通过索引去查找它们的位置,这种方法即拉链法。
哈希表——我欲修仙(功法篇)

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法,一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置有两种元素(a与b),在哈希表中存放a,那么就向下找一个空位放置b。所以要求哈希表可存放的个数一定要大于数据元素个数 ,要不然哈希表上就没有空置的位置来存放冲突的数据了。

哈希表——我欲修仙(功法篇)


三种哈希结构

在我们使用哈希表进行解决问题时通常有三种结构可供我们选择:

  • 数组
  • set(集合)
  • map(映射)

set

哈希表——我欲修仙(功法篇)

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

map

哈希表——我欲修仙(功法篇)

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的


总结

大多数情况下,使用哈希表和哈希集合的场景都会使用 HashMap 类和 HashSet 类的对象。如果哈希表的键范围有限或者哈希集合的元素范围有限,例如只能是数字或者只能是字母,则可以用数组代替哈希表。虽然从复杂度分析的角度而言,数组和哈希表的时间复杂度和空间复杂度相同,但是在实际运行时,数组的操作时间和占用空间都优于哈希表。

哈希表——我欲修仙(功法篇)
(图片与部分内容来源于网络,侵权请联系删除)文章来源地址https://www.toymoban.com/news/detail-425195.html

到了这里,关于哈希表——我欲修仙(功法篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 怎么提升数据分析能力?——功法篇(下)

    先来复习一下上篇提到的3个疑问: 为什么我做出来的分析总觉得没有别人的那么高级? 老板为什么总说我的分析“太浅了”? 数据分析师每天的工作就是取数做需求? 看完上篇讲的金字塔原理,如果你还有疑问,不妨再认识一下另一个数据分析的无上功法: 自从某一次马

    2024年01月23日
    浏览(37)
  • 蓝桥杯十大常见天阶功法——炎之呼吸.叁之型.动态规划--(上篇)

    友友们好(^-^)🌹🌹🌹,我是 杨枝 ,一枚在算法领域迈步的呆萌的博主呀~ 目前还是一只纯纯的菜汪🐶。 典型的又菜又爱闹那种👀,做不好很多事,说不好很多话,写题还总不Ac😅,还在努力还在前进👣。 你们对我来说都是是独一无二的呀💓 。在点开这篇文章的那一刻,

    2024年01月16日
    浏览(35)
  • Java修仙之路,十万字吐血整理全网最完整Java学习笔记(基础篇)

    导航: 【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/黑马旅游/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码-CSDN博客 推荐视频: 黑马程序员全套Java教程_哔哩哔哩 尚硅谷Java入门视频教程_哔哩哔哩 推荐书籍: 《Java编程思想 (第4版

    2024年01月24日
    浏览(50)
  • 【C++高阶(五)】哈希思想--哈希表&哈希桶

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 相信大家一定听说过大名鼎鼎的 哈希结构吧,就算是没用过,也听说 过这句话:这道题无脑哈希就能做 本章重点: 本篇文章着重讲解关联式容

    2024年02月05日
    浏览(32)
  • 力扣75——哈希表/哈希集合

    总结leetcode75中 哈希表/哈希集合 的算法题解题思路。 上一篇:力扣75——滑动窗口 以下代码大部分为本人所写,少部分为官方示例代码。 题目: 题解:先用哈希表分别记录各自的元素,然后各自检测是否有不存在于对方的元素。 题目: 题解:先用unordered_map记录每个字母出

    2024年02月16日
    浏览(32)
  • 哈希函数和哈希表

    哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。 哈希函数有有一些性质,是可以运用的,元素经过哈希函数映射到一个有限的集合中,这些数在集合中的分布是均匀的,就像沙子均匀散落在盘中一样。 常见的哈希函数有MD5和Shal两种。MD5它哈希值的范围是

    2024年01月23日
    浏览(28)
  • 数据结构-哈希-哈希表实现

    🚀理想的搜索方法:不经过任何的比较,一次直接从表中得到要搜索的元素。如果构造一种存储结构,通过某种函数使元素的存储位置与其关键码之间能够建立起一一映射的关系,那么在查找的时候就能通过此函数快速的找到该元素。 🚀向该结构中插入元素:根据该元素的

    2024年02月10日
    浏览(36)
  • 【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]

    在现代计算机科学和数据结构中,哈希(Hash)是一项重要而广泛应用的技术。通过将输入数据映射为固定长度的哈希值,哈希函数能够快速高效地进行数据存储、搜索和比较。然而,由于输入数据的多样性和哈希值的有限长度,哈希冲突成为了一个不可避免的问题。本文将介

    2024年02月08日
    浏览(44)
  • Python之哈希表-哈希表原理

    集合,简称集。由任意个元素构成的集体。高级语言都实现了这个非常重要的数据结构类型。 Python中,它是可变的、无序的、不重复的元素的集合 set() - new empty set object set(iterable) - new set object 去重:在集合中,所有元素必须相异 无序:因为无序,所以不可索引 可哈希:Py

    2024年02月07日
    浏览(31)
  • 【C++杂货铺】一文带你走进哈希:哈希冲突 | 哈希函数 | 闭散列 | 开散列

    在 C++98 中,STL 提供了底层为红黑树结构的一些列关联式容器,在查询时效率可以达到 O ( l o g 2 N ) O(log2^N) O ( l o g 2 N ) ,即最差情况下需要比较红黑树高度次,当树中的结点非常多的时候,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在

    2024年02月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包