Description
ConcurrentHashMapV8 hash spreading function is very simple:
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}For Long and Integer keys (and anything similar) this means low values map 1:1 to hashcodes. This means a table of integer keys {1..8192} will end up occupying the low half of a 16384 slot table, while leaving the high half empty. This interacts badly with our sampling logic used in eviction since it means samples drawn from the later half of the map have to run through the a large number of entries before being able to return a sample. We should fix this by using a spreading function that better distributes the keys through the map.
Graph below shows time taken to select 8 random entries from maps of various size, and shows the issues at large map sizes for the current method (black) and the improvements after adopting the original JDK6 spreader (red).
