一系列用于哈希查找的简洁算法

本节是顺序查找和二分法的延续。 本节相对独立，因此，如果您只想了解哈希表和哈希查找，请阅读此部分。 如果您想对搜索算法有一个系统的了解，我们建议您先阅读上一节。

本文前三段都是基础介绍，没有具体的算法问题，如果对这部分知识有一定的了解，可以直接跳到第四部分。

正如我们前面提到的，使用顺序查找方法来确认未排序数组中元素的存在的时间复杂度为o(n)。基本类似于蛮力查找，没有什么特殊技能可言，具体时间取决于运气，但平均而言，它与阵列的大小呈线性关系。 如果数组被排序，我们可以使用时间复杂度为o(log(n))。但分拣本身是有代价的。 正如我们将在接下来的几节中看到的那样，排序是一个相当昂贵的过程。 因此，仅仅为了更容易找到数组而对数组进行排序是非常不经济的。

那么有没有一种搜索方法，既不要求数组排序好，又能达到很高的搜索效率呢？

正如标题所暗示的那样，这种方法是存在的。

对于我们前面讨论的两次查找，给定一个任意值，例如整数 4，可以存在于数组中的任何位置。 例如，对于长度为 8 的数组a[8]，4 此值可能不存在，或者可能存储在a[0]a[7]介于两者之间。 这使得我们很难找到它：我们事先不知道它可能在哪里，所以我们需要使用各种愚蠢的方法来枚举、探测和缩小它的范围。

这给了我们一个新想法：如果我们能在一个值和它可能存储的位置之间建立关系，那么当我们想要找到一个值时，我们只需要看一眼可能的位置。 如果没有，则该元素不在数组中。 这样，我们就可以完成查找，而不必遍历整个数组。

让我们举一个最简单的例子：假设我们有一个大小为 5 的数组a[5]用于存储整数，数组起初是空的。

此时，需要存储一个新值 38。 这一次我们没有把它放在先到先得的基础上a[0]取而代之的是，我们事先商定了一个规则：传入值存储在等于该数字除以 5 的余数的位置。 。所以我们把 38 放进去a[3]

后来又出现了几个数字，我们遵循取 5 的余数并将它们分开放置的规则a[1] a[0] a[4] a[2]

存储任务完成。

如果我想找到它，我该怎么办？假设我们想查看数组中是否存在 4，我们不必遍历整个数组。 我们知道每个数字的存储位置等于其除以 5 的余数，因此我们只需要遵循此规则a[4]看看那里。 “是”就是“是”，“否”就是“否”。 请注意，时间复杂性是o(1)！这意味着，在理想情况下，无论阵列有多大，我们都可以将其淘汰，因为我们知道存储规则一个相应的门，只要打开这扇门我们就可以判断结果。 此过程的时间损失是恒定的，与阵列大小无关。

这是最简单的哈希表。 除其他外x%5它是它的哈希函数，通过哈希函数，我们将每个传入的值映射到它应该去的地方。 这使我们非常方便地找到它：现在我们知道它要去哪里，我们只需要去这个位置看一看。

以上是一个理想的基本哈希表。 您可能发现了很多问题：

例如，如果出现两个数字，则余数除以 5 相等跟此时如何分配房间？

除以 5 是心血来潮吗，为什么不除以 6？

好吧，便利并非没有代价。 一个被选中了o(1)方式，有必要打包并承担它带来的所有问题。

上述哈希函数的最大问题是它们会导致冲突。 当两个数字到 5 的余数相等时，它们争夺相同的位置。 因此，如何将每个传入号码映射到一个唯一的位置是设计哈希函数时的一个大问题。

一种可能的解决方案是使余数除数非常大，以便在一定程度上避免冲突。 假设如果除数设置为 10000000，那么 10000000 以内的整数可以通过取它的余数来获得一个唯一值，并且它们都会被分配到不同的房间，所以不会发生冲突。

但以成本计算，您必须相应地准备 10,000,000 个房间。 这对记忆来说是一个巨大的挑战。 除非我们有很多元素，否则你可以想象这种内存利用率是极低的。

另一种方法是拆解一个大数字，例如，如果我们想存储一个**数字 135-234-232-10。 我们可以把它拆成一个三位一体，总结一下：。在这种情况下，如果数组大小为 12，则余数为 11。

另一种常用的方法是所谓的中方法。 假设我们要存储的数字是 35，求其平方，取中间两位数得到 22，然后根据数组的大小取余数。

如果我们存储的不是整数，而是一个字符，那么我们也可以通过获取 ASCII 代码来获取该值的值，然后设计哈希函数。

总之，设计哈希函数有许多常用的方法，但没有系统的一刀切方法。 这里的要点是：

