哈希表

哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。

  对哈希表的使用者一一人来说,这是一瞬间的事。哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。

  哈希表也有一些缺点它是基于数组的,数组创建后难于扩展某些哈希表被基本填满时,性能下降得非常严重,所以程序虽必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

  而且,也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力,就只能选择其他数据结构。

然而如果不需要有序遍历数据,井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

哈希表算法-哈希表的概念及作用

  一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。

  理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。

哈希表最常见的例子是以学生学号为关键字的成绩表,1号学生的记录位置在第一条,10号学生的记录位置在第10条...

如果我们以学生姓名为关键字,如何建立查找表,使得根据姓名可以直接找到相应记录呢?

哈希表算法

用上述得到的数值作为对应记录在表中的位置,得到下表:

哈希表算法

上面这张表即哈希表。

如果将来要查李秋梅的成绩,可以用上述方法求出该记录所在位置:

李秋梅:lqm 12+17+13=42 取表中第42条记录即可。

问题:如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录?

这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。

哈希表算法-哈希表的构造方法

1、直接定址法

例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。

但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

哈希表算法

2、数字分析法

有学生的生日数据如下:

年.月.日

75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15 ...

经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。

3、平方取中法

取关键字平方后的中间几位为哈希地址。

4、折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。

例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则:

哈希表算法

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

哈希表算法-处理冲突的方法

如果两个同学分别叫 刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:

1、开放定址法

Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

其中m为表长,di为增量序列

如果di值可能为1,2,3,...m-1,称线性探测再散列。

如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

称二次探测再散列。

如果di取值可能为伪随机数列。称伪随机探测再散列。

例:在长度为11的哈希表中已填有关键字分别为17,60,29的记录,现有第四个记录,其关键字为38,由哈希函数得到地址为5,若用线性探测再散列,如下:

哈希表算法

2、再哈希法

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。

3、链地址法

将所有关键字为同义词的记录存储在同一线性链表中。

哈希表算法

4、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

原文发布于微信公众号 - java达人(drjava)

原文发表时间:2015-10-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿凯的Excel

让你眼花缭乱的匹配函数反查技巧

小编已经连续写了三期关于匹配函数的用法,匹配函数的扛把子(老大)肯定是Vlookup函数莫属,但是Vlookup函数有一个问题,就是要查找的内容,必须在查找内容...

2956
来自专栏

shell之sort命令

1 sort的工作原理 sort将文件的每一行作为一个单位,相互比较,比较原则是从首字符向后,依次按ASCII码值进行比较,最后将他们按升序输出。 [rocro...

2097
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

1331
来自专栏C/C++基础

统计无符号整数二进制中1的个数(Hamming weight)

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙...

1452
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.7K5
来自专栏企鹅号快讯

30分钟学会用Python编写简单程序

参与文末每日话题讨论,赠送异步新书 异步图书君 学习目标 知道有序的软件开发过程的步骤。 了解遵循输入、处理、输出(IPO)模式的程序,并能够以简单的方式修改它...

57910
来自专栏小樱的经验随笔

HUST 1588 辗转数对

1588 - 辗转数对 时间限制:1秒 内存限制:128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b),我们可以通过一步将这个数对...

3459
来自专栏WD学习记录

牛客网 合唱团

有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能...

1632
来自专栏ATYUN订阅号

PyTorch 4.0版本迁移指南

欢迎阅读PyTorch 0.4.0的迁移指南。在此版本中,我们引入了许多振奋人心的新功能和重要的bug修复,旨在为用户提供更好,更清晰的接口。在这个指南中,我们...

1592
来自专栏小樱的经验随笔

UESTC 1599 wtmsb【优先队列+排序】

题目链接:UESTC 1599 wtmsb 题意:给你一组数,每一次取出两个最小的数,将这两个数的和放入这组数中,直到这组数只剩下一个,求最后剩下那个数的大小!...

2746

扫码关注云+社区

领取腾讯云代金券