哈希表

简介: 哈希表的表示

几个概念

  • 哈希函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为H(K)。
  • 冲突:对不同的关键字可能得到同一哈希地址的现象,即key1 != key2,而H(key1)=H(key2)。
  • 同义词:发生冲突的不同关键字。
  • 哈希表:根据关键字直接进行访问的数据结构,建立了关键字与存储地址之间的一种直接映射关系。

哈希函数的构造方法

(1)直接定址法
取关键字或关键字的线性函数值为哈希地址,即H(key)=key或H(key)=a*key+b。
这种方法对于不同的关键字不会发生冲突,但关键字分布不连续,空位多,会造成存储空间的浪费。
(2)除留余数法
取关键字被某个不大于哈希表表长length的数p除后所得的余数为哈希地址,即H(key)=key % p,p<=length。
p一般取一个不大于length但最接近或等于length的质数。
(3)平方取中法
取关键字平方后的中间几位为哈希地址。
(4)数字分析法
设关键字是r进制数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干位组成哈希地址。
(5)折叠法
将关键字分割成位数相同的几部分,然后取这几部分的叠加和(舍去进位)作为哈希地址。
当关键字位数很多,而且关键字中每一位上数字分布大致均匀是适用。

处理冲突的方法

  • 开放定址法

H~i~ = (H(key) + d~i~) % length,i = 1,2,3,...,length。
其中:H(key)为哈希函数;length为哈希表表长;d~i~为增量序列。
对于d~i~有几种不同的取法:
(1)d~i~ = 1,2,3,...,length-1,称为线性探测再散列
(2)d~i~ = 1^2^,-1^2^,2^2^,-2^2^,3^2^,...,+-k^2^(k<=length/2),称为二次探测再散列
(3)d~i~ = 伪随机数序列,称为伪随机探测再散列
在这里插入图片描述

  • 再哈希法

H~i~ = RH~i~(key),i = 1,2,3,...,length。
RH~i~均为不同的哈希函数,即在同义词产生冲突时计算另一个哈希函数地址,直到冲突不在发生。

  • 链地址法

将所有关键字为同义词的记录存储在同一线性表中。
在这里插入图片描述

目录
相关文章
|
8天前
|
存储 缓存 数据库
哈希表
【10月更文挑战第24天】哈希表是一种非常实用的数据结构,它在各种计算机应用中发挥着重要作用。通过深入了解哈希表的原理、实现和应用,我们可以更好地利用它来解决实际问题。
|
6月前
|
存储 算法 Java
【算法系列篇】哈希表
【算法系列篇】哈希表
|
5月前
|
存储
哈希表的设计与实现
哈希表的设计与实现
32 1
|
存储 算法 Serverless
|
6月前
|
存储 Serverless
哈希及哈希表的实现
哈希及哈希表的实现
56 0
|
存储 缓存 算法
趣味算法——探索哈希表的神秘世界
前言: 在编程世界中,数据存储和检索的效率常常是我们关注的重点。对于这个问题,哈希表提供了一个既高效又实用的解决方案。哈希表是一种通过哈希函数将键转化为数组索引,以实现快速查找的数据结构。在大多数情况下,哈希表能够在常数时间内完成查找,插入和删除操作,因此在许多应用场景中得到了广泛使用。
69 0
|
存储 算法 Java
哈希表(散列表)详解
什么是哈希表,以及如何使用哈希表
|
存储 算法 JavaScript
关于散列表(哈希表)我所知道的
关于散列表(哈希表)我所知道的
59 0
|
存储 Java Serverless
哈希表以及哈希冲突
哈希表以及哈希冲突
135 0
哈希表以及哈希冲突
|
存储 算法 C++
C++:哈希:闭散列哈希表
讲解了哈希的概念以及哈希函数,简单实现了闭散列哈希。闭散列哈希的重点之一是取模操作。
C++:哈希:闭散列哈希表