散列表

作者: jimmyzha | 来源:发表于2018-11-21 20:30 被阅读0次

散列表是一种基本的数据结构,那么散列表到底是什么样的一种数据结构呢?又有哪些应用场景呢?

假如我们要从一本电话本中查找一个人的电话号码

如果这个电话本不是有序的,那我们每一行去找O(n)

如果是排列有序的,那我们可以通过二分查找O(logn)

需要注意的是O(n)O(logn)的运行时间有着天壤之别,假设每秒能查找10行,在我们使用简单查找O(n)与二分查找O(logn)耗时如下表:

如图二分查找效率已经高出很多,但是还要去扫描多行,那有没有更高效、常数级O(1)的查找呢? 这就是散列表的用武之地。

散列函数

    我通俗解释为,把输入映射(转换)到数字,并满足一些条件:

必须是一致的,相同的输入必须转换到相同的数字,例如输入”张三”时得到的是0,那么每次输入”张三”得到的数值都必须是0。

将不同的输入映射成不同的数字,最为理想的情况下将不同的输入映射到不同的数字。

散列函数又有何用处呢?

如上图,散列函数准确的指出了”张三”的存储位置,根本不用查找,因为:

散列函数将同样的输入映射到了相同的索引。

散列函数将不同的输入映射到了不同的索引。

散列函数数组内的有效索引(没有超过数组的边界)。

冲突

    前面我们假设的散列函数总是能将不同的输入映射到了数组的不同位置。而实际上,几乎不可能编写出这样的散列函数。

不同的输入被分配到了同一个数组位置上了,这就是冲突。所以只能在这个索引位置上存储一个链表。

如上图,如果散列表除第3个位置上有存储了一个列表,其它位置上都是空的,换而言之就是说,这个散列表中的所有元素都在这个链表上。那性能会很糟糕O(n)

所以,散列函数非常非常重要。

(有兴趣的朋友可以研究一下MurmurHash,https://en.wikipedia.org/wiki/MurmurHash)

一般常见语言都实现了散列表,如Java的HashMap

Go中的map

Python的字典

引伸一下应用,如Redis中字典的实现:

https://sourcegraph.com/github.com/antirez/redis@fe43406929dbf6e6316f53f891370850cd8e1c3f/-/blob/src/dict.h#L77

dictEntry:哈希表数组

size:哈希表大小

sizemask:散列表大小的掩码,用于计算索引值

used:使用节点的数量

key:键值中的键

v:键值中的值

next:下一下散列节点的指针(解决散列函数的碰撞问题)

Resize 散列表扩容

可以自行参考一下Redis的rehash与渐进式rehash,本文主要介绍一下散列表这种数据结构基础。

码农闲话

相关文章

  • 散列表

    1.啥是散列表及散列函数? 很多语言都提供了散列表的实现方式,python是用dict{ }来实现 2.有啥优势?...

  • 散列表

    基本概念(非严谨) 散列表:按照思考事物本质以及理想状态的思路,那么散列表从本质来讲就是一个表,而理想的散列表应该...

  • 散列表

    散列表:散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f...

  • 散列表

    转载请注明出处!https://www.jianshu.com/p/e325578eb512 链表实现 Githu...

  • 散列表

    一、定义 散列表(Hash Table,也叫哈希表),是通过把键值映射成整数来作为数组的索引,并进行访问记录的一种...

  • 散列表

    https://blog.csdn.net/pcwl1206/article/details/83582986

  • 散列表

    散列查找法的两项基本工作 计算位置:构造散列函数直接确定关键词存储位置散列函数的设计,主要目的是构造随机性:计算简...

  • 散列表

    散列表是一种基本的数据结构,那么散列表到底是什么样的一种数据结构呢?又有哪些应用场景呢? 假如我们要从一本电话本中...

  • 散列表

    散列表 认识散列表 是 字典(键 、值对)的一种实现方式。每次在字典中获取一个值,都需要重复遍历字典,如果用散列表...

  • 散列表

    散列函数将被查找的键转换为数组的索引 解决冲突的方法:拉链法和线性探测法 将整数散列最常见的方法是除留余数法,通常...

网友评论

      本文标题:散列表

      本文链接:https://www.haomeiwen.com/subject/xurhqqtx.html