哈希表的理论知识


1. 哈希表的基本概念

哈希表又称散列表,若要存储的元素个数为n,设置一个长度为m(m >= n)的连续内存单元,以每个元素的关键字为自变量,通过一个称为哈希的函数把关键字映射为内存单元地址(或下标),并将该元素存储在这个内存单元中,而这个内存单元的值也称为哈希地址,这样构造出来的线性存储结构称为哈希表

  • 两个不同的关键字哈希之后可能得到相同的值,这样叫做哈希碰撞

2. 与哈希表查找性能相关的三个元素

  • 填装因子,即已经放入哈希表的元素n和哈希表总大小m之比(n/m),通常填装因子控制在0.6~0.9
  • 采用的哈希函数,若选用的哈希函数合适,即会使元素均匀分布,减少碰撞
  • 解决哈希冲突的方法,该方法决定元素如何放置,相关查询顺序

3. 哈希函数的构造方法

哈希函数的目标是让所有元素的哈希地址尽可能均匀分布,且计算过程尽可能简单提高时间效率,下面讨论整形的哈希值

  • 直接定址法

以关键字本身或加某个常量c作为哈希地址的方法,h(k) = k + c,该方法适用分布基本连续时,不然内存会极大浪费

  • 除留余数法

用关键字取模不大于哈希表的长度,h(k) % p (p为不大于哈希表长度的整形),使用范围最广,比如之前介绍的HashTree底层的哈希表就是采用这种方法,该方法使映射地址的概率相同

  • 还有很多方法省略这里不做说明

4. 哈希碰撞的解决方法

4.1 开放定址法

出现哈希碰撞时在表中找一个空闲的位置存放元素

  • 线性探测法

从发生碰撞的地方依次往下探测空闲地址,若到了哈希表尾,则从头开始探测

  • 平方探测法

即在碰撞位置向前向后加上自然数的平方来找位置

4.2 拉链法

把碰撞的元素用链表拼接起来,相比开放定址法拉链法处理简单,无堆积现象,且链表可以动态改变结构,目前推荐使用拉链法

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 哈希算法的设计要点及应用场景

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇主要介绍了哈希算法相关的内容,包括什么是哈希算法、哈...

    syy
  • AI综述专栏| 大数据近似最近邻搜索哈希方法综述(上)(附PDF下载)

    在科学研究中,从方法论上来讲,都应先见森林,再见树木。当前,人工智能科技迅猛发展,万木争荣,更应系统梳理脉络。为此,我们特别精选国内外优秀的综述论文,开辟“综述...

    马上科普尚尚
  • 图像检索:基于内容的图像检索技术(四)

    基于树结构的最近邻搜索方法和基于哈希的最近邻搜索方法在理论计算机科学、机器学习以及计算机视觉中是一个很活跃的领域,这些方法通过将特征空间划分成很多小的单元,以此...

    用户3578099
  • LeetCode | 你不得不了解的哈希算法 !

    问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ?

    小小詹同学
  • 朝花夕拾-哈希表(hashTable)

    所以在Aa,BB、Ab,BC时会出现碰撞。通过如下测试代码可以发现,他们的hashCode是相同的。

    皮皮熊
  • 浅谈哈希表

    哈希表是一种根据哈希键去寻找哈希值的数据映射结构。通过该结构找到哈希键映射的位置,再根据映射的位置去寻找存放哈希值的地方。

    小蜜蜂
  • 哈希

    我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个...

    对弈

扫码关注云+社区

领取腾讯云代金券