How about a doubly-linked list with "hash characteristsics"? The back links are "slower" than the forward links. I say "hash characteristics" since it is unneccessary to count to 5 in order to use the number...Any other ideas?
Update: maybe even a hash with linked list characteristics?