来，咱们聊聊机器学习时代的哈希算法～

机器学习基础

为了理解机器学习如何被用来重新创建哈希表（和其他索引）的关键特征，我们需要快速重新审视统计建模的主要思想。统计模型是一种函数，它接受一些向量作为输入，并返回：标签（用于分类）或数值（用于回归）。输入向量包含有关数据点的所有相关信息，标签/数值输出是模型的预测。

在预测高中生是否会进入哈佛大学的模型中，向量可能包含学生的GPA、SAT分数、该学生所属的课外俱乐部数量以及与其学业成绩相关的其他数值；该标签将是真/假（会进入/不会进入哈佛）。

在预测抵押贷款违约率的模型中，输入向量可能包含信用评分值、信用卡账户数量、延迟付款频率、年收入以及与申请抵押贷款的人的财务状况相关的其他值；该模型可能会返回0到1之间的数字，表示违约的可能性。

通常，机器学习用于创建统计模型。机器学习从业者将大型数据集与机器学习算法相结合，并且在数据集上运行算法的结果是训练有素的模型。机器学习的核心是创建算法，该算法可以从原始数据自动构建精确的模型，而无需人类帮助机器“理解”数据实际表示的内容。这与其他形式的人工智能不同，人类对数据进行广泛检查，为计算机提供有关数据含义的线索（例如通过定义启发式算法），并定义计算机将如何使用该数据（例如，使用最小最大值或A *）。然而，在实践中，机器学习经常与经典的非机器学习技术相结合，人工智能代理商会经常使用学习和非学习策略来实现其目标。

考虑着名的国际象棋“深蓝”和最近广受好评的“AlphaGo”。深蓝是完全非机器学习的AI；人类计算机程序员与人类国际象棋专家合作创建一个函数，该函数将棋局的状态作为输入（所有棋子的位置，以及该棋手的状态），并返回与该状态的“良好”相关的值对于深蓝。深蓝从来没有“学过”任何东西，而是人类国际象棋运动员苦苦编纂机器的评估功能。深蓝的主要特点是树搜索算法，它允许它计算所有可能的移动，以及它的所有对手对这些移动的可能响应，以及将来的许多移动。

AlphaGo树搜索的可视化。

AlphaGo也执行树搜索，就像Deep Blue一样，AlphaGo在每一个可能的移动中都会看到几个动作。与Deep Blue不同，AlphaGo创建了自己的评估功能，没有Go专家的明确指示。在这种情况下，评估函数是一个训练有素的模型。AlphaGo的机器学习算法接受Go的状态（对于每个位置，是否有白色的石头、黑色的石头或没有石头），标签代表哪个玩家赢得了游戏（白色或黑色）。利用这些信息，在数十万种游戏中，机器学习算法决定了如何评估任何特定的电路板状态。AlphaGo通过观察数以百万计的例子，教会自己哪种举动将提供最高的胜利可能性。

（这是一个非常重要的简化，就像AlphaGo的工作原理一样。你可以从AlphaGo的创建者那里了解更多关于AlphaGo的信息。）

模型作为指标，从ML标准出发

Google的研究人员在他们的论文中首先提出了索引是模型的前提，或者至少可以使用机器学习模型作为索引。理由是：模型是接受一些输入并返回一个标签的机器；如果输入是关键字，标签是模型对内存地址的估计，那么可以使用模型作为索引。虽然这听起来很简单，但索引问题显然不适合机器学习。以下是谷歌团队不得不脱离机器学习规范以实现其目标的一些领域。

通常情况下，机器学习模型会根据其所了解的数据进行训练，并负责对未见数据进行估算。当我们对数据建立索引时，估计是不可接受的。索引唯一的工作是实际查找内存中某些数据的确切位置。Google通过跟踪训练期间每个节点所经历的最大（最正）和最小（最负）误差来处理这个问题。使用这些值作为边界，ML索引可以在这些边界内执行搜索以查找元素的确切位置。

另一个出发点是机器学习从业者通常必须小心避免将他们的模型“过度拟合”到训练数据上；这样的“过度拟合”模型将对其所训练的数据产生高度准确的预测，但通常会对训练集外的数据执行得非常糟糕。另一方面，索引从定义上讲是过度拟合的。训练数据是被索引的数据，也使其成为测试数据。由于查找必须发生在索引的实际数据上，所以在这种机器学习应用中，过度拟合更容易被接受。同时，如果模型过度适合现有数据，则向索引添加项目可能会产生可怕的错误预测；正如文件中指出的那样：

这个模型的普遍性和“最后一英里”表现似乎有一个有趣的折衷; “最后一英里”预测越好，可以说，模型过度拟合的能力就越强，而对新数据项的推广能力就越差。

最后，训练模型通常是该过程中最昂贵的部分。不幸的是，在广泛的数据库应用程序（和其他索引应用程序）中，向索引添加数据相当普遍。

学习哈希

