Re: Re-orderable keyed access structure?

[kvale]

If the array is kept sorted, for some appropriate comparison operator, then searches for keys in that array are all O(log N). Hash lookups are also typically logarithmic, so it seems that array + binary search would do what you want: reorder the array as needed while still locating keys with good efficiency.

[BrowserUk]

The ordering of the array isn't dependant upon the values of the referenced items. The positions change purely on the basis of theway in which they are accessed--kind of like a least-recently used or most recently used algorithm--so there is no sort order through which to perform a binary search. That I can see anyway.

Each time an item is accessed, via it's key, it's position may be changed. Conversely, if an attempt is made to read a new item via its key, and it isn't already in the array, the top item may be popped off the array to free up room for the new item to be added. When this is done, the old item's hash reference must be nulled or deleted.

Hence the need to able to discover the hash key via it's array index, and it's array index via it's hash key.