浅谈哈希表

1.哈希表的定义

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

最典型的例子就是字典,假设我们根据拼音索引来查找“阿”这个字的详细信息。我们肯定会去根据它的拼音“a”去查找拼音索引。结果如下:

这个过程就是键值映射。我们先看一下哈希函数的公式:

哈希值=哈希函数(哈希键)

字典的例子中,“阿-a”是哈希键,拼音索引就是哈希函数,页码就是哈希值。

2.哈希冲突

但是问题来了,如果我们要查“啊-a”或者“阿-a”两个不同的哈希键,却得到了一样的哈希值1。这就是哈希冲突。

在公式上表达就是key1≠key2,但f(key1)=f(key2)。冲突会给查找带来麻烦,你想想,你本来查找的是“阿”,但是却找到“啊”字,你又得向后翻一两页,在计算机里面也是一样道理的。

如果你要完全避开这种情况,只能每个发音都在不同的页上,然后每个字在索引里面都有对应的页码,这就可以避免冲突。但是会导致空间增大。所以一般我们认为哈希冲突是正常现象。

3.哈希冲突解决办法

如果遇到冲突,哈希表一般是怎么解决的呢?

最常用的就是开发定址法链地址法

我们主要讨论地址法,我感觉业界上用的最多的就是链地址法。

链地址法的原理是如果遇到冲突,就会在原地址新建一个空间,然后以链表结点的形式插入到该空间。

下面从百度上截取来一张图片,可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353...},而我的哈希算法是H(key)=key mod 16,第一个数据1的哈希值f(1)=1,插入到1结点的后面,第二个数据12的哈希值f(12)=12,插入到12结点,第三个数据26的哈希值f(26)=10,插入到10结点后面,第4个数据337,计算得到哈希值是1,遇到冲突,但是依然只需要找到该1结点的最后链结点插入即可,同理353。

4.哈希函数如何选择

哈希函数应该尽量减少哈希冲突的出现,哈希键对应的哈希值均匀分配在哈希表里面。

1.尽量使哈希键对应的哈希值均匀分配在哈希表里面(比如说某厂商卖30栋房子,均匀划分ABC3个区域,如果你划分A区域1个房子,B区域1个房子,C区域28个房子,有人来查找C区域的某个房子最坏的情况就是要找28次)。

2.哈希键极小的变化可以引起哈希值极大的变化。

5.关于哈希表的性能

由于哈希表高效的特性,查找或者插入的情况在大多数情况下可以达到O(1),时间主要花在计算hash上,当然也有最坏的情况就是hash值全都映射到同一个地址上,这样哈希表就会退化成链表,查找的时间复杂度变成O(n),但是这种情况比较少,只要不要把hash计算的公式外漏出去并且有人故意攻击,一般也不会出现这种情况。

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

6.回顾全文

1. 哈希键

2. 哈希值

3. 哈希表

4. 哈希值=哈希表(哈希键)

5. 哈希冲突:key1≠key2,但f(key1)=f(key2)

6. 哈希冲突解决办法:链地址法

7. 哈希函数如何选择

8. 哈希表的性能:善于查找或者插入,不善于排序

-纸上得来终觉浅,绝知此事要躬行-

本文分享自微信公众号 - 明丰随笔(liumingfengwx2),作者:刘明丰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈.Net反射 2

    C#代码在经过编译之后会得到二进制格式的程序集,程序集一般是一个.dll或.exe后缀的文件。

    小蜜蜂
  • 版本检查小工具

    我们在系统在发到live环境之后,有时候会因为发布的dll文件不是最新的版本,才导致live defect。因为live环境一般是发布专员控制,我们普通的开发人...

    小蜜蜂
  • 迭代器模式

    在面向对象编程里,迭代器模式是一种最简单也最常见的设计模式。它可以让用户透过特定的接口访问集合中的每一个元素而不用了解底层的实现。一般实现一个集合的方法有:数组...

    小蜜蜂
  • 哈希

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

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

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

    syy
  • LeetCode | 你不得不了解的哈希算法 !

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

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

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

    马上科普尚尚
  • 朝花夕拾-哈希表(hashTable)

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

    皮皮熊
  • 图像检索:基于内容的图像检索技术(四)

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

    用户3578099
  • 哈希表的理论知识

    哈希表又称散列表,若要存储的元素个数为n,设置一个长度为m(m >= n)的连续内存单元,以每个元素的关键字为自变量,通过一个称为哈希的函数把关键字映射为内存单...

    晚上没宵夜

扫码关注云+社区

领取腾讯云代金券