Re^5: What makes an array sorted and a hash unsorted?

Howdy!

You appear to be conflating being ordered with being sorted and searching with simple access.

Arrays are ordered. The elements have a defined order. Orderedness and sortedness are not the same thing. One speaks to the intrinsic sequencing of the elements of a collection (orderedness) while the other speaks to an externally imposed sequencing of the elements of a collection (sortedness).

Searching for an element is different from accessing an element. In the first case, you don't know which element is the target, so you have to find it. Accessing a specific element means you have the index of the item already. For a hash, the index is a string; for an array, the index is an integer.

You cannot speak generally of the intrinsic sequence of the elements of a hash. It is not a fixed quantity. Adding or removing elements can change the sequence in ways that are not readily predictable. Iterating over the elements first involves collecting the set of keys. That act turns them into a list which has an intrinsic order, but it's no longer a hash or a set. The set of keys has become an ordered n-tuple (where n is the number of keys), but it's no longer a set.

yours,
Michael

Comment on Re^5: What makes an array sorted and a hash unsorted?

Replies are listed 'Best First'.
Re^6: What makes an array sorted and a hash unsorted? by JavaFan (Canon) on Jun 03, 2009 at 15:18 UTC
You cannot speak generally of the intrinsic sequence of the elements of a hash. It is not a fixed quantity It most certainly is. Each hash element is mapped to a bucket using a fixed function: `hash(key,seed,nr_of_bufs)`. `key` is the key to be hashed, `seed` is fixed at program start, and `nr_of_bufs` is the current number of buffers used. But there's no randomness involved in the `hash` function. Given the same input parameters, the result will always be the same. It's a deterministic function. Arrays can be seen as a special case, where the "hash" function is just `sub hash {0+$_[0]}`.	[reply] [d/l] [select]
Re^7: What makes an array sorted and a hash unsorted? by herveus (Prior) on Jun 03, 2009 at 18:33 UTC
Howdy! You are missing the point. In general, a Perl hash with a given set of keys will produce them in a consistent order when you call keys(). Calling keys() makes the set of keys into a list. That list is inherently ordered, but it's not the hash. Now, add or delete elements from the hash. There is no assurance that the list returned by keys() will be in the same order. In fact, insertions can change the order of keys that existed before. The set of keys in a hash has no deterministic fixed order. Change the insertion order and the keys come out in a different order. Consider the following: `my @hash_keys = qw/foo bar baz quux w x y z/; my %foo; my %bar; for my $key (@hash_keys) { $foo{$key} = 1; print "$key: ", join(':', keys %foo), "\n"; } for my $key (reverse @hash_keys) { $bar{$key} = 1; print "$key: ", join(':', keys %bar), "\n"; }` [download] which produced the following output: `foo: foo bar: bar:foo baz: bar:baz:foo quux: bar:baz:quux:foo w: w:bar:baz:quux:foo x: w:bar:baz:quux:x:foo y: y:w:bar:baz:quux:x:foo z: y:w:bar:baz:quux:x:foo:z z: z y: y:z x: y:x:z w: w:y:x:z quux: w:y:quux:x:z baz: w:y:baz:quux:x:z bar: w:y:bar:baz:quux:x:z foo: w:baz:x:y:bar:quux:foo:z` [download] If there was an intrinsic sequence, why does adding "foo" to hash cause "x" to suddenly appear much earlier in the list produced by keys()? Why are the lists with all eight keys not the same? If the sequence were intrinsic, one would not expect either of those outcomes. yours, Michael	[reply] [d/l] [select]
Re^8: What makes an array sorted and a hash unsorted? by JavaFan (Canon) on Jun 03, 2009 at 20:31 UTC
If there was an intrinsic sequence, why does adding "foo" to hash cause "x" to suddenly appear much earlier in the list produced by keys Which part of hash(key,seed,nr_of_bufs). key is the key to be hashed, seed is fixed at program start, and nr_of_bufs is the current number of buffers used did you fail to grasp?	[reply]
Re^6: What makes an array sorted and a hash unsorted? by JavaFan (Canon) on Jun 03, 2009 at 14:00 UTC
You appear to be conflating being ordered with being sorted and searching with simple access. I'm just following the terminology set down by the OP. Let me recall the name of the topic: What makes an array sorted* and a hash unsorted?* Surely you don't suggest that ikegami thinks all arrays are sorted the way you describe sorted?	[reply]
Re^7: What makes an array sorted and a hash unsorted? by herveus (Prior) on Jun 03, 2009 at 14:16 UTC
Howdy! The properties of being sorted and being ordered are very different things. Well, being sorted requires being ordered, but not the other way around. The topic makes an incorrect assertion right up front, and a number of respondents have noted that. Insisting on sticking with demonstrably incorrect usage is kind of silly. My response was specifically to the words you wrote. I'm not trying to read ikegami's mind here. Was my explanation confusing or unclear? yours, Michael	[reply]