Ruby 名称Hash有点误导。对于大多数开发人员来说，它们实际上是maps，这意味着你给他们一个值，他们给你另一个相关的值。它们是散列映射的事实实际上只是使它们快速的一个实现细节，实际上它与散列集的原理相同，给定一个值，只告诉您该值是否在集合中。
为了稍微简化一下，想象一下：
您有一个包含 10 个元素的数组。你被告知要记住 35 =“一些数据”。然后对索引 (35)进行哈希处理，我将其简化为将其除以数组长度的模数，因此结果为35 % 10 = 5.
然后我们将数据 35 = "some data" 存储在该索引处，例如作为元组 [35, "some data"]。
然后我们得到更多数据，25 =“更多数据”和 78 =“很酷的东西”。所以再次，我们散列键并得到5和8。存储第二个很容易，我们只需要将 [78, "cool stuff"] 存储在数组的第 8 位。
但是存储 [25, "more data"] 是一个问题，因为在 position 已经有一个桶5。正如您已经指出的，这是通过存储链表来解决的。所以我们回到开头，而是存储 [35, "some data", nil] 作为我们的第一个值。
要插入，25我们只需更改它，使第一个元素指向第二个元素，然后得到array[5] = [35, "some data", <pointer>] -> [25, "more data", nil]
过了一会儿，用户想知道与“25”相关联的值是什么。
由于我们实现了一个哈希映射，我们可以对值进行哈希处理，25 % 10 = 5并且知道我们的对存储在位置5。然后我们只需要迭代一个包含 2 个元素的链表来寻找 value [25]，当我们找到它时，只需取第二个值并将其返回给用户。
当然，上面是一个过于简单的例子，但它显示了哈希映射如何操作的基本思想。
在现实世界中，散列算法当然会比模除法更复杂，但思想是一样的。键的散列始终转换为数组中的索引。一个好的散列算法应该是 1. 快速和 2. 随机，以避免有很多空桶和一些有很多元素的桶。
此外，我们的数组不会有固定的 10 长度，但要聪明一点，并尝试通过不要太大来节省内存，但同时对内存要足够大，以避免不必要的收缩/增长所有时间并保持水桶合理短。
在最好的情况下，您可以拥有几千个元素的映射，并且要访问一个您只需散列它，这需要与散列大小无关的相同时间，而不必迭代所有这些数千个元素并进行比较每一个到你正在寻找的一个。
关于你的第三个问题，答案是肯定的。
至于第二个，键存储在桶中，但可能只是它们的散列值。
我不确定 ruby 如何在内部存储桶，但通常它们可以通过多种方式实现，如数组、结构等。
| 归档时间： |
|
| 查看次数： |
726 次 |
| 最近记录： |