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




More information about the use-livecode mailing list