哈希算法思想（浅谈机器学习时代的哈希算法）

哈希算法思想（浅谈机器学习时代的哈希算法）本文由阿里云云栖社区组织翻译。这可能听起来像链接是更好的选择，但线性探测被广泛接受为具有更好的性能特征。在大多数情况下，这是由于差劲的高速缓存使用链表和数组的有利缓存的利用率。简短版本是检查链表中的所有链接比检查相同大小的数组的所有索引要慢得多。这是因为每个索引在数组中物理上相邻。但是，在链接列表中，每个新节点在创建时都会被赋予一个位置。这个新节点不一定与列表中的邻居物理上相邻。结果是，在链表中，列表顺序中“彼此相邻”的节点很少就我们的RAM芯片内部的实际位置而言，在物理上彼此相邻。由于我们的CPU高速缓存的工作原理，访问相邻内存位置的速度很快，并且随机访问内存位置速度要慢得多。链接：重复的冲突会创建更长的链接列表，但不会占用阵列的任何其他索引线性探测在概念上仍然很简单，但实施起来很麻烦。在线性探测中，散列表中的每个索引仍保留为单个元素。当索引i发生碰撞时，我们检查索引i 1是否为空，

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

2017年12月，谷歌和麻省理工学院的研究人员发表了一篇关于他们在“学习型指数结构”中的研究报告。这些研究非常令人兴奋，正如作者在摘要中所述：

“我们相信，通过学习模型取代数据管理系统核心组件的想法对未来的系统设计有着深远的影响，而且这项工作只是提供了可能的一瞥。”

事实上，谷歌和麻省理工学院研究人员提出的研究成果包括表明索引世界中的中坚力量新竞争的结果：B-树和哈希图。工程界对机器学习的未来感到不安，因此这篇研究论文已经在Hacker News、Reddit和工程界中进行了深入的探讨。

链接：重复的冲突会创建更长的链接列表，但不会占用阵列的任何其他索引

线性探测在概念上仍然很简单，但实施起来很麻烦。在线性探测中，散列表中的每个索引仍保留为单个元素。当索引i发生碰撞时，我们检查索引i 1是否为空，如果是，我们将数据存储在那里；如果i 1也有元素，我们检查i 2，然后i 3等等，直到找到一个空插槽。只要我们找到一个空插槽，我们插入值。再一次，查找可能不再是严格不变的时间；如果我们在一个索引中存在多个碰撞，那么在我们找到要找的项目之前，我们最终不得不搜索一系列长项目。更重要的是，每当我们发生碰撞时，我们都会增加后续碰撞的机会，因为（与链接不同）传入的项目最终会占据一个新的索引。

线性探测：给定与上面的链接图像相同的数据和散列函数，我们得到一个新的结果。导致碰撞的元素（红色）现在驻留在同一个数组中，并从碰撞索引开始按顺序占据索引。

这可能听起来像链接是更好的选择，但线性探测被广泛接受为具有更好的性能特征。在大多数情况下，这是由于差劲的高速缓存使用链表和数组的有利缓存的利用率。简短版本是检查链表中的所有链接比检查相同大小的数组的所有索引要慢得多。这是因为每个索引在数组中物理上相邻。但是，在链接列表中，每个新节点在创建时都会被赋予一个位置。这个新节点不一定与列表中的邻居物理上相邻。结果是，在链表中，列表顺序中“彼此相邻”的节点很少就我们的RAM芯片内部的实际位置而言，在物理上彼此相邻。由于我们的CPU高速缓存的工作原理，访问相邻内存位置的速度很快，并且随机访问内存位置速度要慢得多。

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

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

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

本文为云栖社区原创内容，未经允许不得转载。