ruby - 散列(在像 Ruby 这样的语言中)如何工作 "under the hood"？

Question

我在这里和那里阅读过有关 HashMap /表的信息，并且可以理解哈希表本质上是一个有限大小数组的概念。该函数可以使用取模运算符来确定数组中的哪个索引对应于特定键。如果发生冲突，则可以实现链表来存储所有冲突的值。这是我非常新手的理解，我希望有人可以在 Ruby 哈希的上下文中详细说明/更正它。在 Ruby 中，您真正需要做的就是

hash = {}    
hash[key] = value

这会创建一个具有相应值的键。假设您只是将一堆符号存储为键，将数字存储为值:

hash[:a] = 1
hash[:b] = 2
...

在数组和链表中存储值方面到底发生了什么？什么是碰撞的例子？

Answer 1

Ruby 语言规范没有为 Hash 规定任何特定的实现策略类(class)。只要他们遵守契约(Contract)，每个实现都可以按照他们想要的方式实现。

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

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

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

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