Patchmap：内存高效的哈希表和伪随机排序

我已经考虑好的散列函数很长时间了，所以将两次乘法和二进制轮换结合起来得到一个输出非常均匀的散列函数并不难。这类似于Malte Skarupke最终所做的，从黄金比例的单次乘法开始，也就是斐波纳契散列，然后用位移位合成它。伽罗瓦域乘法也是一个很好的积木，但我的笔记本电脑有点旧，因此很难进行无进位乘法。

最近我想计算大量的大型直方图。计算直方图的最快方法涉及哈希表。因为c++是我最喜欢的编程语言，所以我选择std：：unorder_map作为后端。一切都很顺利，就像我想象的那样，但是当我在我的笔记本电脑上运行代码，而不是在研究所的服务器上运行代码时，一切都冻结了。所需的内存大约是我预期的8倍。当我在64位机器上将16位值映射到16位值时，我发现我触发的是std：：unordered_map接近最坏的情况。unorder_map是一个链接哈希表，这意味着对于需要存储64位指针的每对16位值，这在这种情况下会产生特别大的开销。最后，我首先对值进行排序，然后根据排序后的数组计算直方图，这花费的时间要长得多，但使用的内存最少。但我仍然有更多的可用内存，我的笔记本电脑有16 GB的内存，我只使用了6 GB。如果有一种数据结构可以在两个解决方案之间进行插值，那不是很好吗？或者至少如果有一个内存效率更高的哈希表呢？

甚至在我发现确实存在效率更高的哈希表之前，我就有了一个想法，我需要尝试一下。

正如已经暗示的那样，其思想是在排序数组和哈希表之间进行内插。也就是说，将键线性映射到哈希表，并基于键的数值解决冲突(如果冲突发生)。如果密钥是均匀分布的，则这工作得很好，并且在这种情况下具有实质上在O(1)时间和O(1)存储器中对密钥进行排序的附加效果，但是没有到位。然而，为了有效地工作，需要一些分数的额外空间，至少额外5%将是好的。

这种方法可能看起来非常类似于O.Amble D.E.Knuth(1974年1月1日)中建议的方法，但是这里的哈希表首先按键的散列排序，然后按键的值排序，这一点有很大的不同。然而，如果条目仅按散列值排序，则存在全局顺序，这突然允许诸如内插搜索和二进制搜索之类的高级搜索策略。

实际上，该方法更类似于具有线性探测的罗宾汉散列，因为如果两个密钥在相同位置发生冲突，则散列值较低的密钥也将被更多地移位，并且因此将用较大的散列值替换密钥，从而保持相同的顺序。然而，还没有使用带有线性探测的罗宾汉散列的散列表来利用这一事实。

[C++17，开源，测试版体育场，如果您想使用它，请让我知道，我会尽量让它为您工作！]。

有关补丁图内部工作原理的更详细描述，您可以查看(开放访问)：

具有最小输出大小且不会引入额外冲突的散列函数必然是双射的。双射函数正是创建哈希函数时要使用的方法。它们可以任意组合，也可以倒置。它们可以任意变得难以反转。例如，素数域上的平方求幂在密码学中使用，求逆在计算上非常昂贵，但它是双射的。认为密码散列函数的安全性取决于散列冲突是一种常见的误解。对于哈希表来说，不管好的混合是多么重要，易于反转甚至可能是一个优势。

查找是哈希表中最频繁的操作，因此它的速度势在必行。在补丁图中，因为数据是按键的散列排序的，所以对于每次查找，需要将键的散列与其他几个散列进行比较。为了加快比较速度，可以将散列与数据一起存储，就像在其他一些散列表中一样。然而，给定一个双射散列函数及其倒数，可以节省这个空间，并且我们可以只存储散列，而不是存储散列和数据。可以根据散列计算数据。

一些分配器能够调整分配的大小，类似于realloc，但是除了dlib：：allocator之外，没有C++可以公开该特性。我尝试过调整大小，可以减少增大和缩小表格的时间，但是有很多角落的情况需要正确处理，这就是为什么当前版本的补丁图中没有这个功能的原因。

如果有一种方法可以手工减少散列，以便只需要将一小部分数据实际移动到新位置，则无需重新定位就可以调整大小，这一点特别有用。据我所知，唯一能够利用这一巧妙想法的哈希表是Khash。当表大小是因子2时，哈希缩减可以简单到取n比特的哈希即可。在增长表时，这意味着只需要移动表中一半的键，这使得增长操作的成本更低。如果有一种方法可以将这个技巧推广到任意大小的哈希表就好了！