「哈希按照相應的鍵被插入的順序枚舉它們的值。」

Question

從Ruby文檔在http://ruby-doc.org/core-2.4.0/Hash.html#method-i-each：

散列枚舉在相應的鍵被插入的順序的值。

定期地，我希望以隨機順序枚舉散列（以任何任意語言）。

ruby​​如何設法跟蹤插入順序？除了哈希桶之外，它還在鍵之間保存鏈接列表嗎？我想這很簡單，但我真的很驚訝（以一種好的方式），他們首先做到了。

Answer 1

This forum提供您正確尋找的答案，並且由Matz自己回答。

有人可以解釋爲什麼添加此功能嗎？

用於某些情況下，尤其是關鍵字參數。

是不是會減慢哈希上的操作？

編號散列參考操作不會觸及訂單信息，只有 用於迭代。內存消耗增加了一點。

Answer 2

是的，它保留一個鏈表。這可以在不損害典型散列表的典型O（1）分期最壞情況步驟複雜性保證的情況下完成，因爲使鏈表成本昂貴的所有操作（例如，刪除元素）與需要按順序遍歷列表有關到找到一個元素，但在這種特殊情況下，通過使用散列表查找可以使「查找」部分短路。

如果您對Ruby實現的內部感興趣，我推薦閱讀Rubinius源代碼;它比YARV更加清潔和易於閱讀，而且它是用Ruby編寫的，這是一種你認爲可以預知的語言。 Rubinius的Hash課程是在core/hash.rb中實施的。請注意，當前版本的Rubinius使用Hash Array Mapped Trie (HAMT)，這與YARV使用的簡單傳統哈希表有很大不同，但與使用附加鏈接列表無關。如果你真的想，你可以看看仍然有傳統散列表的older version。