MagLev / maglev

GemStone Maglev Ruby Repository
http://maglev.github.io
517 stars 41 forks source link

Hash should preserve insertion order #163

Open matthias-springer opened 12 years ago

matthias-springer commented 12 years ago

(see http://slideshow.rubyforge.org/ruby19.html#21)

Ruby 1.9 irb(main):001:0> {:a=>"a", :c=>"c", :b=>"b"} => {:a=>"a", :c=>"c", :b=>"b"}

Ruby 1.8 irb(main):001:0> {:a=>"a", :c=>"c", :b=>"b"} => {:a=>"a", :b=>"b", :c=>"c"}

timfel commented 12 years ago

I imagine this will be difficult, as I don't think there is such a Dictionary on the Smalltalk side. You may have to write your own. There's good implementations how such a Hash should in work in the literature, and an efficient implementation is in Rubinius in C++ and I can show you one in Python (it's in a private repo I have access to)

AllenOtis commented 12 years ago

Tim, Matthias,

One approach would be to start with the existing implementation in src/kernel/bootstrap/Hash.rb and instead of storing key/value pairs, store key/association pairs.

The associations would be a subclass of Association with instVars key,value,prev,next . The prev,next instVars would give you a linked list to maintain order.

The existing implementation is designed to use instances of Hash for collision buckets, thus trying to avoid a Hash becoming a "large"(i.e. > 2034 instVars) object on disk.

Allen