尽量避免冲突，尽量提高空间利用率，根据存储对象的性质设计不同的哈希函数例如，如果我们存储的数字都是 5 的倍数（比如网球比赛的比分，那么使用余数就不合适了），这里可以参考一些哈希函数的设计。 基本上，无论哈希函数设计得多么巧妙，冲突在某种程度上总是不可避免的。 那么，如果发生冲突怎么办？如果阵列已满，每个位置都有人，那么当然没有别的办法了。 即使对于一般数组也是如此，因此我不会在这里讨论它。 要考虑的情况是，如果数组中仍有空白空间，那么自然的选择是为新元素找到一个次优位置。

问题是如何找到它

我们使用empty指示阵列的空插槽中没有人。 假设取了 7 的盈余，数组当前如下所示：

a[7] = [35, empty, empty, 3, 11, 19, 34];

一种方法是存储在附近，如果该位置中已经有余数为 0 的人，则将其保存到余数为 1 的位置，如果仍然不起作用，则将其保存到下一个位置，依此类推。 这种方法称为线性探测。

这种方法的优点是它很简单，但潜在的问题是，如果某个位置有很多冲突的值，除了最先占据的元素外，所有元素都会被推迟。 请注意，此线性探测是 ***。 与上面的示例一样，保存了 7 个a[1]，这也使得那些余数为 1 的数字必须找到另一个位置，这可能会产生连锁效应：在a[0]在这个街区附近，所有的数字都不在它们应该在的地方。

一种方法是一次移动一个以上的位置，以确保整个阵列均匀分布。 这样，它就不会纠缠在一个角落（聚类）。 所以，除了加一个，我们也可以加三，加五。 此过程以下列方式表示：

new_position = (original_positon + offset) %array_size

另一种方法是用它设置一个固定的offset我们可以更改这个值，例如，在开始时通过添加一个来查找空缺位置，如果它不起作用，则添加 4，如果它不起作用，则添加 9、16、25......

处理冲突的另一种方法是链寻址。 这意味着原始数组不是存储特定值，而是在每个房间中放置一个映射（指针），该映射指向导致相同余数的元素集。 这听起来很复杂，但让我们用下图（除以 5）来说明它：

第一行用于存储指针，如果出现相应的元素，则将其放入相应的链中。 这种方法的优点是我们可以确定一个元素在哪个链中，例如，与启发式不同，我们不必担心余数为 2 到 3 的数字。 但是，缺点也是可想而知的，随着链长的增加，查找的难度也随之增加，地图本身的存储也占用了一定的内存量。

那么这两种方法哪一种更好呢？这个问题这里就不赘述了，有兴趣的可以参考这里。 示例 1创业公司一直坚持小而美的理念，员工人数一直保持在11人以下。 设计一种数据类型来存储每个员工的工作编号和工资，并要求在给定某个员工编号时，可以在o(1)（或返回：员工编号不存在）。 作业编号的格式为：yyyymmdd，输入日期，例如，工资以美元计量，例如：。具体需要的实现类如下：

类员工信息： def init （self，size）： 定义**的大小，以及两个项目：工作编号和工资 selfsize = size self.id = [none]*self.size self.salary = [none]*self.size def set（self，id，salary）： 该函数用于输入数据，输入员工编号和工资，并保存在数据表中 def get（self，id）： 此函数返回具有员工 ID 的员工工资 def hash function（self，id）： 定义哈希函数 def collision resolve（self， origin， offset）：定义冲突解决方案，无论此处可以使用哪种方法

class employee_info: def __init__(self,size): self.size = size self.id = [none]*self.size self.salary = [none]*self.size def set（self，id，salary）： 找到职位编号对应的哈希值，这里用的余数方法是员工编号 %selfsize hash_value = self.hash function（id） 如果对应房间没有人，很简单，如果自己id[hash_value] == none: self.id[hash_value] = id self.salary[哈希值] = salary 如果房间里有人，则应进行冲突解决 否则： time = 1 这用于测试地址，直到 self 出现空缺id[hash_value] != none：二次探测偏移量 = time**2 用于通过冲突解决函数确定下一个暂定房间 hash 值 = self碰撞解析（哈希值，偏移量） 时间 += 1 到自身id[hash_value] = id self.salary[hash value] = salary def get（self，id）： 或者找到对应的哈希值 = selfhash_function(id) if self.id[hash_value] == none: return '作业编号不存在！'否则，开始寻找它，如果进展顺利，就找到一次，否则你必须遵循二次探测的可能位置，直到工作编号的值与 time = 1 匹配，而 selfid[hash_value] != id: offset = time*2 hash_value = self.冲突 resolve（hash value，offset） time += 1 被找到，返回对应的工资返回 selfsalary[hash value] def hash function（self， key）： 余数返回 key%self。size def collision resolve（self， origin， offset）： 冲突解决返回 （origin+offset）%self。size

