Hash key ordering?

dargosch has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: Hash key ordering? by jmcnamara (Monsignor) on May 02, 2002 at 11:38 UTC
Hashes with the same keys won't necessarily return the keys in the same order, as shown below. However, as Juerd points out, the order shouldn't change for a given hash if the keys don't change, also shown below. The only problem that I can see is that the order the keys are returned in might change in a future release. So, I wouldn't rely on that. `#!/usr/bin/perl -wl use strict; my %h1; my %h2; @h1{1..10} = undef; print join " ", keys %h1; @h1{5..10, 1..4} = undef; print join " ", keys %h1; @h2{5..10, 1..4} = undef; print join " ", keys %h2; __END__ Prints: 1 2 3 10 4 5 6 7 8 9 1 2 3 10 4 5 6 7 8 9 1 2 3 4 10 5 6 7 8 9` [download] -- John.	[reply] [d/l]
Re: Re: Hash key ordering? by demerphq (Chancellor) on May 02, 2002 at 12:42 UTC
A second thought: There should be no anticipation of the same set of keys being produced on two seperate runs, or even in different hashes, but keys will return the same list for the same hash in the same runs every time. Yves / DeMerphq --- Writing a good benchmark isnt as easy as it might look.	[reply]
Re: Re: Hash key ordering? by dargosch (Scribe) on May 02, 2002 at 12:06 UTC
Thank you all for all the help on that issue.	[reply]
Re: Hash key ordering? by tadman (Prior) on May 02, 2002 at 10:37 UTC
The safe answer is "No", the order of things in the hash is arbitrary. In practice, you might find some relationship between data and order. This, however, may change from version to version, or platform to platform, depending on how the hash is implemented. In some cases, you might not be using a hash at all, but something tied to another source. Who knows what might be going on in there. If you care about order, always ask for it sorted. Don't bother sorting, though, if you are merely iterating, since that usually worthless.	[reply]
Re: Hash key ordering? by choocroot (Friar) on May 02, 2002 at 11:00 UTC
If you need to keep/maintain the order of the keys you can give a look at Tie::IxHash http://search.cpan.org/search?mode=module&query=Tie%3A%3AIxHash "This Perl module implements Perl hashes that preserve the order in which the hash elements were added."	[reply]
Re: Hash key ordering? by Juerd (Abbot) on May 02, 2002 at 10:39 UTC
If the hash keys do not change, their order will not change. - Yes, I reinvent wheels. - Spam: Visit eurotraQ.	[reply]
Re: Hash key ordering? by Elian (Parson) on May 02, 2002 at 13:37 UTC
You can count on it within runs of a particular program. The order is dependent on the hashing function, which can't change during the course of a program run. (Well, it can, but it takes a huge amount of work) The hashing function has changed at least once during perl 5's life though, and may change again, so different versions of perl may give you different ordering. All bets are off if the hash is tied, of course.	[reply]
Re: Hash key ordering? by rinceWind (Monsignor) on May 02, 2002 at 12:04 UTC
The arbitrariness of sequential hash key retrieval via each or keys does present a design problem sometimes. See my recent node for when this caused me a major problem with persistence and Data::Dumper.	[reply]
Re: Hash key ordering? by Cybercosis (Monk) on May 02, 2002 at 17:49 UTC
Aside from the hash algorithm changing (which shouldn't happen unless you change your perl), and barring any particularly bizarre things, you should be able to count on a consistant key ordering if you create the keys in the same order. Internally, perl copes with hash collisions (two keys hashing to the same numeric value) by sticking the offending value at the end of a linked list with the other, not-so-offending values. When it goes to assemble the list for the keys() function, it adds them in a linear fashion. So, if you have two keys that collide, keys() won't list them in the same order if they appear in a different order in the linked list. OTOH, if you sort the keys() list, they'll always be in the same order, so do that. =-) ~Cybercosis nemo accipere quod non merere	[reply]
Re: Re: Hash key ordering? by kwilliams (Sexton) on May 03, 2002 at 05:40 UTC
Most people's replies seem to be focusing on the details of the implementation, but this isn't the greatest idea. One can, however, make certain conclusions based only on guarantees in the documentation: (perldoc -f keys) The keys are returned in an appar- ently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be the same order as either the `values' or `each' function produces (given that the hash has not been modified). [download] That's exactly how much you can count on - the fact that it is "the same order as" values() and each() means that it also must be the same order as future calls to keys() (by the transitivity property of the word "same"). If you make any changes to the hash, this guarantee goes away. Of course, this is not the same as the OP's original phrase "provided of course that the keys are the same" - you can insert & delete things in a hash and end up with the same eventual set of keys, but your modifications may still change the order of keys().	[reply] [d/l]

Greetings fellow monks!