Hashes are typically implemented with a number of buckets pre-allocated,
usually in the form of an array. Hash values are calculated on the keys to
be inserted, and a bucket is chosen mod bucket_count. So it's pretty much
anyone's guess where a given hash will put a key. The apparent reordering is
actually not quite correct; what was seen is apparent *ordering*. The fact
that the insertion order was retained was only a lucky coincidence. Try
inserting a, b, and c in a different order.
To make matters worse, a hash will frequently have collisions when choosing
a bucket, so you generally also have a linked list in each bucket to hold
values that collide. Then if there are n elements with the same hash mod
bucket_count, you'll have to iterate over them looking for the correct
element (in Ruby's case, I believe the one that matches eq?). To avoid too
many collisions impacting hash performance, it may be necessary to expand
the number of buckets and rehash everything...at a cost of n, where n is the
number of elements inserted up to that point. After rehashing, all apparent
ordering will likely have disappeared.
The general associative structure is called a map, not a hash, because it
maps keys to values. A hash is one way to implement a map that gives
insertion and lookup performance guarantees; specifically, values can be
inserted, removed, and queries in constant time (as opposed to some
polynomial of n elements). The trade-off is that order is not guaranteed,
since order ends up being determined by the hash values.
You can implement a map that preserves or maintains order in multiple ways;
you can use a tree--or specifically a "red/black tree", which is memory
optimal but requires at most log(n) time a given value, and something like
log(n) to rebalance the tree periodically. The characteristic used to
maintain order (and balance) in the tree is not important. You can also
maintain a hash and an ordered list internally, using the list for iteration
and the hash for all other operations. Hash lookups remain constant time but
modifications take some polynomial of n (because you now have to update the
ordered list).
It's all about tradeoffs. Array is a minimum implementation of an ordered
list...in that it maintains the order you provide for it. It is not a sorted
list, which maintains an order based on some external characteristic (like a
sort algorithm or <=>). Hash is a minimal implementation of an unordered
map, which provides fast access to named keys but does not preserve order or
perform any sorting.
Those calling for an ordered hash are really looking for an ordered map, and
it seems in many cases they want a sorted map (or an ordered or sorted
"associative array", as others have mentioned...tomato/tomato). Hash should
not be modified to preserve order, since it would add overhead to many, many
cases where order is unnecessary additional overhead. I wouldn't be opposed
to adding a general-purpose Tree, to allow those who want to implement an
ordered map a fast, native data structure to do so; but I would oppose
adding uncommon variants of hash to the standard libraries, specifically the
OHash (and IHash?!?) that have come up a few times.
···
--
Contribute to RubySpec! @ www.headius.com/rubyspec
Charles Oliver Nutter @ headius.blogspot.com
Ruby User @ ruby.mn
JRuby Developer @ www.jruby.org
Application Architect @ www.ventera.com
