摘要：级别标签算法散列表哈希表作者审校团队本篇将介绍散列表哈希表的相关基础知识。该数即为散列表数组的下标。因此，散列表的最优情况就是平均情况，时间复杂度为常数级。建议高于时，考虑散列表翻倍扩容优秀的散列函数。
级别： ★☆☆☆☆
标签：「算法」「Hash」「散列表」「哈希表」
作者： MrLiuQ
审校： QiShare团队
本篇将介绍散列表（哈希表）的相关基础知识。
散列表(Hash table，也叫哈希表)是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。（来源360百科）
散列函数：简单来说是一个函数，传入一个Key就返回一个固定的数。该数即为散列表数组的下标。（用一句话描述：散列函数将“输入”映射到“数字”。）
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突(碰撞)。
常见的解决哈希冲突方案有以下四种：（详细细节见下篇讲解）
开放定址法：为产生冲突的地址H(key)求得一个新的地址序列： Hi =（H(key)+ di）% m （i=1，2，3，...，m-1） 其中H(key)为哈希函数，m为表长，di称为增量序列。（其中增量di的取值方法也有多种，详细细节见下篇）
链地址法：将所有哈希地址相同的记录都链接在同一链表中。
再哈希法：产生冲突时计算**另一个哈希函数（散列函数）**的地址，直到冲突不再发生为止。
建立公共溢出区：把冲突的值都放在另一个溢出表中，不把冲突的值存原表中。
先介绍一个散列表的专有名词：填装因子（负载因子）。
这里列出了常见数据结构操作的时间复杂度。
| / | 散列表（最佳情况） | 散列表（最坏情况） | 数组 | 链表 |
|---|---|---|---|---|
| 取值 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | O(n) | O(1) |
| 删除 | O(1) | O(n) | O(n) | O(1) |
可以看出散列表在最佳情况下的性能是很出色的，虽然最坏情况的性能不好，但我们可以通过一些手段避免掉最坏情况。因此，散列表的最优情况就是平均情况，时间复杂度为常数级O(1)。
因此，散列表在使用中需要注意两点：
较低的填装因子（或称负载因子）。（建议：高于0.7时，考虑散列表翻倍扩容）
优秀的散列函数。（尽量减少冲突的发生）
PS：Python的做法是，会设法保证大概还有三分之一的表元是空的，当快要达到这个阀值的时候，会进行扩容，将原散列表复制到一个更大的散列表里。
例如，用散列表实现一个电话薄。
主要功能如下：
加入联系人及电话号码。
通过查找对应名称首字母，得到所有该首字母名称的联系人。
图解如下：
代码如下：
# 创建一个telBook的散列表
telBook = dict()
# 将A-Z的字母作为telBook的Key，Value还是一个散列表
for ch in xrange(0x41, 0x5A):
telBook[unichr(ch)] = dict()
# 将联系人加入telBook中，取首字母作为第一个Key，名称作为第二个Key，电话作为第二个Key的Value。
def addFriend(name, phoneNumber):
telBook[name[0:1]][name] = phoneNumber
addFriend("QiShare1", 13800000000)
addFriend("QiShare2", 13811111111)
addFriend("QiShare3", 13822222222)
addFriend("QiShare4", 13833333333)
addFriend("QiShare5", 13844444444)
addFriend("QiShare6", 13855555555)
addFriend("Police", 110)
addFriend("XiaoMing1", 1)
addFriend("XiaoMing2", 2)
addFriend("XiaoMing3", 3)
# 输出结果：
for ch in xrange(0x41, 0x5A):
if telBook[unichr(ch)]:
print unichr(ch)+":"
print telBook[unichr(ch)]
打印结果如下：
小编微信：可加并拉入《QiShare技术交流群》。
关注我们的途径有：
QiShare(简书)
QiShare(掘金)
QiShare(知乎)
QiShare(GitHub)
QiShare(CocoaChina)
QiShare(StackOverflow)
QiShare(微信公众号)
推荐文章：
iOS UIButton根据内容自动布局
iOS 指定初始化方法
UIView中的hitTest方法
iOS关于tabBar的几处笔记
A的女儿是B的女儿的妈妈，A是B的谁？
算法小专栏：选择排序
iOS Runloop（一）
奇舞周刊
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/6756.html
摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...
摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...
摘要：散列是一种算法通过散列函数，将大型可变长度数据集映射为固定长度的较小整数数据集。在讨论散列函数的实现之前，让我们讨论理想的情况完美的散列函数。对于标准二次探测冲突解决方法，当哈希表的时，插入可能失败。 目录 简介 散列表的关键概念 数组和散列表 数组的问题 hash的问题 线性探测 二次探测 双倍散列 分离链接 ...
阅读 965·2019-08-30 15:55
阅读 3409·2019-08-30 13:10
阅读 1242·2019-08-29 18:45
阅读 2297·2019-08-29 16:25
阅读 2077·2019-08-29 15:13
阅读 2332·2019-08-29 11:29
阅读 525·2019-08-26 17:34
阅读 1448·2019-08-26 13:57
