# the keys of myArray

Dar Scott dsc at swcp.com
Fri Sep 8 11:48:54 CDT 2006

```On Sep 8, 2006, at 10:23 AM, jbv wrote:

> I created keys in an array in the following order :
> 1
> 4
> 5
> 11
> 52
> 500
> 555
>
> "the keys of myArray" outputs this :
> 1
> 11
> 4
> 500
> 5
> 555
> 52
>
> then I created the same keys but in reverse order :
> 555
> 500
> 52
> 11
> 5
> 4
> 1
>
> and "the keys of myArray" outputs this :
> 1
> 11
> 4
> 5
> 500
> 52
> 555
>
> if anyone sees any logic in the above, please let me know...

I think Richard described it.  He seems to have some "inside"
knowledge that a hash table is used.  The above data is consistent
with that.

In your example, it looks like 5 hash buckets are used:  (1), (11),
(4), (5, 500), and (52,555).  Within each bucket, the order is based
on history and is in reverse order of creation and thus the key-
element pairs are probably stored in a linked list.  It looks like
the first character has a strong influence on the hash.

If this is really the case--who knows?--then we can guess how lookup
works.  Looking up "11" means going to the second nonempty bucket
based on the hash.  The list there has only one item.  The key is
confirmed and the item is returned.  Looking up "500" involves going
to the 4th nonempty bucket quickly based on the hash.  Then each key
in the list is checked.  The first one ("5") fails, but the second
one matches and the value is returned.

On creating the list of keys, rev might go through all the buckets
and within each bucket go through all the pairs in the list.  This is
consistent with the above output.

Of course, this model could be wrong.  If you are curious you might
be able to run some experiments to see how that works.  Maybe you can
figure out the number of buckets.  Maybe timing experiments can help.

But that should be for curiosity sake only.  The order of "the keys"
is not defined by Revolution and could change as the engine changes.
This could be for subtle reasons; this might change because of a
change in an underlying library.

If you are interested in order rather than random access, maybe you
need to make a list of keys.  If you need pairs, make a line list and
each line can consist of two items.

By not giving your sort order or build order, the implementers are
free to optimize how the array works.

Dar Scott

```