Why Ruby's array of 1000 hashes' key and v

Question

Say if there is an array of 1000 hashes, with pairs like {:id => 1, :name => 'something', :created_at => '2010-08-18'}

when I use a loop to print out those 1000 records, supposedly, the hash's key / value pair order is not guaranteed, but the print out of the table, it always appear in the same order. Why is it and can it be counted on? Otherwise, what good method is good for sorting the key / value pairs?

(I was thinking of mapping :id to 10, and :name to 20, and :create_at to 30, and then sort the keys by these mapped values, so that :id is before :name, and is before :created_at)

(the hash is printed out by a_hash.each_pair do |k, v| ...)

Answer 1

The layout of the hash is deterministic. So for a particular version of ruby, if you always add/remove the keys of a hash in the same order, the layout of the hash will be the same. This means iterating over the hashes in your array will have the keys all in the same order.

Answer 2

Ruby hashmaps (and hashmaps in general) have no implied ordering of keys. They are however implemented in a way that makes retrieving a value given a key an efficient operation (amortized O(1)) time.

So in the underlying implementation, the keys are always structured in the same way, which makes them appear to have an order.

Answer 3

Ruby doesn't guarantee ordering of Hash keys, though Ruby 1.9 does preserve insertion order.

If you want to process a Hash's keys in a specific but arbitrary order, the best way is to create an Array specifying the order. So you might have an array like [:id, :name, :create_at]. If you want to process a Hash in, say, alphabetical order, you can just use sort and it will give you an array of the key-value pairs in order.

Answer 4

Why is it and can it be counted on?

Any hash is going to have a "natural sort".

A "natural sort" is either maintained either as each element is inserted or is performed before the first search.

If there is no natural sort returning a value matching a particular key would require an exhaustive search.

An exhaustive search, of course, would take n comparisons where n is the number of elements in the hash.(e.g 65536 elements searched in 65536 comparisons.)

On the other hand, If a hash is sorted alphabetically by KEY, then a binary search can find a match in LOG2(n) comparisons. (e.g 65536 elements searched in 16 comparisons.)

There are other sorting methods, but they all require some initial sort. This sort could be a system with a hidden index that leaves the key/value pair elements unsorted.

e.g. In the following partial implementation, the key/values pairs are stored as objects in an underlying array.

myArray[0] = {"b", "Skies"}
myArray[1] = {"c", "dog"}
myArray[2] = {"a", "Jax"}
myArray[3] = {"d", "gone"}
myArray[4] = {"r", "run"}
myArray[5] = {"q", "quit"}

a second array, to which the Ruby developer has no access, holds the sort.

sortArray[0] = 2
sortArray[1] = 0
sortArray[2] = 1
sortArray[3] = 3
sortArray[4] = 4 
sortArray[5] = 5 

Thus, internally to the hash object

for(i=0 to 5) 
    print myArray[sortArray[i]]

would print the sorted array.

Ruby's spec apparently does not specify which method to use, sorting by key, a hidden sort, or some other method, so, no, you can not count on the natural sort.

Answer 5

The documentation at ruby-doc.org for ruby 1.9 (not sure if it's 1.9.0 or 1.9.1) incorrectly says

The order in which you traverse a hash by either key or value may seem arbitrary, and will generally not be in the insertion order.

But 1.9.1 news says

Hash preserves order. It enumerates its elements in the order in which the keys are inserted.

I had a look at the trunk of ruby (what's being developed), and it says

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

The change to the documentation was in a September 25, 2009 commit that was fixing incorrect documentation.

I'm not 100% sure that an ordered enumeration is part of the specification of ruby 1.9.1. Rubyspec would be one way of checking. But if the main implementation gives a contract, then you'd expect any other implementation to honor that contract unless it explicitly says otherwise.