散列表（一） - 单词拼写与检查功能的实现

1. 散列思想

散列表利用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

2. 散列函数

散列函数定义为 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

该如何构造散列函数？有三点基本要求：

• 散列函数计算得到的散列值是一个非负整数；
• 如果 key1 = key2，那 hash(key1) == hash(key2)；
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

第一、二点很好理解，第三点实际上几乎不可能，因为它无法避免散列冲突。

3. 散列冲突

解决方法：开放寻址法和链表法。

开放寻址法

核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。探测方法有线形探测、二次探测和双重散列。

线性探测

• 插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
• 查找数据：通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等。如果相等，则说明就是要找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。
• 删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为 deleted，当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。

结论：最坏的时间复杂度为O(n)

二次探测

线性探测每次探测的步长为1，即在数组中一个个探测，而二次探测的步长变为原来的平方。

双重散列

使用一组散列函数，直到找到空闲位置为止。

散列表用装载因子（load factor）来表示空位的多少，计算公式是：

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

链表法

更加常用，比开放寻址法简单。

在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

• 插入数据：当插入的时候，通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以时间复杂度为 O(1)。
• 查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数 k=n/m，其中 n 表示散列表中数据的个数，m 表示散列表中槽的个数，所以时间复杂度为 O(k)。

思考

1. Word 文档中单词拼写检查功能是如何实现的？
2. 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
3. 有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？

自己是从事了七年开发的Android工程师，不少人私下问我，2019年Android进阶该怎么学，方法有没有？

没错，年初我花了一个多月的时间整理出来的学习资料，希望能帮助那些想进阶提升Android开发，却又不知道怎么进阶学习的朋友。【包括高级UI、性能优化、架构师课程、NDK、Kotlin、混合式开发（ReactNative+Weex）、Flutter等架构技术资料】，希望能帮助到您面试前的复习且找到一个好的工作，也节省大家在网上搜索资料的时间来学习。

资料获取方式：加入Android架构交流QQ群聊：513088520 ，进群即领取资料！！！

点击链接加入群聊【Android移动架构总群】：加入群聊

资料大全