hashtable - 用两个数组创建一个哈希表

Question

有谁知道如何做到这一点以及伪代码是什么样的？

众所周知，哈希表存储键值对，当调用键时，函数将返回与该键关联的值。我想要做的是了解创建该映射函数的底层结构。例如，如果我们生活在一个除了数组之外没有先前定义的函数的世界，我们如何复制我们今天拥有的 Hashmap？

Answer 1

实际上，今天的一些 Hashmap 实现确实如您所建议的那样由数组构成。让我勾勒一下这是如何工作的:

哈希函数
散列函数将您的键转换为第一个数组(数组 K)的索引。为此可以使用散列函数，例如 MD5 或更简单的函数，通常包括模运算符。

水桶
一个简单的基于数组的 Hashmap 实现可以使用桶来处理冲突。数组 K 中的每个元素('bucket')本身包含一个成对数组(数组 P)。添加或查询元素时，哈希函数会将您指向 K 中的正确存储桶，其中包含所需的数组 P。然后您遍历 P 中的元素，直到找到匹配的键，或者在P的结尾。

使用哈希将键映射到桶
您应该确保桶的数量(即 K 的大小)是 2 的幂，比如 2^b。要为某个键找到正确的桶索引，请计算 Hash(key) 但只保留前 b 位。这是转换为整数时的索引。

重新缩放
计算 key 的哈希值并找到正确的存储桶非常快。但是，一旦桶变得更满，您将不得不迭代越来越多的项目，然后才能找到正确的项目。所以有足够的桶来正确分配对象很重要，否则你的 Hashmap 会变慢。

因为您通常不知道要在 Hashmap 中存储多少对象，所以希望动态地扩大或缩小 map 。您可以对存储的对象数量进行计数，一旦超过某个阈值，您就可以重新创建整个结构，但这次对数组 K 使用更大或更小的大小。通过这种方式，K 中的一些桶是非常满现在将它们的元素分成几个桶，这样性能会更好。

替代品
您也可以使用二维数组而不是数组数组，或者您可以将数组 P 交换为链表。此外，您可以简单地选择重新创建(即重新缩放)哈希图，而不是保留存储对象的总数，一旦其中一个存储桶包含的项目数量超过某个配置数量。

您所要求的一个变体在 Hash table Wikipedia entry 中被描述为“数组哈希表”。 .

代码
有关代码示例，请查看 here .

希望这可以帮助。