❤数据结构入门❤——哈希表
目录
哈希表
概述
issue
希望读者读完本文可以独立解决一下问题:
-
为什么用哈希表?
-
哈希表的优缺点
-
关于冲突以及结果方法
-
处理冲突的两种方式分别是什么?它们个在自己的领域有着怎样的优势
一、什么是哈希表
文章开头就已经提到,哈希表是一种在链表上做一些特殊操作的数据结构。那么它与链表有什么样的联系呢,我下面举个简单的例子:
图书馆有十万万图书,把它们随意放在书架上,此时书架上的书是没有顺序的,小王想找一本《C primer puls》,他只能从第一本图书开始找,一本一本遍历,这样复杂度会很高;
哈希表就是给这些图书编号放置,便于查找。如何给图书编号那就得靠哈希函数了,通过哈希函数对其进行特殊处理下标,并将其储存在数组中。
二、哈希表的优缺点
大家在刚才的描述中一定能看出哈希表的优缺点了,这里我总结一下 ,还是希望大家能独立思考
(1)优点
-
对于一些大数据多数据,hash表处理起来比较轻松
-
能够快速的 查,改,插,删元素 等操作
-
代码简单(自己想好hash函数就完成啦)
(2)缺点
-
在hash函数处理某些元素的时候,不免出现下标重复相同的情况,这种情况可以称作为冲突
-
哈希表中的数据都是没有顺序的
冲突的解决方法
前面提到的冲突,当两个或两个以上的下标相同时发生冲突,那么该如何处理这种情况呢,下面提到两种方法,拉链法和开放寻址法,
这里比较懒用y总的图来形象的概括下
(1)拉链法
可以看出在重复下表的下面又开了一个数组,有点像邻接表。在这个数组将重复的全部装进去,这样在查找的时候只需要遍历这个数组就ok了;
这是第一种解决 冲突 的方法,但使用是还是需要考虑数组长度是否合适的
(2)开放地址法
这种方法简单来说就是当元素下标值发生冲突时,寻找空白的位置插入数据。
其实当发生冲突时,寻找空白的位置也有三种方法,分别是 线性探测 、二次探测 、再哈希法
1.线性探测
线性的意思是 :当发生冲突时,索引 1,查看此时位置是否为空,是的话插入,否则重复以上操作;
但这个方法的有一个致命的缺点,当很长一段长度都不为空时候上述步骤要重复很多次,这种现象称为聚集
那么我们将如何处理这种问题呢,接下来讲的二次探测来缓解这种情况
2.二次探测
二次探测 在线性探测的基础上,将每次探测的步长改为了当前下标值 index 1²
、index 2²
、 index 3²
…… 直到找到空白位置插入元素为止
我们可以看到,二次探测 在一定程度上解决了 线性探测 造成的 聚集 问题,但是它却在另一种程度造成了一种聚集,就比如 1²
、2²
、3²
…… n²
上的聚集。所以这种方式还是有点不太好。
3.再哈希法
再哈希法 就是再将我们传入的值进行一次 哈希化,获得一个新的探测步数 step
,然后按照这个步数进行探测,找到第一个空着的位置插入数据。这在很大的程度上解决了 聚集 的问题。
HASH表的基本操作
-
计算hash函数的值
-
定位到对应链表
O(1)的复杂度
今天时间有点赶,可能写的不够全也不够好,还有代码实现以及一些配图没有完成例子也没有多么生动,以后有时间会做修改,最后,希望大家指出我的不足,大家共同学习进步,早日进大厂!!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfgikf
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01