Forum: Ruby Order in Hashes

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
7b56484f1e9d9af7b4c2c7ef16142197?d=identicon&s=25 Martin Boese (Guest)
on 2006-04-04 14:46
(Received via mailing list)
Hello,

I am building a menu structure for rails that I'd like to store in a
simple
Hash.

Now I found out that ruby Hashes do not keep the order, like this
program:

> b = {'upkpgn'=>1,
>      'jmay'=>2,
>      'vkvxxm'=>3}
>
> b.each_key {|k|
>  puts "%s => %s" % [k, b[k]]
> }

...will output:

> upkpgn => 1
> vkvxxm => 3
> jmay => 2

(vkvxxm and jmay are swapped)

I read an article describing this behavior, but it only mentions a
'sort'
solution which is useless for me because my menu has a logical order:

http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby...

Are there any workarounds for this? Or shall I rather write my own
containers?

BTW: Why is ruby doing this anyways...?!

Thanks,
Martin
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-04-04 14:55
(Received via mailing list)
On Apr 4, 2006, at 7:43 AM, Martin Boese wrote:

>>      'jmay'=>2,
>> jmay => 2
>
> (vkvxxm and jmay are swapped)

b.keys.sort.each { |k|
   # ...
}

> I read an article describing this behavior, but it only mentions a
> 'sort'
> solution which is useless for me because my menu has a logical order:
>
> http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby...
>
> Are there any workarounds for this?

You've mentioned the first one, you can sort when you access the values.

You could also switch away from a Hash and use something like an
Array of Arrays.  Lookup the method Array#assoc and Array#rassoc,
which might be helpful with this.

> Or shall I rather write my own containers?

I'm pretty sure there is an OrderedHash on the RAA.

> BTW: Why is ruby doing this anyways...?!

A Hash is, by definition, an unordered construct.

James Edward Gray II
D2ce3fc131413e4456054ea24efcca0e?d=identicon&s=25 unknown (Guest)
on 2006-04-04 14:58
(Received via mailing list)
>
> BTW: Why is ruby doing this anyways...?!
>

A Hash is an unsorted container; It is a widely-used algorithm that
makes no guarantees about the order of keys to optimise reading times at
the expense of insertion.

As with all algorithms, if the container doesn't have the
characteristics you want, then you are using the wrong container.

There's a Wikipedia article here on Hash Tables:

http://en.wikipedia.org/wiki/Hash_table

I would suggest that what you're looking for is not a Hash at all,
but simply a List.

Martin
C3050802c32066bc092f54760f21b4f6?d=identicon&s=25 Bob Gustafson (Guest)
on 2006-04-04 15:45
(Received via mailing list)
A hash has no 'order' requirement. Items are added in an
'implementation efficiency' order - which may be different on
different underlying platforms.

If you want to retain a particular order, use an array.

Bob G
159cd33667611645164e8623de42f67e?d=identicon&s=25 Toby DiPasquale (Guest)
on 2006-04-04 15:46
Martin Boese wrote:
> Hello,
>
> I am building a menu structure for rails that I'd like to store in a
> simple
> Hash.
>
> Now I found out that ruby Hashes do not keep the order, like this
> program:
>
>> b = {'upkpgn'=>1,
>>      'jmay'=>2,
>>      'vkvxxm'=>3}
>>
>> b.each_key {|k|
>>  puts "%s => %s" % [k, b[k]]
>> }
>
> ...will output:
>
>> upkpgn => 1
>> vkvxxm => 3
>> jmay => 2
>
> (vkvxxm and jmay are swapped)
>
> I read an article describing this behavior, but it only mentions a
> 'sort'
> solution which is useless for me because my menu has a logical order:
>
> http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby...
>
> Are there any workarounds for this? Or shall I rather write my own
> containers?

If all you're using it for is to test existence of keys, then Hash can
be replaced with SortedSet. See 'ri Set' for more info (the two classes
are in the same file in the standard distribution). Otherwise, you will
need to find or implement a Hash that maintains key order.

