聊聊哈希表

手机游戏开发者 · 2024-10-3 15:24:43

概述

哈希表名字源于 Hash，也可以叫作散列表。哈希表是一种可以根据键（Key）直接访问数据在内存储存位置的数据布局。它通过盘算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加速了查找速率。这个映射函数称哈希函数也叫散列函数，存放记载的数组称做 散列表 或者 哈希表 。
本文旨在表明哈希表的由来和根本原理，不做深入探究，正所谓万丈高楼平地起，相识底子数据布局才能走向更高深的算法世界。
常用数据布局的查找时间复杂度

数组
数组在存储数据时是按次序存储的，而且存储数据的内存也是连续的，以是数组内的数据，可以通过索引值直接取出得到，按位置查找的话，查找的时间复杂度是0(1)。按条件查找的时间复杂度是O(n)，有序数组可以使用二分查找法，此时查找的时间复杂度可以降到O(logn)。

链表
链表在存储数据时不是按次序存储的，而且存储数据的内存也是不连续的，以是链表内的数据，不能通过索引值直接取出得到，按位置查找的话，查找的时间复杂度是0(n)，按条件查找的时间复杂度也是O(n)。

二叉树
假如是平凡二叉树，查找的时间复杂度 O(n)。假如是二叉查找树，则可以在 O(logn) 的时间复杂度内完成查找动作。

哈希表
可以提供非常快速的插入-删除-查找操纵，无论多少数据，插入和删除只须要靠近常量的时间即O(1)。

哈希表的焦点头脑

我们先来看看数组的查找操纵：数组是通过数据的索引（index）来取出数值的，比方要找出数组A中索引值为i的元素，那么直接通过 a 就可以取出这个数据。可以看出 数组实现了“数据所在 = f (index)”的映射关系。
假如用哈希表的逻辑来明确的话，这里的 f () 就是一个哈希函数。它完成了索引值到现实所在的映射，这就让数组可以快速完成基于索引值的查找。然而，数组的局限性在于，它只能基于数据的索引去查找，而不能基于数据的数值去查找。
哈希表的操持采取了 函数映射 的头脑，将记载的存储位置与记载的关键字关联起来。如许的操持方式，可以大概根据记载的关键字快速定位到想要查找的记载，而且不须要与表中存在的记载的关键字比力后再来举行查找（比如二分查找）。
哈希表的焦点头脑就是实现了“数据所在 = f (关键字)”的映射关系，如许就可以快速完成基于数据的数值的查找了。

总结一下

数组实现了“所在 = f (index)”的映射关系。字典实现“所在 = f (关键字)”的映射关系
哈希函数

Hash 函数操持的优劣会直接影响到对哈希表的操纵服从
什么是哈希函数

哈希函数就是将键转化为数组索引的过程,这个函数应该易于盘算且可以大概均与分布全部的键。
假如，我们要对手机通讯录举行存储，并要根据姓名找出一个人的手机号码，如下所示：
张一：155555555
张二：166666666
张三：177777777
张四：188888888
一个可行的方法是，界说包罗姓名、手机号码的布局体，再通过线性表的方式把 4 个接洽人的信息存起来。当要判定“张四”是否在链表中，或者想要查找到张四的手机号码时，就须要从线性表的头结点开始遍历。依次将每个结点中的姓名字段，同“张四”举行比力。直到查找乐成或者全部遍历一次为止。这种做法的时间复杂度为 O(n)。
假如要低沉时间复杂度，就须要借助哈希表的思绪，构建姓名到所在的映射函数“所在 = f (姓名)”。如许我们就可以通过这个函数直接盘算出”张四“的存储位置，在 O(1) 时间复杂度内就可以完成数据的查找。
通过这个例子，不丢脸出 Hash 函数操持的优劣会直接影响到对哈希表的操纵服从。 假如对上面的例子采取的 Hash 函数为姓名的每个字的拼音开头大写字母的 ASCII 码之和。即：
address (张一) = ASCII (Z) + ASCII (Y) = 90 + 89 = 179；
address (张二) = ASCII (Z) + ASCII (E) = 90 + 69 = 159；
address (张三) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；
address (张四) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；
我们发现这个哈希函数存在一个非常致命的题目，那就是 f ( 张三) 和 f (张四) 都是 173。这种征象称作哈希辩论，是须要在操持哈希函数时举行规避的。
从本质上来看，哈希辩论只能尽大概淘汰，不能完全克制。这是由于输入数据的关键字是个开放聚集。只要输入的数据量够多、分布够广，就完全有大概发生辩论。因此哈希表须要操持公道的哈希函数，而且对辩论有一套处理机制。
操持哈希函数

哈希函数能使对一个数据序列的访问更加敏捷有用，通过散列函数，数据元素将被更快定位。
一些常用的操持哈希函数的方法：

直接定址法
取关键字或关键字的某个线性函数值为散列所在。即hash(k) = k或者hash(k) = a*k + b，a、b为常数

数字分析法
假设关键字聚集中的每个关键字 key 都是由 s 位数字构成（k1,k2,…,Ks），从中提取分布匀称的多少位构成哈希所在。上面张一、张二、张三、张四的手机号信息存储，就是使用的这种方法。

办理哈希辩论

