有谁知道如何做到这一点以及伪代码是什么样的？我们都知道一个哈希表存储键，值对，并且当一个键被调用时，函数将返回与该键相关联的值。我想要做的是了解创建映射函数的底层结构。例如，如果我们生活在一个除了数组之外没有预先定义的函数的世界中，我们如何复制我们今天的哈希表？用两个数组创建一个哈希表

来源

2010-11-06 locoboy

你能成为一个更确切的一点？你想要达到什么目的？您是否针对特定语言？ – romaintaz 2010-11-06 16:54:29

@romaintaz请参阅上面的说明 – locoboy 2010-11-06 22:07:48

事实上，一些今天的Hashmap implentations确实做出来阵列的，你建议。让我素描是如何工作的：

Hash函数 散列函数变换钥匙进入第一个阵列（列K）的索引。散列函数（如MD5）或更简单的散列函数（通常包括模运算符）可用于此目的。

存储桶 一个简单的基于数组的Hashmap实现可以使用存储桶来处理collies。数组K中的每个元素（'bucket'）都包含一个数组（数组P）。当添加或查询元素时，散列函数将您指向K中正确的桶，其中包含所需的数组P.然后，遍历P中的元素直到找到匹配的键，或者在P.

映射按键

端使用哈希 桶，你应该确保（即K的大小）桶的数量是2的幂，比方说2^b。要为某个密钥找到正确的桶索引，请计算哈希（密钥），但只保留前b位。这是您的索引时转换为整数。

重新调整 计算密钥的散列并找到正确的存储区非常快。但是一旦桶变得更加饱满，在你找到合适的桶之前，你必须迭代越来越多的物品。所以有足够的桶来正确分配对象是非常重要的，否则你的Hashmap会变得很慢。

由于您通常不知道您需要预先在Hashmap中存储多少对象，因此需要动态增大或缩小地图。您可以保留对象数目的存储数量，一旦超过一定的阈值，您可以重新创建整个结构，但是这次对于数组K而言，这个时候的数据量可能会更大或更小。通过这种方式，K中的一些桶非常满，现在将它们的元素分配到几个桶中，这样性能会更好。

替代品 您也可以使用二维数组而不是阵列数组，也可以将数组P换成链接列表。此外，一旦一个桶包含多于一些配置数量的项目，您可以简单地选择重新创建（即重新缩放）散列映射，而不是保留存储对象的总数。

您所要求的变体在Hash table Wikipedia entry中被描述为'阵列哈希表'。

代码有关代码示例，请参阅here。

希望这会有所帮助。

来源

2010-11-11 17:41:01

-1

你能更精确吗？一个数组是否包含键，另一个是值？

如果是这样，这里是Java的一个例子（但这里也有这种语言的一些具体情况）：

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

当然，你必须实例化map对象（如果你使用的是Java，我建议使用HashMap<Object, Object>而不是过时的HashTable），并测试您的阵列以避免null对象并检查它们是否具有相同的大小。

来源

2010-11-06 16:42:42 romaintaz

他没有说他在使用Java，但仍然是很好的建议。 – 2010-11-06 16:45:45

是的，的确，我没有看到。我已经编辑了我的答案，但主要部分并不特定于Java。 – romaintaz 2010-11-06 16:46:52

我很确定他想用两个数组创建自己的哈希表实现。 – sepp2k 2010-11-06 18:02:08

-1

您的意思是？

使用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

来源

2010-11-06 16:52:26

谢谢，但你究竟在哪里定义哈希函数？据我所知，你需要一个哈希函数，两个数组和一个摆脱碰撞的方法。 – locoboy 2010-11-06 22:10:29

样品说明：

在下面的源，基本上做了两两件事：

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位，然后加入炭（换算后为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
How does a hash table work?

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

来源

2016-07-16 12:15:19

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

回答

1.地图表示

2。散列函数

相关问题