Hash order bug?

ruby-talk
1

I have this piece of simple code:

···

----------------------------------------------
def foo
    return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv => false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

----------------------------------------------
ruby pro.rb
{:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
----------------------------------------------

Now, i delete the foo function from the code (the foo function don't do nothing at all), and i get a well ordered hash:

----------------------------------------------
ruby pro.rb
{:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
----------------------------------------------

What's happening? all my code is behaving wrong because of that.

2

Hi --

···

On Tue, 25 Jul 2006, Javier Valencia wrote:

I have this piece of simple code:

----------------------------------------------
def foo
  return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv => false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

----------------------------------------------
ruby pro.rb
{:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
----------------------------------------------

Now, i delete the foo function from the code (the foo function don't do nothing at all), and i get a well ordered hash:

----------------------------------------------
ruby pro.rb
{:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
----------------------------------------------

What's happening? all my code is behaving wrong because of that.

Hashes are unordered. If you need an ordered collection, you'll need
to use an array.

David

--
http://www.rubypowerandlight.com => Ruby/Rails training & consultancy
Ruby for Rails => RUBY FOR RAILS (reviewed on
                                     Slashdot, 7/12/2006!)
http://dablog.rubypal.com => D[avid ]A[. ]B[lack's][ Web]log
dblack@wobblini.net => me

3

by definition a hash table is not ordered.

[...]

···

On 7/25/06, Javier Valencia <jvalencia@log01.org> wrote:

I have this piece of simple code:

----------------------------------------------
def foo
    return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv =>
false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

--
Nicolas Desprès

4

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--

5

dblack@wobblini.net wrote:

Hi --

I have this piece of simple code:

----------------------------------------------
def foo
  return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv => false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

----------------------------------------------
ruby pro.rb
{:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
----------------------------------------------

Now, i delete the foo function from the code (the foo function don't do nothing at all), and i get a well ordered hash:

----------------------------------------------
ruby pro.rb
{:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
----------------------------------------------

What's happening? all my code is behaving wrong because of that.

Hashes are unordered. If you need an ordered collection, you'll need
to use an array.

David

Oh my god, i didn't know it, sorry. Is that a missing feature?

···

On Tue, 25 Jul 2006, Javier Valencia wrote:

6

Nicolas Desprès wrote:

···

On 7/25/06, Javier Valencia <jvalencia@log01.org> wrote:

I have this piece of simple code:

----------------------------------------------
def foo
    return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv =>
false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

by definition a hash table is not ordered.

[...]

Well, i don't mind ordering alphabetically, just to maintain their construction order, like an array.
Anyway, thanks all for quick responses, hope to see that implemented in core-ruby soon :slight_smile:

Thanks

7

Indeed. Here's one reference:

I'm not sure I like the idea (discussed elsewhere in this thread) that the
Hash class may be changed in the future to be ordered.

···

On 2006-07-25, Nicolas Desprès <nicolas.despres@gmail.com> wrote:

On 7/25/06, Javier Valencia <jvalencia@log01.org> wrote:

I have this piece of simple code:

----------------------------------------------
def foo
    return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv =>
false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

by definition a hash table is not ordered.

--

8

Mind you, you'd just be amortizing that overhead into each hash
insertion/removal, and paying high interest besides -- to say nothing of
having to write more code :wink:

--ch--

···

On Sun, 2006-07-30 at 00:02 +0900, Charles Hoffman wrote:

If you want, and if you really must do away with the overhead of
having
to retrieve the key array and sort it first,

9

Charles Hoffman wrote:

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.

True.

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])}

h = { 'zebra', 2, 'horse', 0, 'sheep', 1 }
    ==>{"horse"=>0, "sheep"=>1, "zebra"=>2}
h.sort.each{|x| p x}
["horse", 0]
["sheep", 1]
["zebra", 2]
    ==>[["horse", 0], ["sheep", 1], ["zebra", 2]]

10

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.

Oddly enough, I never made that assumption -- but I think that's because
I first learned about hashes/dictionaries/associative arrays by reading
something that explained up-front the fact that they're not ordered and,
more to the point, why they aren't ordered, in any particular manner
that makes immediate sense to the programmer.

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.

If so, you might want to have some words with Guido van Rossum about the
use of the term "dictionary" in Python. I'd probably be happier with
"lexicon" than "dictionary", but I like "hash" most of all.
"Associative array" is probably best, aside from the fact that it's WAY
too long to be comfortable for general use.

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.

Agreed . . . but I wouldn't be opposed to a method that produces
alphabetized and/or asciibetized output, by key, from a hash.

···

On Sun, Jul 30, 2006 at 12:02:50AM +0900, Charles Hoffman wrote:

--
CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
"A script is what you give the actors. A program
is what you give the audience." - Larry Wall

11

Why doesn't someone write a red-black tree for Ruby? I mean, it would
be trivial to do with a C++ extension and std::map<>...

12

Hashes are unordered. If you need an ordered collection, you'll need
to use an array.

Hashes are unordered. that is how sadly for me,really!

···

--
Posted via http://www.ruby-forum.com/\.

13

No, its just not a feature. You can check
http://rubyforge.org/projects/arrayfields if you want a ordered hash.

j`ey
http://www.eachmapinject.com

···

On 7/25/06, Javier Valencia <jvalencia@log01.org> wrote:

dblack@wobblini.net wrote:

> Hi --
>
> On Tue, 25 Jul 2006, Javier Valencia wrote:
>
>> I have this piece of simple code:
>>
>> ----------------------------------------------
>> def foo
>> return 5
>> end
>>
>> a = {:gr => false, :und => false, :det => true, :sta => false, :inv
>> => false}
>> puts a.inspect
>> ----------------------------------------------
>>
>> when I execute it i get a totally unordered hash:
>>
>> ----------------------------------------------
>> ruby pro.rb
>> {:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
>> ----------------------------------------------
>>
>> Now, i delete the foo function from the code (the foo function don't
>> do nothing at all), and i get a well ordered hash:
>>
>> ----------------------------------------------
>> ruby pro.rb
>> {:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
>> ----------------------------------------------
>>
>> What's happening? all my code is behaving wrong because of that.
>
> Hashes are unordered. If you need an ordered collection, you'll need
> to use an array.
>
> David
>

Oh my god, i didn't know it, sorry. Is that a missing feature?

14

Hi --

Hi --

I have this piece of simple code:

----------------------------------------------
def foo
  return 5
end

a = {:gr => false, :und => false, :det => true, :sta => false, :inv => false}
puts a.inspect
----------------------------------------------

when I execute it i get a totally unordered hash:

----------------------------------------------
ruby pro.rb
{:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
----------------------------------------------

Now, i delete the foo function from the code (the foo function don't do nothing at all), and i get a well ordered hash:

----------------------------------------------
ruby pro.rb
{:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
----------------------------------------------

What's happening? all my code is behaving wrong because of that.

Hashes are unordered. If you need an ordered collection, you'll need
to use an array.

David

Oh my god, i didn't know it, sorry. Is that a missing feature?

Debate rages on this point :slight_smile: It's mostly a speed issue, I think.
At least my memory is that Matz's latest statement was to the effect
that he would do it if it could be done efficiently.

The question came up during a lunch here at OSCON (with me, Jim
Weirich, Pat Eyler, and a fellow named Nicolas whose last name I'm
afraid I don't remember) as to whether making hashes ordered in a
future Ruby would break any existing code. I think the answer is no,
which is kind of interesting considering what a major change it would
be. It's a case where the feature would be purely additive.

David

···

On Tue, 25 Jul 2006, Javier Valencia wrote:

dblack@wobblini.net wrote:

On Tue, 25 Jul 2006, Javier Valencia wrote:

--
http://www.rubypowerandlight.com => Ruby/Rails training & consultancy
Ruby for Rails => RUBY FOR RAILS (reviewed on
                                     Slashdot, 7/12/2006!)
http://dablog.rubypal.com => D[avid ]A[. ]B[lack's][ Web]log
dblack@wobblini.net => me

15

Javier Valencia wrote:

> Hi --
>
>
>> I have this piece of simple code:
>>
>> ----------------------------------------------
>> def foo
>> return 5
>> end
>>
>> a = {:gr => false, :und => false, :det => true, :sta => false, :inv
>> => false}
>> puts a.inspect
>> ----------------------------------------------
>>
>> when I execute it i get a totally unordered hash:
>>
>> ----------------------------------------------
>> ruby pro.rb
>> {:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
>> ----------------------------------------------
>>
>> Now, i delete the foo function from the code (the foo function don't
>> do nothing at all), and i get a well ordered hash:
>>
>> ----------------------------------------------
>> ruby pro.rb
>> {:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
>> ----------------------------------------------
>>
>>
>> What's happening? all my code is behaving wrong because of that.
>
>
> Hashes are unordered. If you need an ordered collection, you'll need
> to use an array.
>
>
> David
>

Oh my god, i didn't know it, sorry. Is that a missing feature?

No. What language has ordered hashes?

When you say
a = {:gr => false, :und => false, :det => true, :sta => false, :inv
  => false}
you are saying that you want to access the values in this fashion:
a[:und]
So the order in which they are stored is irrelevant.
If you want to access them this way
a[1]
then you set them up like this
[ false, false, true, false, false ]

If you want to get a sequence of values in a certain order:
a.values_at( :und, :det, :sta )

If you want to have your cake and eat it too, you could
use an association list:

as = [[:foo,22], [:bar,33], [:baz,44]]

=> [[:foo, 22], [:bar, 33], [:baz, 44]]

as.assoc(:bar)

=> [:bar, 33]

as.rassoc( 44 )

=> [:baz, 44]

as[0]

=> [:foo, 22]

If the list has a large number of elements, access will be slow.

···

dblack@wobblini.net wrote:
> On Tue, 25 Jul 2006, Javier Valencia wrote:

16

Javier,

I don't believe it's a missing feature. In every language I've used, Hashes
are not ordered. It has to do with how they are implemented under the
hood. If you really need an ordered Hash, you could create a class that
uses an Array to maintain the order of the keys, and store the values in a
Hash.

/Doug

···

On 7/25/06, Javier Valencia - jvalencia@log01.org <+ruby- talk+closure+a5facb16dd.jvalencia#log01.org@spamgourmet.com> wrote:

dblack@wobblini.net wrote:

> Hi --
>
> On Tue, 25 Jul 2006, Javier Valencia wrote:
>
>> I have this piece of simple code:
>>
>> ----------------------------------------------
>> def foo
>> return 5
>> end
>>
>> a = {:gr => false, :und => false, :det => true, :sta => false, :inv
>> => false}
>> puts a.inspect
>> ----------------------------------------------
>>
>> when I execute it i get a totally unordered hash:
>>
>> ----------------------------------------------
>> ruby pro.rb
>> {:inv=>false, :gr=>false, :und=>false, :det=>true, :sta=>false}
>> ----------------------------------------------
>>
>> Now, i delete the foo function from the code (the foo function don't
>> do nothing at all), and i get a well ordered hash:
>>
>> ----------------------------------------------
>> ruby pro.rb
>> {:gr=>false, :und=>false, :det=>true, :sta=>false, :inv=>false}
>> ----------------------------------------------
>>
>> What's happening? all my code is behaving wrong because of that.
>
> Hashes are unordered. If you need an ordered collection, you'll need
> to use an array.
>
> David
>

Oh my god, i didn't know it, sorry. Is that a missing feature?

17

Just Another Victim of the Ambient Morality wrote:

    Why doesn't someone write a red-black tree for Ruby? I mean, it would be trivial to do with a C++ extension and std::map<>...

Not sure, but I think it's been done.

Hal

18

> 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.

If so, you might want to have some words with Guido van Rossum about the
use of the term "dictionary" in Python. I'd probably be happier with
"lexicon" than "dictionary", but I like "hash" most of all.
"Associative array" is probably best, aside from the fact that it's WAY
too long to be comfortable for general use.

I like "Hash" because it reminds you opf the fact that its
implementation involves "hashing" they keys with a mathematical function
of some sort so as to make them quick to get to.

I didn't know Python calls it Dictionary too. I don't know any Python
actually.

> 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.

Agreed . . . but I wouldn't be opposed to a method that produces
alphabetized and/or asciibetized output, by key, from a hash.

I think someone posted in this thread an example showing that Hash has a
sort method. But now I'm not so sure...

/me heads off to irb to try it...

--ch--

···

On Sun, 2006-07-30 at 04:28 +0900, Chad Perrin wrote:

19

Hi, I missed some of this thread, I only just joined the list. Although it's
less than optimal, can you not just sort the keys when you need them.
Something like:

require 'enumerator'
sorted_keys = hash.enum_for(:each_key).to_a.sort

Again, there might very well be a better way to do even that, I'm new to
ruby.

Nick

···

On 5/5/07, Haoqi Haoqi <axgle@126.com> wrote:

> Hashes are unordered. If you need an ordered collection, you'll need
> to use an array.

Hashes are unordered. that is how sadly for me,really!

--
Posted via http://www.ruby-forum.com/\.

20

[snip]

What's happening? all my code is behaving wrong because of that.

Hashes are unordered. If you need an ordered collection, you'll need
to use an array.

Oh my god, i didn't know it, sorry. Is that a missing feature?

Debate rages on this point :slight_smile: It's mostly a speed issue, I think.
At least my memory is that Matz's latest statement was to the effect
that he would do it if it could be done efficiently.

The question came up during a lunch here at OSCON (with me, Jim
Weirich, Pat Eyler, and a fellow named Nicolas whose last name I'm
afraid I don't remember) as to whether making hashes ordered in a
future Ruby would break any existing code. I think the answer is no,
which is kind of interesting considering what a major change it would
be. It's a case where the feature would be purely additive.

I guess there won't be many ppl using algorithms that use the *un*sorted
aspect of a Hash. Using Kernel#rand instead of Object#hash seems
better. printing a few hash-values suggest they're not that random anyway...

Other than that, would you sort the hash (or iterator) on its keys, its
values or insertion sequence?

NB: why did I read "addictive" at first pass? The question has been raised
more often; and I admit I have overridden Hash#keys (and Hash each_pair,
iirc) to achieve a (partially) sorted effect... The problem is that you can
not generally sort keys (specifically not symbols).