Comment by mjevans

Random numbers sound possibly expensive for 'small' caches. Though I /offhand/ I guess if there's a hardware RNG source it doesn't need to be cryptographically secure or trusted as long as it's fast for this task.

Similarly if updates are bursty an idle cull could use a bitvector to mark free slots within a fixed array for rather low overhead and a burst of speedy inserts when load picks up. Something close is probably already necessary overhead for when the cache isn't yet populated.