该论文审查了使用机器学习模型替代标准哈希函数的可能性。研究人员有兴趣了解的一个问题是：知道数据的分布能否帮助我们创建更好的索引？通过我们上面探讨的传统策略（移位乘法、murmur hash、素数乘法...），数据的分布被明确忽略。每个传入项目都被视为一个独立的值，而不是作为具有宝贵属性的较大数据集的一部分来考虑。结果是，即使在很多先进的哈希表中，也存在很多浪费的空间。

哈希表的实现具有大约50％的内存利用率是常见的，这意味着哈希表占用了实际需要存储的数据两倍的空间。换句话说，当我们存储与数组中存储的数量完全一样多的项时，哈希表中的一半地址仍为空。通过用机器学习模型替换标准哈希表实现中的哈希函数，研究人员发现它们可以显着减少浪费的空间量。

这并不是特别令人意外的结果：通过对输入数据进行训练，学习的散列函数可以更均匀地在一些空间上分布值，因为ML模型已经知道数据的分布！然而，这是一种潜在的强大方式，可以显着减少基于散列索引所需的存储量。这带来了一个折衷：ML模型比我们上面看到的标准哈希函数要慢一些，并且需要一个标准哈希函数不需要的训练步骤。

也许使用基于ML的散列函数可以用于有效的内存使用，但关键问题是计算能力很大的情况下。谷歌/麻省理工学院的研究小组认为数据仓库是一个很好的用例，因为计算能力正在很快的提升过程中；使用更多的计算时间来获得显着的内存节省可能是许多数据仓库环境的一个胜利。

但还有一个情节扭转，进入布谷鸟哈希。

布谷鸟哈希（Cuckoo Hashing）

布谷鸟哈希于2001年发明，并以布谷鸟命名。布谷鸟哈希是链接和线性探测碰撞处理的替代方案（不是替代哈希函数）。该策略的名称也有一定的来历，因为在某些布谷鸟种群中，准备下蛋的雌性会找到一个被占领的巢穴，并将它现有的卵子从它上面取下来以便自己放置。在布谷鸟哈希中，传入的数据会窃取旧数据的地址，就像布谷鸟鸟偷走对方的巢穴一样。

以下是它的工作方式：当你创建你的哈希表时，你立即将表分成两个地址空间；我们会称它们为主要和次要地址空间。此外，还可以初始化两个独立的散列函数，每个地址空间一个散列函数。这些散列函数可能非常相似，例如它们都可以来自“主要乘数”族，其中每个散列函数使用不同的素数。我们将这些称为主要和次要散列函数。

最初，插入布谷鸟哈希仅使用主哈希函数和主地址空间。当发生冲突时，新数据会清除旧数据；然后将旧数据与次散列函数进行散列并放入次地址空间。

如果该次要地址空间已被占用，则会发生另一次逐出，并将次要地址空间中的数据发送回主地址空间。因为有可能造成无限的驱逐循环，所以通常设置逐出驱逐的门槛；如果达到这种驱逐次数，则重建该表，这可能包括为该表分配更多空间和/或选择新的散列函数。

双重驱逐：传入的黄色数据驱逐绿色，绿色驱逐红色，红色在主地址空间找到一个新家（淡红点）

众所周知，这种策略在记忆受限的场景中是有效的。所谓的“两种选择的力量”允许布谷鸟哈希即使在非常高的利用率下也具有稳定的性能（这不是链式或线性探测的真实情况）。

Bailis和他在斯坦福大学的研究团队发现，通过一些优化，布谷鸟散列速度可以非常快，即使在99％的利用率下也能保持高性能。从本质上讲，布谷鸟哈希可以通过利用两种选择的力量，在没有昂贵的训练阶段的情况下实现机器学习的哈希函数的高度利用。

索引的下一步是什么？

最终，每个人都对能够学习的索引结构的潜力感到兴奋。随着越来越多的ML工具的推出，像TPU这样的硬件进步使机器学习工作负载更快，索引可以越来越受益于机器学习策略。与此同时，像布谷鸟哈希这样的漂亮算法提醒我们，机器学习不是万能的。融合了机器学习技术和古老理论（如“两种选择的力量”）的令人难以置信的力量将继续提高计算机效率和能力的界限。

索引的基本原理似乎不可能一夜之间被机器学习策略所取代，但自调整索引的想法是一个强大而令人兴奋的概念。随着我们继续更善于利用机器学习，并且随着我们不断提高计算机处理机器学习工作负载的效率，利用这些进步的新想法必将找到主流使用方式。下一个DynamoDB或Cassandra可能会很好地利用机器学习策略，PostgreSQL或MySQL的未来实现最终也可能采用这种策略。最终，这将取决于未来研究的成功，这将继续建立在最先进的非学习策略和“AI革命”的尖端战术上。

本文由阿里云云栖社区组织翻译。

文章原标题《an-introduction-to-hashing-in-the-era-of-machine-learning》，

译者：虎说八道，审校：袁虎。