--
Toby DiPasquale
0b561a629b87f0bbf71b45ee5a48febb?d=identicon&s=25 Dave Burt (Guest)
on 2006-04-04 16:15
(Received via mailing list)
Martin Boese wrote:
> I am building a menu structure for rails that I'd like to store in a simple
> Hash.
>
> Now I found out that ruby Hashes do not keep the order, like this program:
> ...
> Are there any workarounds for this? Or shall I rather write my own containers?

You can use SortedHash. You can get it from the RAA. It preserves sort
order.

Cheers,
Dave
D2ce3fc131413e4456054ea24efcca0e?d=identicon&s=25 unknown (Guest)
on 2006-04-04 16:49
(Received via mailing list)
On Tue, Apr 04, 2006 at 11:13:47PM +0900, Dave Burt wrote:
> Martin Boese wrote:
> > I am building a menu structure for rails that I'd like to store in a simple
> > Hash.
> >
> > Now I found out that ruby Hashes do not keep the order, like this program:
> > ...
> > Are there any workarounds for this? Or shall I rather write my own containers?
>
> You can use SortedHash. You can get it from the RAA. It preserves sort
> order.

I assume a SortedHash is a tree of some kind? Probably Red-Black Tree,
or similar. In which case, this is not what he wants. He wants the keys
to be read out in the order in which they were inserted, he doesn't want
*sorting* per se, at all.

As far as I can tell, what he wants is a list.

Martin
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2006-04-04 17:04
(Received via mailing list)
If you need one, have a look at Facets' Dictionary class (also called
OrderedHash).

  http://facets.rubyforge.org

T.
0b561a629b87f0bbf71b45ee5a48febb?d=identicon&s=25 Dave Burt (Guest)
on 2006-04-04 17:20
(Received via mailing list)
azrael@cream.org wrote:
> On Tue, Apr 04, 2006 at 11:13:47PM +0900, Dave Burt wrote:
>> You can use SortedHash. You can get it from the RAA. It preserves sort
>> order.
>
> I assume a SortedHash is a tree of some kind? Probably Red-Black Tree,
> or similar. In which case, this is not what he wants. He wants the keys
> to be read out in the order in which they were inserted, he doesn't want
> *sorting* per se, at all.

Sorry about the error. The name of the package I'm thinking of is
actually OrderedHash, and it is what he wants - it preserves (insertion)
order.

http://raa.ruby-lang.org/project/orderedhash/

Cheers,
Dave
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2006-04-04 17:45
(Received via mailing list)
On Tue, 4 Apr 2006, Martin Boese wrote:

>>
> (vkvxxm and jmay are swapped)
>
> I read an article describing this behavior, but it only mentions a 'sort'
> solution which is useless for me because my menu has a logical order:
>
> http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby...
>
> Are there any workarounds for this? Or shall I rather write my own containers?

use an Array and Array#assoc

     harp:~ > cat a.rb
     b =
       %w( upkpgn 1 ),
       %w( jmay 2 ),
       %w( vkvxxm 3 )

     b.each{|kv| puts "%s => %s" % kv}

     puts b.assoc('upkpgn').last
     puts b.assoc('jmay').last
     puts b.assoc('vkvxxm').last


     harp:~ > ruby a.rb
     upkpgn => 1
     jmay => 2
     vkvxxm => 3
     1
     2
     3


> BTW: Why is ruby doing this anyways...?!

hashes are, by definition, unsorted containers.

regards.

-a
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2006-04-04 17:48
(Received via mailing list)
On Wed, 5 Apr 2006, Dave Burt wrote:

> Sorry about the error. The name of the package I'm thinking of is
> actually OrderedHash, and it is what he wants - it preserves (insertion)
> order.
>
> http://raa.ruby-lang.org/project/orderedhash/

that one has some errors.  i've patched it in my alib, also on the raa.
feel
free to lift it.

fyi.

-a
This topic is locked and can not be replied to.