创建一个包含两个数组的哈希表

Question

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

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

Answer 1

实际上，当今的一些 Hashmap 实现确实如您所建议的那样由数组组成。让我概述一下它是如何工作的：

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

桶 一个简单的基于数组的 Hashmap 实现可以使用存储桶来应对冲突。数组 K 中的每个元素（“桶”）本身包含一个对的数组（数组 P）。添加或查询元素时，哈希函数会将您指向 K 中的正确存储桶，其中包含所需的数组 P。然后您迭代 P 中的元素，直到找到匹配的键，或者在P 结束。

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

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

因为您通常不知道要在 Hashmap 中存储多少对象，所以最好动态增长或缩小映射。您可以对存储的对象数量进行计数，一旦超过某个阈值，您就重新创建整个结构，但这次数组 K 的大小更大或更小。这样，K 中的一些存储桶就被保留了。 very full 现在会将其元素分配到多个存储桶中，这样性能会更好。

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

您所要求的内容的变体在哈希表维基百科条目中被描述为“数组哈希表”。

代码 有关代码示例，请查看此处。

希望这有帮助。

Answer 2

你能说得更准确一点吗？一个数组包含键，另一个数组包含值吗？

如果是这样，这里有一个 Java 示例（但这里没有这种语言的特殊性）：

for (int i = 0; i < keysArray.length; i++) {
    map.put(keysArray[i], valuesArray[i]);
}

当然，您必须实例化您的

map

对象（如果您使用 Java，我建议使用

HashMap<Object, Object>

而不是过时的

HashTable

），并测试您的数组以避免

null

物体并检查它们是否具有相同的尺寸。

Answer 3

示例说明：

在下面的源代码中，基本上它做了两件事：

1.地图表示

• 一些（X 个列表）列表
• X 是 2 次方 N 的列表数量是不好的。 A (2 次方 N)-1，或 (2 次方 N)+1，或素数都可以。

示例：

List myhashmap [hash_table_size];
// an array of (short) lists
// if its long lists, then there are more collisions

注意：这是数组的数组，而不是两个数组（我看不到可能的通用哈希图，最好只用 2 个数组）

如果您了解算法>图论>邻接表，这看起来完全相同。

2.哈希函数

哈希函数将字符串（输入）转换为数字（哈希值），即数组的索引

• 将哈希值初始化为第一个字符（转换为int后）
• 对于每一个字符，左移 4 位，然后添加 char（转换为 int 后）

例如，

int hash = input[0];
for (int i=1; i<input.length(); i++) {
    hash = (hash << 4) + input[i]
}

hash = hash % list.size()
// list.size() here represents 1st dimension of (list of lists)
//      that is 1st dimension size of our map representation from point #1
//      which is hash_table_size

参见第一个链接：

int HTable::hash (char const * str) const

来源：
http://www.relisoft.com/book/lang/pointer/8hash.html
哈希表如何工作？

更新
这是最好的来源：http://algs4.cs.princeton.edu/34hash/

Answer 4

如果您想通过实施来学习，这是一本有趣的读物：https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

Answer 5

你的意思是这样吗？

以下以Ruby的

irb

为例：

 cities = ["LA", "SF", "NY"]
 => ["LA", "SF", "NY"] 

 items = ["Big Mac", "Hot Fudge Sundae"]
 => ["Big Mac", "Hot Fudge Sundae"] 

 price = {}
 => {} 

 price[[cities[0], items[1]]] = 1.29
 => 1.29 

 price
 => {["LA", "Hot Fudge Sundae"]=>1.29} 

 price[[cities[0], items[0]]] = 2.49
 => 2.49 

 price[[cities[1], items[0]]] = 2.99
 => 2.99 

 price
 => {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

 price[["LA", "Big Mac"]]
 => 2.49