Ruby ruby hash table 是记录插入顺序的,实现方法简单粗暴

linjunhalida · 2013年05月28日 · 最后由 linjunhalida 回复于 2013年05月28日 · 5590 次阅读

刚才看 ruby hash table 实现,翻到:

http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/

原先知道 ruby hash table 是保留插入顺序的,一直不知道是如何实现的。 上面给出答案:hash table 里面每个元素保存的方式是采用链表,然后这个链表结构st_table_entry里面有 2 个指针st_table_entry *fore, *back, 然后就是说 hash table 同时也是一个双向链表!

真的是非常有意思。

额。。原来是顺序的 真的蛮怀疑性能的。。。

#1 楼 @iBachue 增加双向列表主要是应对 Ordered Hash, 在 查找 的性能上并没有降低 (查找并不使用双向列表),而且 遍历 的性能还提高了。 只是 插入 和 删除 略受一点影响。

链表只是用来存储数据。当你用 key 来查找 value 的时候,肯定不是遍历链表来查找的,所以这个应该不影响性能,但确实带来了记录顺序的好处。

#2 楼 @skandhas #3 楼 @yanhao 好吧 算是同时维护了一根双向链表和一个索引咯。 话说一般凡是用 Hash 都是默认 key 无序的,有序 key 用得不多啊。

#1 楼 @iBachue 有和 1.8 比较过插入删除性能, 基本没什么区别

这个实现和 java 的 hashtable 完全一样啊

@iBachue 有序 hash 的好处很多。因为应用上面很多时候是期待 hash 遍历是按照顺序的。一个例子就是我做 test 的时候需要检查 hash table 的结果。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号