上面这些常用方法都有大概会出现哈希辩论。产生辩论很正常，办理它就可以了
常用的方法，有以下两种：
第一，开放定址法
当一个关键字和另一个关键字发生辩论时，使用某种探测技能在哈希表中形成一个探测序列，然后沿着这个探测序列依次查找下去。当碰到一个空的单位时，则插入此中。
常用的探测方法是线性探测法。比如有一组关键字 {55,11,1,23,68,14,37,19,86}，采取的哈希函数为 key mod 11。
插入这组关键字到哈希表

h(55)=0，0的位置没数据，就把55插入0的位置

h(11)=0，0的位置已经有数据0了，以后探测发现1的位置没数据，就把11插入1的位置

h(1)=1，此时1的位置已经有数据11了，以后探测，2的位置没数据，就把1插入2的位置

h(23)=1，此时1的位置已经有数据11了，以后探测直到3的位置没数据，就把23插入3的位置

h(68)=2，此时2的位置已经有数据1了，以后探测直到3的位置没数据，就把68插入4的位置

h(14)=3，此时3的位置已经有数据23了，以后探测直到3的位置没数据，就把14插入5的位置

h(37)=4，此时4的位置已经有数据68了，以后探测直到3的位置没数据，就把37插入6的位置

h(19)=8，此时8的位置没数据，直接把19插入8的位置

h(86)=9，此时9的位置没数据，直接把86插入9的位置

查找数据：
比如查找68，h(68)=2，根据哈希表，2的位置的数据是1，这时间再去2的下一位取数据，发现是23，再往下一位，发现位置4的数据是68，此时就完成了查找。
第二，链所在法
将哈希所在相同的记载存储在一张线性链表中。
比方，有一组关键字 {55,11,01,23,68,14,37,19,86}，采取的哈希函数为 key mod 11。如下图所示：
第一次发生辩论的位置是0，这时间将11插入0位置的链表的尾部即可，23类似。
案例

例 1，将关键字序列 {7, 8, 30, 11, 18, 9, 14} 存储到哈希表中。哈希函数为： H (key) = (key * 3) % 7，处理辩论采取线性探测法。
接下来，我们分析一下创建哈希表和查找关键字的细节过程。
起首，我们实行创建哈希表，求出这个哈希所在：
H (7) = (7 * 3) % 7 = 0
H (8) = (8 * 3) % 7 = 3
H (30) = 6
H (11) = 5
H (18) = 5
H (9) = 6
H (14) = 0
按关键字序列次序依次向哈希表中填入，发生辩论后按照“线性探测”探测到第一个空位置填入。
再来看一下查找的流程：
1，查找 7。输入 7，盘算得到 H (7) = 0，根据哈希表，在 0 的位置，得到结果为 7，跟待匹配的关键字一样，则完成查找。
2，查找 18。输入 18，盘算得到 H (18) = 5，根据哈希表，在 5 的位置，得到结果为 11，跟待匹配的关键字不一样（11 不即是 18）。因此，以后挪移一位，在 6 的位置，得到结果为 30，跟待匹配的关键字不一样（11 不即是 30）。因此，继续以后挪移一位，在 7 的位置，得到结果为 18，跟待匹配的关键字一样，完成查找。
例 2，假设有一个在线体系，可以及时吸取用户提交的字符串型关键字，并及时返回给用户累积至今这个关键字被提交的次数。
比方，用户输入"abc"，体系返回 1。用户再输入"qwt"，体系返回 1。用户再输入"iot"，体系返回 1。用户再输入"abc"，体系返回 2。用户再输入"abc"，体系返回 3。
一种办理方法是，用一个数组生存用户提交过的全部关键字。当吸取到一个新的关键字后，插入到数组中，而且统计这个关键字出现的次数。
根据数组的知识可以盘算出，插入到末了的动作，时间复杂度是 O(1)。但统计出现次数必须要全部数据遍历一遍，时间复杂度是 O(n)。随着数据越来越多，这个在线体系的处理时间将会越来越长。显然，这不是一个好的方法。
假如采取哈希表，则可以使用哈希表新增、查找的常数级时间复杂度，在 O(1) 时间复杂度内完成相应。预先界说好哈希表后（可以采取 Map < String, Integer > d = new HashMap <> (); ）对于关键字（用变量 key_str 生存），判定 d 中是否存在 key_str 的记载。
假如存在，则把它对应的value（用来记载出现的频次）加 1；
假如不存在，则把它添加到 d 中，对应的 value 赋值为 1。末了，打印处 key_str 对应的 value，即累积出现的频次。
总结

哈希表的长处：
1，在查找方面，哈希表完成了关键字到所在的映射，可以在常数级时间复杂度内通过关键字查找到数据。
2，它可以提供非常快速的插入-删除-查找操纵，无论多少数据，插入和删除只须要靠近常量的时间。
哈希表的缺点：
1，哈希表中的数据是没有次序概念的，以是不能以一种固定的方式（比如从小到大）来遍历此中的元素。在数据处理次序敏感的题目时，选择哈希表并不是个好的处理方法。
2，哈希表中的 key 是不答应重复的，在重复性非常高的数据中，哈希表也不是个好的选择。
哈希表使用了数组可以通过所在直接取值的特性以实现O(1)时间复杂度完成查找，这才是哈希表的焦点之所在。
参考

使用链所在法实现 hash表

聊聊哈希表

所属分类: 问答交流

新帖推荐: 30日

推荐作品