indexing - 什么决定了元素/桶的大小？- 哈希索引

Question

我搜索过的承诺，人们也问过类似的问题，但答案似乎总是技术上不可能，但没有说明原因。我也进行了谷歌搜索并获得了相同的信息。

我是从独立于语言的方面提出这个问题的。我知道哈希索引的工作原理是创建一个数组，然后将一个键放入一个哈希函数，然后映射到数组中的一个索引。文献总是说每个键只能有一个值，我假设这取决于数据类型/cpu 意味着内存中每个元素/索引 4,8 个字节。我知道，如果您使用指向另一个数组或列表的指针，每个键可以有多个值，但技术上阻止您声明例如键 = 汽车值 = 奥迪、蓝色、房地产、19 英寸车轮并在该元素中放置更多字节?

是否因为对索引的调用需要在一次内存读取中进行，并且存储桶的最大大小与数据总线宽度相同？还是因为这就是编译器的设计方式，理论上他们可以让编译器使用那些声明每个键需要多个值的代码？或者最后它可能与散列函数有关，因为它事先知道数组的大小，并且为了将所有键/值对放入连续内存中，它需要每个元素只存储一个值？

抱歉，如果我遗漏了一些非常明显的东西，但我就是不明白为什么它在技术上是不可能的。谢谢你听我继续大声笑

标签： indexinghashassociative-array

Answer 1

欢迎来到 SO，罗布！

什么都不能有多个值。例如，数学中的一个变量不能有多个值。X 不能既是 1 又是 0，除非我们在谈论量子计算。同样，每个键不能有多个值。

另一种看待它的方法是使用函数依赖，它指出如果键 X 具有值 Y 和 Z，那么您可以拥有键 X 两次，一次指向 Y，一次指向 Z。这意味着您将需要重复键，这是我们在哈希映射中无法做到的。

我希望这有帮助。