Re: Hash order bug?

I think this is just a common mistake among newbie-ish programmers.
Which isn't to say anything about Javier specifically, I don't know him,
but in general, a review of one's Data Structures course may be in order
when this happens. But I think it happens to just about every
programmer at some point. I remember the first time I tried to do some
ASP scripting for some web pages and I decided to use the Dictionary
object. At one point I wanted to loop through the Dictionary and
display a listing of its contents. I got all pissed off when I realized
that the loop didn't return the items in alphabetical order. Only later
did I realize that the underlying data structure is a hash, and that the
whole point of a hash is to maximize speed of access by sacrificing
things like, being able to iterate it in any particular order. Of
course, the word "Dictionary" does, for most of us, bring to mind
something that's in alphabetical order, so maybe it was Microsoft's
fault for givig it a dumb name. At any rate, it would be a bad idea to
allow what is essentially a mistake made by programmers to force an
abnormal, slower implementation onto a data structure whose definition
is largely agreed upon in computing. In other words, I'm with the "we
don't need an 'ordered hash'" crowd. I think that, besides slowing it
down, it goes against the very definition of what a hash is.

If you need to iterate through a hash in order by key, it's a simple
matter to grab an array of the keys first, sort it, then iterate from
that. I'm probably going to embarrass myself with my Ruby nuby-ness
here, but off the top of my head:

my_hash.keys.sort.each{|key| doSomethingWith(my_hash[key])}

If you want, and if you really must do away with the overhead of having
to retrieve the key array and sort it first, you could modify the Hash
class with in your own program (Ruby lets you do stuff like that) and
have it keep a sorted array of keys, by adding each new key to it in a
sorted position, after every time an item is added to the hash, and
splicing the key out of the array whenever an item is removed. Then you
could override the each method, and the inspect method if necessary.

--ch--


.

Relevant Pages

  • Duck Typed Concepts for Ruby (was Re: A use case for an ordered hash)
    ... An Sequencable mixin can be defined that implements all sorts of operations such as append, concat, splice, sort, etc. ... extending an instance of Array with Sorted if the array is known to be sorted. ... Now returning to the thread at hand we can see that the difference between the associative array and hash hierarchies is that the hash hierarchy depends upon Hashable keys. ...
    (comp.lang.ruby)
  • Re: Suggestions for double-hashing scheme
    ... >> The items that are being moved are the items in the hash table itself, ... >> which are of fixed size (they are in an array, ... > typedef struct { ... One "uchar" aka 'unsigned char' is plenty to hold a probe ...
    (comp.programming)
  • [SUMMARY] Index and Query (#54)
    ... This was a fun quiz for me because I really don't know anything about indexing ... We see in initializethat the index is just a Hash. ... an Array of symbolic document names where the word can be found ). ...
    (comp.lang.ruby)
  • Re: Not enough parallelism in programming
    ... Tools can provide feedback to programmers on deductions that can be made from their individual expressions, to tell them some things about what they are really saying, especially when their overall expression appears to be unproductive. ... It should analyse the complexity in terms of basic ... Looking up an array element in a not-required-to-be-contiguous array ... analyses are likely to be about as successful as any other analyses ...
    (comp.arch)
  • Re: Static vs. Dynamic typing (big advantage or not)---WAS: c.programming: OOP and memory management
    ... >>Sure, the vector class is useful, and I use it most of the time. ... > to the language standard. ... Because a variable-size array type is a wheel that C++ programmers have ...
    (comp.object)