Seems like a cache using open addressing but no probing, just instant eviction on any initial collision. So, could also consider adding probing to lessen destr

Seems like a cache using open addressing but no probing, just instant eviction on any initial collision. So, could also consider adding probing to lessen destructive collisions (up to some chosen probing depth) while there are other unused slots, in still-constant average time. Or, any other choice-of-slots approach such as 'cuckoo hashing': http://en.wikipedia.org/wiki/Hash_table#Cuckoo_hashing http://en.wikipedia.org/wiki/Hash_table#Cuckoo_hashing Whether you'd want to pay that cost could depend on how soon you reach saturation within each reset period, after which 'every' insert results in an eviction. But if you were usually in one-for-one eviction mode, you might add a bit or more that hints 'age' or 'recent access' to probed items. Then each eviction could be biased towards an older/less-accessed value... taking more advantage of the clustering-in-time that was reported. And once you add that aging bit you might not need discrete full-restart periods ("hourly") at all: just make a useful proportion of older entries eligible for eviction each interval, maintaining a steady-state of full-array, evictions-biased-towards-older-entries.