Hashes with intelligent management adapt themselves to growth. It's best when you know exactly what's the data, of course. In my case, as the cache is size limited anyway, the hash can be "true O(1)". If the required cache size is N, making a hash with ~ 2N buckets should make practically all accesses O(1).