http://www.perlmonks.org?node_id=767329


in reply to What makes an array sorted and a hash unsorted?

Hash values are often reordered when more buckets are allocated and so forth, right?

I would say the thing that makes arrays sorted is that you can say @arrayname to get the values, and they'll be in a consistent order. If you say values %hash to get the values of a hash, they will be in no particular order.

Arrays have push and pop and shift and unshift that take advantage of the order of the array. for iterates through arrays in known order; each iterates through hashes. I think not merely our usage, but the language's design, says that arrays are ordered and hashes are unordered.


Caution: Contents may have been coded under pressure.

Replies are listed 'Best First'.
Re^2: What makes an array sorted and a hash unsorted?
by ikegami (Patriarch) on Jun 01, 2009 at 17:35 UTC

    If you say values %hash to get the values of a hash, they will be in no particular order.

    So if the following change was built into Perl, hashes would be considered sorted?

    use subs qw( values ); sub values(\%) { my $h = shift; return keys(%$h) if !wantarray(); my @keys = sort keys(%$h); return @{$h}{@keys}; }
    my %h = map { $_ => $_ } 'a'..'z'; print(values(%h), "\n"); # abcdefghijklmnopqrstuvwxyz

    I think there's more to it than just this change in the builtin accessors.

      Yes, they'd be considered sorted. However, it would be of limited use, which is probably why it isn't built that way. Arrays are designed for things that are sorted. Hashes are designed for lookup by key, with ordering left up to the users as a separate step.

      When people think they have a hash in a particular order, it isn't generally ASCIIbetical order, but the order they put the elements into it. Obviously, that's a misconception. Hashes don't preserve order. Arrays, on the other hand, do. Wherever you put an element, it has a position relative to other elements of the array. That's intrinsic to the array.

      All the iterators built into the language will walk the array in the same order. That is not the case for hash iterators. The language could have been written to iterate over arrays in random order, or hashes in predefined order, but it was not.


      Caution: Contents may have been coded under pressure.

        Yes, they'd be considered sorted.

        Even with that change, I think we'll still get EXACTLY the same questions we get today. People want custom ordering of keys when dealing with hashes (as opposed to custom ordering of values when dealing with arrays).

        So if your claim is true, that means the answer we currently give ("hashes are unsorted") is wrong because the hashes being sorted wouldn't help at all.

        I actually believe that hash are unsorted, and I believe the answer we are giving is right.

        When people think they have a hash in a particular order, it isn't generally ASCIIbetical order, but the order they put the elements into it.

        Exactly. It's how we use hashes that makes them unsorted. The keys are actually part of the value, and thus can't be used for ordering.