问哈希(在Ruby这样的语言中)是如何“在幕后”工作的？

EN

Ruby Language Specification没有为Hash类规定任何特定的实现策略。只要遵守合同，每个实现都可以随心所欲地实现它。

例如，这里是Rubinius的实现，它是用Ruby编写的，很容易理解：kernel/common/hash.rb这是一个相当传统的哈希表。(关于这个实现，另一个需要注意的很酷的事情是，它实际上恰好和YARV一样快，这证明Ruby代码可以和手工优化的C一样高效。)

Rubinius还可以使用Hash Array Mapped Trie：kernel/common/hash_hamt.rb实现Hash类。注意:这个实现使用了三个用C++编写的VM原语。

您可以使用配置选项在这两种实现之间切换。因此，不仅不同的Ruby实现之间的Hash实现是不同的，甚至在完全相同的Ruby实现的完全相同的版本上运行完全相同的程序的两次运行之间也可能是不同的！

在IronRuby中，Ruby的Hash类只是简单地委托给一个.NET System.Collections.Generic.Dictionary<object, object>：Ruby/Builtins/Hash.cs在以前的版本中，它甚至没有委托，它只是一个子类：Ruby/Builtins/Hash.cs

如果你是这方面的铁杆分子，你可以直接看看它的实现。这就是散列最终使用的内容：https://github.com/ruby/ruby/blob/c8b3f1b470e343e7408ab5883f046b1056d94ccc/st.c

散列本身在这里：https://github.com/ruby/ruby/blob/trunk/hash.c

大多数时候，diego在评论中提供的文章就足够了

在ruby 2.4中，哈希表被移动到开放寻址模型，所以我将只描述哈希表结构是如何工作的，而不是描述它在2.4及更高版本中是如何实现的。

让我们想象一下，我们将所有条目存储在一个数组中。当我们想要找到一些东西时，我们必须遍历所有的元素来匹配其中的一个。如果我们有很多元素，这可能需要很长时间，使用哈希表，我们可以通过计算该键的哈希函数，直接转到具有所需值的单元格。

哈希表以类似于数组的数据结构存储存储(箱)组中的所有值。

How does hash table work

当我们添加一个新的键值对时，我们需要计算这个键值对将被插入到哪个“存储”中，我们使用.hash方法(散列函数)来做这件事。散列函数的结果值是一个伪随机数，因为它总是为相同的值产生相同的数字。

粗略地说，hash返回与存储当前对象的内存位置的链接等效的内容。但是，对于字符串，计算是相对于值的。

收到伪随机数后，我们必须计算将存储键值对的“存储”的数量。

'a'.hash % 16 =>9 a - key 16 - amount of storage 9 - the storage number

因此，在Ruby中，插入的工作方式如下：

How insertion works

1. 它使用内部散列函数获取密钥的散列。获取散列值，借助模运算(2782%16)，我们将获得将键值对:d.hash % 16
2. Add键值保存到适当bin

的链表中的存储号。

搜索的工作方式如下：

搜索的工作方式与此完全相同：

确定“散列”function;

• Find "storage";

• Then遍历列表并检索散列元素。

在ruby中，每个bin的平均元素数量是5。随着记录数量的增加，每个存储库中的元素密度将会增加(实际上，哈希表的大小只有16个存储空间)。

如果元素的密度很大，例如一个“存储”中的10_000元素，我们将不得不遍历这个链表中的所有元素来查找相应的记录。我们将回到O(n)时间，这是非常糟糕的。

为了避免这种情况，应用了表重新散列。这意味着哈希表的大小将会增加(直到下一个数字- 16，32，64,128，...)并且对于所有当前元素，将重新计算“存储”中的位置。

当所有元素的数量大于最大密度乘以当前表大小时，就会发生“重新散列”。

81 > 5 * 16 - rehash will be called when we add 81 elements to the table.

num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins

当条目的数量达到当前哈希表的最大可能值时，该哈希表中的“存储”的数量增加(它从16、32、64、128中获取下一个大小编号)，并且它重新计算并校正该哈希表中所有条目的位置。

查看这篇文章以获得更深入的解释：Do You Know How Hash Table Works? (Ruby Examples)