概述

哈希表名字源于 Hash,也能够叫作散列表。哈希表是一种能够依据键(Key)直接拜访数据在内存储存方位的数据结构。它经过计算出一个键值的函数,将所需查询的数据映射到表中一个方位来让人拜访,这加快了查找速度。这个映射函数称哈希函数也叫散列函数,存放记载的数组称做 散列表 或者 哈希表

本文旨在解释哈希表的由来和基本原理,不做深入探讨,正所谓万丈高楼平地起,了解根底数据结构才能走向更高深的算法国际。

常用数据结构的查找时刻复杂度

  • 数组

    数组在存储数据时是按次序存储的,而且存储数据的内存也是连续的,所以数组内的数据,能够经过索引值直接取出得到,按方位查找的话,查找的时刻复杂度是0(1)。按条件查找的时刻复杂度是O(n),有序数组能够运用二分查找法,此刻查找的时刻复杂度能够降到O(logn)。

  • 链表

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

  • 二叉树

    假设是一般二叉树,查找的时刻复杂度 O(n)。假设是二叉查找树,则能够在 O(logn) 的时刻复杂度内完结查找动作。

  • 哈希表

    能够供给十分快速的刺进-删去-查找操作,无论多少数据,刺进和删去只需要接近常量的时刻即O(1)。

哈希表的中心思维

咱们先来看看数组的查找操作:数组是经过数据的索引(index)来取出数值的,例如要找出数组A中索引值为i的元素,那么直接经过 a[i] 就能够取出这个数据。能够看出 数组完结了“数据地址 = 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表