我们输入一组数据来执行测试：

t = employee_info(11)t.set(20131225,180000)t.set(20140825,90000)t.set(20141110,112300)t.set(20141121,112300)print t.idprint t.salaryprint t.get(20131225)print t.get(20111220)

[20141110、20140825、无、无、20131225、20141121、无、无][112300、90000、无、无、180000、112300、无、无] 180000 不存在

上述实现是一个最小化的类，仅用于说明目的。 即使只是为了习修炼，也有一些基本的事情需要考虑。

西在上面的**中，假设有人加薪，工号为20140824的员工的工资从96,000涨到了112,200，这个时候我们该如何更新呢？与现有的set该功能能解决问题吗？如果没有，请修改set功能可以满足这一需求。 或者再添加一个update功能。

例如，如果有人离开了公司，数据自然被删除，那么是否应该定义一个？del像这样的功能？这是如何工作的？

此外，如果我们定义一个包含 11 个数据的表并输入 12 条数据，此时会发生什么？如何修改上面的**，保证输入的数据不超过数据表的大小？

这些问题留给大家，如果写出相应的**（不管是什么语言），请记得分享给我！

Python 自带dict此数据类型可以方便地用于存储键值等数据。 在下面的示例中，我们将使用它。 当然，你也可以用它来代替它，但稍微改变一下你在上一节写的哈希表，你也可以用它来解决下面的问题。 dict使用方法非常简单，详情可以看这里。 示例 2给定一个数组和一个目标值，从数组中找到两个数字，使它们的总和等于目标值，返回数组中两个数字的下标（从开头开始）。

比如，给定跟，则返回两个下标 1 和 3，注意这里的下标从 1 开始。

这是 leetcode 的第 1 个问题，难度中等。 这里的假设是答案必须存在并且是唯一的。 一个自然愚蠢的方法是，每次我们轮询一个数字时，我们都会遍历数组的其他元素，看看是否有任何可以匹配的元素。 但在这种情况下，在最坏的情况下可以达到时间复杂度o(n^2)。更好的方法是利用哈希表的强大功能，通过快速查找元素的存在与否来降低复杂性。 因此，可能的流程是这样的：1使用哈希表来存储数组的元素和下标; 2.循环访问新创建的哈希表，从第一个元素开始，查看是否有另一个可以匹配的元素，直到找到它。 由于我们有哈希表，因此该过程的第二步在最坏的情况下会很复杂o(n)

再进一步想想，第一步和第二步其实是可以组合起来的：每次有元素进来的时候，我们先看看哈希表是否已经有匹配的元素，如果有，我们可以直接返回结果。 如果没有，请将新元素存储在哈希表中。 如果你这样想，它可能是这样的：

num 是数组，target 是目标值 def two sum（num， target）： 创建一个新的 python dict 数据类型 d = {}for i in range（len（num））：if target-num[i] in d 如果匹配值已经在哈希表中，则只需返回两个下标 返回 i+1， d[target-num[i]] else： 以数值为键， 并将以下内容标记为值，以便我们可以通过数值快速找到 d[num[i]] = i + 1

这是 leetcode 的第 3 个问题，难度中等。 不难看出，这是另一个需要我们经常判断的问题if a is in b标题。 通常，在这种情况下，哈希表可能会派上用场。 基本思想是，由于它是一个子字符串，我们需要有两个指针（或标记变量）来标识子字符串的开始和结束。 基本过程是我们对整个字符串进行遍历，如果在当前子字符串中遇到新字符和其他重复项，我们停下来查看当前字符串的长度，与当前最长的长度相比，如果它比最长的长度长，我们更新它，否则我们继续向下走。

def lengthoflongestsubstring(self, s): if s == ''：如果是空字符串，不要费心返回 0 slist = 列表 定义一个哈希表来记录字符出现的最近位置 dict = {} 记录最大长度 len = 0 记录每个子字符串的起始下标 start = 0 for i in range（len（slist））： 遍历所有字符串 if slist[i] in dict： 当前角色至少出现过一次。但是，如果它不在当前字符串中，请不要在意，如果它在当前字符串中 将当前子字符串的长度与最大 len 进行比较，其长度为 if（dict[slist[i]] = start）： max len = max（max len， i-start） 重置新子字符串的开头 请注意，这里不能将其设置为 i+1， 但应该是 dict[slist[i]]+1，为什么？start = dict[slist[i]]+1 如果不存在，则记录 dict[slist[i]] = i max len = max（max len，len（slist）-start） return max len