Re: [tlug] Are ordered hashes useful?

[Marty Pauley <marty.pauley@example.com>]

On Tue, Feb 15, 2011 at 11:59 AM, Raymond Wan <rwan.kyoto@example.com> wrote:
>
> Yes, I don't agree that dictionary order and ordered list
> are the same.  Ordered list access could be provided by a
> tree, but to enable dictionary access, you either need to
> augment the tree with a hash table or build two trees in
> parallel.

Don't say that too loudly.  All the databases in the world may stop working!!!

Maybe by "ordered list" you mean the insertion order, which is where
this thread started.  I'm talking about sorted key order, or
"dictionary order" as you mentioned.

But my main point is that trees do provide dictionary access.  That's
what they're for.

In pseudocode:

  t = new Tree
  t.insert("banana" => "yellow")
  t.insert("carrot" => "orange")
  t.insert("apple" => "red")
  t.insert("durian" => "smelly")
  t.keys == {"apple","banana","carrot","durian"} # ordered access
  t.get("carrot") == "orange" # fast lookup

Most large dictionaries use trees, not hashes.  The whole point of a
tree is that it provides fast lookup O(log n) and ordered access.
Hashes don't cope well with a large amount of data (unless it's known
in advance).

-- 
Marty