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

I would not use the term sorted, I would use the term ordered.

This distinction is perhaps more obvious when you look at another way to map a string to a value. The two approaches I'm familiar with are binary trees and hash tables.

In the case of a binary tree, the items are ordered because the structure of the tree imposes an intrinsic order on the data. Hashes, on the other hand, are intrinsically not ordered internally. In fact, this feature is what allows for (relatively) inexpensive insertion and deletion. (Two items with keys very close to each other are likely to end up in different areas of the hash table.)

As you said, the interface we see for the hash could be changed to return the data in an ordered fashion, but the data structure is still intrinsically unordered.

G. Wade
  • Comment on Re: What makes an array sorted and a hash unsorted?

Replies are listed 'Best First'.
Re^2: What makes an array sorted and a hash unsorted?
by Fletch (Bishop) on Jun 01, 2009 at 21:46 UTC

    Having probably instigated this with my use of the term today :), I was browsing over wikipedia entries while eating lunch and trying to come up with my take. I think that you're getting at the distinction here: Perl has associative arrays (an abstract datatype) which are implemented on top of hash tables (a more concrete datatype; which of course explains the colloquial usage of calling them "hashes"). However neither of these two guarantees nor provides any intrinsic ordering of keys. Were the associative arrays implemented on top of something else instead (say some sort of binary search tree, or an assoc list with new items added in sorted order rather than just prepended) the underlying implementation would then provide an intrinsic ordering of keys and then Perl's associative arrays could be said to be ordered (and probably wouldn't be called hashes . . . :).

    So yeah, "unordered" is probably a better description than "unsorted".

    The cake is a lie.
    The cake is a lie.
    The cake is a lie.

[reply]
Re^2: What makes an array sorted and a hash unsorted?
by JavaFan (Canon) on Jun 01, 2009 at 23:29 UTC
    Hashes, on the other hand, are intrinsically not ordered internally. In fact, this feature is what allows for (relatively) inexpensive insertion and deletion. (Two items with keys very close to each other are likely to end up in different areas of the hash table.)
    That's not correct. Hash keys are ordered, otherwise you wouldn't be able to quickly search for them (and hence, no quick deletion either). However, the order internally isn't the same order people want (this thread seems to consider "ordered hashes" as "keys are sorted" - it's not uncommon for people to mean "keys returned in insertion order" when they talk about "ordered hashes"). I've always understood that keys (and its friends) return the keys in the way they are laid out internally - so certainly "ordered", but only after applying a hash function.
[reply]
[d/l]

      You are correct. I was sloppy with the term keys.

      It would be more accurate to say that the data is not ordered with respect to the original keys. However, it is ordered with respect to the result of the hash function applied to the keys.

      Given that a good hash function should distribute the data fairly evenly through the table (and that the hash function is often not known by the user), this is effectively the same as saying that the data is not ordered with respect to the original keys.

      G. Wade
[reply]
      Howdy!

      Hash keys have no predefined ordering. Any given call to keys() will present the keys as a list which will, at that instant, have an order, but that particular ordering is neither persistent nor stable nor predictable in the face of insertions and deletions. Rapid searching for hash keys has nothing to do with ordering, but rather with the nature of hash functions. Ideally, any given key value hashes to a unique value in the hash that can be found (or the existence of tested for) in constant time. Searching an ordered list is going to be O(log n) or worse.

      yours,
      Michael
[reply]
        Searching an ordered list is going to be O(log n) or worse.
        If that were true, finding an item in an array would take logarithmic time (this thread has already established arrays are sorted). It doesn't of course, given the key, it takes constant time to find something in an array.

        Just because binary search on a list of sorted values is logarithmic doesn't mean any search is logarithmic.

[reply]

In Section Meditations