Rehashing can be improved a bit, specifically with the addition of something like CacheLoader.loadKeys(Set<Object> excludes). This will allow the rehash code to load just the necessary keys, excluding keys already considered from the data container directly, and then inspect each key to test if the key needs to be rehashed elsewhere. If so, the value could be loaded using load(), considering that as cluster sizes increase, rehashing would only affect a smaller percentage of overall data.