Iterating Over a Hash in Insertion Order

Problem

Iterations over a hash happen in a seemingly random order. Sorting the keys or values only works if the keys or values are all mutually comparable. You'd like to iterate over a hash in the order in which the elements were added to the hash.

Solution

Use the orderedhash library (see below for how to get it). Its OrderedHash class acts like a hash, but it keeps the elements of the hash in insertion order.

	require ' 
orderedhash'
	h = 
OrderedHash.new
	h[1] = 1
	h["second"] = 2
	h[:third] = 3

	h.keys # => [1, "second", :third]
	h.values # => [1, 2, 3]
	h.each { |k,v| puts "The #{k} counting number is #{v}" }
	# The 1 counting number is 1
	# The second counting number is 2
	# The third counting number is 3

Discussion

OrderedHash is a subclass of Hash that also keeps an array of the keys in insertion order. When you add a key-value pair to the hash, OrderedHash modifies both the underlying hash and the array. When you ask for a specific hash element, you're using the hash. When you ask for the keys or the values, the data comes from the array, and you get it in insertion order.

Since OrderedHash is a real hash, it supports all the normal hash operations. But any operation that modifies an OrderedHash may also modify the internal array, so it's slower than just using a hash. OrderedHash#delete is especially slow, since it must perform a linear search of the internal array to find the key being deleted. Hash#delete runs in constant time, but OrderedHash#delete takes time proportionate to the size of the hash.