Hash Table 算法数据结构基础——哈希表

1. 哈希表简介
哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。
哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。
哈希表的关键思想是使用哈希函数，将键 key 映射到对应表的某个区块中。我们可以将算法思想分为两个部分：
哈希表的原理示例图如下所示：
【Hash Table算法数据结构基础——哈希表】在上图例子中，我们使用 value = http://www.kingceram.com/post/Hash(key) = key // 1000 作为哈希函数。// 符号代表整除。我们以这个例子来说明一下哈希表的插入和查找策略。
在哈希表中搜索一个关键码值：通过哈希函数解析关键字，并在特定的区块搜索该关键字对应的值。
哈希表在生活中的应用也很广泛，其中一个常见例子就是「查字典」。
比如为了查找赞这个字的具体意思，我们在字典中根据这个字的拼音索引 zan，查找到对应的页码为 599 。然后我们就可以翻到字典的第 599 页查看赞字相关的解释了。
在这个例子中：
2. 哈希函数
哈希函数（Hash ）：将哈希表中元素的关键键值映射为元素存储位置的函数。
哈希函数是哈希表中最重要的部分。一般来说，哈希函数会满足以下几个条件：
在哈希表的实际应用中，关键字的类型除了数字类，还有可能是字符串类型、浮点数类型、大整数类型，甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中。
而关于整数类型的关键字，通常用到的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。下面我们介绍几个常用的哈希函数方法。
2.1 直接定址法
这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。
举一个例子，假设我们有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字，哈希函数取关键字自身，如下表所示。
年龄123......100
人数
3000
2000
5000
...
1050
...
...
...
...
比如我们想要查询 25 岁的人有多少，则只要查询表中第 25 项即可。
2.2 除留余数法
这也是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言，一般 p 取素数或者 m，这样可以尽可能的减少冲突。
比如我们需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中（长度为 11 的数组），通过除留余数法将这 7 个数应分别位于如下地址：
索引
数据
88
111
432
92
193
128
2.3 平方取中法
这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关，所以产生的哈希地址也比较均匀，有利于减少冲突的发生。

文章插图
2.4 基数转换法
以为例，哈希地址计算方式如下：
${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 = {10}$
3. 哈希冲突
哈希冲突（Hash ）：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) = Hash(key2)，这种现象称为哈希冲突。