同步操作将从 程序员充电站/LeetCode-Py 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
哈希表(Hash Table):也叫做散列表。是根据关键码值(Key Value)直接进行访问的数据结构。
哈希表通过「键 $key$」和「映射函数 $Hash(key)$」计算出对应的「值 $value$」,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做「哈希函数(散列函数)」,存放记录的数组叫做「哈希表(散列表)」。
哈希表的关键思想是使用哈希函数,将键 $key$ 映射到对应表的某个区块中。我们可以将算法思想分为两个部分:
哈希表的原理示例图如下所示:
在上图例子中,我们使用 $value = Hash(key) = key // 1000$ 作为哈希函数。$//$ 符号代表整除。我们以这个例子来说明一下哈希表的插入和查找策略。
哈希表在生活中的应用也很广泛,其中一个常见例子就是「查字典」。
比如为了查找 「赞」 这个字的具体意思,我们在字典中根据这个字的拼音索引 zan
,查找到对应的页码为 $599$。然后我们就可以翻到字典的第 $599$ 页查看 「赞」 字相关的解释了。
在这个例子中:
zan
可以看做是哈希表中的 「关键字 $key$」。哈希函数(Hash Function):将哈希表中元素的关键键值映射为元素存储位置的函数。
哈希函数是哈希表中最重要的部分。一般来说,哈希函数会满足以下几个条件:
在哈希表的实际应用中,关键字的类型除了数字类,还有可能是字符串类型、浮点数类型、大整数类型,甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型,再通过哈希函数,将其映射到哈希表中。
而关于整数类型的关键字,通常用到的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。下面我们介绍几个常用的哈希函数方法。
这种方法计算最简单,且不会产生冲突。适合于关键字分布基本连续的情况,如果关键字分布不连续,空位较多,则会造成存储空间的浪费。
举一个例子,假设我们有一个记录了从 $1$ 岁到 $100$ 岁的人口数字统计表。其中年龄为关键字,哈希函数取关键字自身,如下表所示。
年龄 | 1 | 2 | 3 | ... | 25 | 26 | 27 | ... | 100 |
---|---|---|---|---|---|---|---|---|---|
人数 | 3000 | 2000 | 5000 | ... | 1050 | ... | ... | ... | ... |
比如我们想要查询 $25$ 岁的人有多少,则只要查询表中第 $25$ 项即可。
这也是一种简单且常用的哈希函数方法。其关键点在于 $p$ 的选择。根据经验而言,一般 $p$ 取素数或者 $m$,这样可以尽可能的减少冲突。
比如我们需要将 $7$ 个数 $[432, 5, 128, 193, 92, 111, 88]$ 存储在 $11$ 个区块中(长度为 $11$ 的数组),通过除留余数法将这 $7$ 个数应分别位于如下地址:
索引 | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
数据 | 88 | 111 | 432 | 92 | 5 | 193 | 128 |
这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关,所以产生的哈希地址也比较均匀,有利于减少冲突的发生。
以 $343246$ 为例,哈希地址计算方式如下:
$343246_{13} = 3 \times 13^5 + 4 \times 13^4 + 3 \times 13^3 + 2 \times 13^2 + 4 \times 13^1 + 6 \times 13^0 = 1235110_{10}$
哈希冲突(Hash Collision):不同的关键字通过同一个哈希函数可能得到同一哈希地址,即 $key1 \ne key2$,而 $Hash(key1) == Hash(key2)$,这种现象称为哈希冲突。
理想状态下,我们的哈希函数是完美的一对一映射,即一个关键字($key$)对应一个值($value$),不需要处理冲突。但是一般情况下,不同的关键字 $key$ 可能对应了同一个值 $value$,这就发生了哈希冲突。
设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类:「开放地址法(Open Addressing)」 和 「链地址法(Chaining)」。
开放地址法(Open Addressing):指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止。
当发生冲突时,开放地址法按照下面的方法求得后继哈希地址:$H(i) = (Hash(key) + F(i)) \mod m$,$i = 1, 2, 3, ..., n (n ≤ m - 1)$。
举个例子说说明一下如何用以上三种冲突解决方法处理冲突,并得到新地址 $H(i)$。例如,在长度为 $11$ 的哈希表中已经填有关键字分别为 $28$、$49$、$18$ 的记录(哈希函数为 $Hash(key) = key \mod 11$)。现在将插入关键字为 $38$ 的新纪录。根据哈希函数得到的哈希地址为 $5$,产生冲突。接下来分别使用这三种冲突解决方法处理冲突。
使用这三种方法处理冲突的结果如下图所示:
链地址法(Chaining):将具有相同哈希地址的元素(或记录)存储在同一个线性链表中。
链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法,链地址法更加简单。
我们假设哈希函数产生的哈希地址区间为 $[0, m - 1]$,哈希表的表长为 $m$。则可以将哈希表定义为一个有 $m$ 个头节点组成的链表指针数组 $T$。
这样在插入关键字的时候,我们只需要通过哈希函数 $Hash(key)$ 计算出对应的哈希地址 $i$,然后将其以链表节点的形式插入到以 $T[i]$ 为头节点的单链表中。在链表中插入位置可以在表头或表尾,也可以在中间。如果每次插入位置为表头,则插入操作的时间复杂度为 $O(1)$。
而在在查询关键字的时候,我们只需要通过哈希函数 $Hash(key)$ 计算出对应的哈希地址 $i$,然后将对应位置上的链表整个扫描一遍,比较链表中每个链节点的键值与查询的键值是否一致。查询操作的时间复杂度跟链表的长度 $k$ 成正比,也就是 $O(k)$。对于哈希地址比较均匀的哈希函数来说,理论上讲,$k = n // m$,其中 $n$ 为关键字的个数,$m$ 为哈希表的表长。
举个例子来说明如何使用链地址法处理冲突。假设现在要存入的关键字集合 $keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]$。再假定哈希函数为 $Hash(key) = key \mod 13$,哈希表的表长 $m = 13$,哈希地址范围为 $[0, m - 1]$。将这些关键字使用链地址法处理冲突,并按顺序加入哈希表中(图示为插入链表表尾位置),最终得到的哈希表如下图所示。
相对于开放地址法,采用链地址法处理冲突要多占用一些存储空间(主要是链节点占用空间)。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中,待比较的关键字都是具有相同哈希地址的元素,而在开放地址法中,待比较的关键字不仅包含具有相同哈希地址的元素,而且还包含哈希地址不相同的元素。
本文讲解了一些比较基础、偏理论的哈希表知识。包含哈希表的定义,哈希函数、哈希冲突以及哈希冲突的解决方法。
哈希表的两个核心问题是:「哈希函数的构建」 和 「哈希冲突的解决方法」。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。