Re: [tlug] Are ordered hashes useful?

[Jun-Dai Bates-Kobashigawa <jd.lists@example.com>]

The most common use case for a bundle of key/value pairs is simply as a dictionary, and thus hash maps / dictionaries / associative arrays are the most common data structure involving key/value pairs.

There are cases where you want an ordered list of key/value pairs.  For example, an ordered list of airport code -> airport name mappings that you want to use in a dropdown.  I've always found this a bit awkward in most languages, but given that it's not so common, there's usually some way to do it.  If you think about it, it's really just a special case of an ordered list of objects, where the object type in question only has two attributes (e.g., airport_code, airport_name), one of which is the basis for the ordering.  Depending on the circumstance, I usually end up with (i) an ordered list of custom objects, (ii) an ordered list of some kind of KeyValuePair objects, or (iii) an ordered list of two-item arrays.

Then there are cases where you want a data structure that provides both dictionary access and ordered list access.  I definitely run into this from time to time (just ran into it this week, actually).  If there were such a construct in the language I was working in, I'm guessing I would use it.  Instead, I usually roll my own each time.  Usually it just involves simultaneously maintaining a dictionary and an ordered list of its keys.  This provides the same quick read-access from either angle, and in most cases where I've encountered the need for this structure it was for something read-only, so the time taken to add a value to both the list and the hashmap isn't important.  The other concerns it creates are memory usage and time taken to assemble the structure (if it's not being cached), but those haven't been problems for me yet…

Neither the second nor the third data structure should really be considered a "hash".  But they can be useful.

It seems the Ruby solution makes similar tradeoffs to what I normally end up building (they have more complex dictionary entries, instead of maintaining two access structures), but with a smaller footprint:

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

I agree it seems wrong to rely on the ordering of a "hash".  I don't know that it's likely to cause bugs in Ruby code, but it does seem like a naming problem that might cause confusion for someone brought up using Ruby that moves on to any other language.

 -Jdbk

On Tue, Feb 8, 2011 at 5:38 AM, Stephen J. Turnbull <stephen@example.com> wrote:

Changing the Subject, because I'm changing the subject.

Josh Glover writes:

 > Ruby has a hash that keeps the keys FIFO ordered, if that makes sense.
 > The first key you put in is the first key that
 > GoogleOnlyKnowsTheNameOfTheHashClass#keys will return.

This has recently been proposed for Python, but the consensus so far
is that it's not very useful by itself.  It doesn't quite do the right
thing when used as a dictionary for keeping keyword arguments AIUI,
which is the most common proposed use for a "bare" FIFO hash at
python-dev.  (The people who want this are probably trying to solve
Dave's problem in an elegant way, in fact, now that you remind me of
the idea of ordered hash.)

Do you know of any use cases for it?

--
To unsubscribe from this mailing list,
please see the instructions at http://lists.tlug.jp/list.html

The TLUG mailing list is hosted by the award-winning Internet provider
ASAHI Net.
Visit ASAHI Net's English-language Web page: http://asahi-net.jp/en/