ruby - "Hashes enumerate their values in the order that the corresponding keys were inserted."

Question

来自 http://ruby-doc.org/core-2.4.0/Hash.html#method-i-each 的 ruby​​ 文档:

Hashes enumerate their values in the order that the corresponding keys were inserted.

通常，我希望以随机顺序枚举哈希值(以任意语言)。

ruby 如何跟踪插入顺序？除了哈希桶之外，它是否在键之间保留一个链表？我想这会非常简单，但我真的很惊讶(以一种好的方式)他们首先做到了。

Answer 1

是的，它有一个链表。这可以在不损害典型哈希表的典型 O(1) 分摊最坏情况步骤复杂性保证的情况下完成，因为使链表昂贵的所有操作(例如删除元素)都与需要遍历列表有关找到一个元素，但在这种特殊情况下，“查找”部分可以通过使用哈希表查找来缩短。

如果您对 Ruby 实现的内部结构感兴趣，我建议您阅读 Rubinius 源代码；它比 YARV 更简洁易读，而且它是用 Ruby 编写的，您可能已经熟记这种语言。 Rubinius 的 Hash 类在 core/hash.rb 中实现.请注意，当前版本的 Rubinius 使用 Hash Array Mapped Trie (HAMT) ，这与YARV使用的简单传统哈希表明显不同，但与附加链表的使用无关。如果你真的想要，你可以看看 older version仍然有传统的哈希表。