A sloppy hash table should be understood at the implementation level, so make a note of what you noticed when you read it briefly. I couldn't read it 10 years ago, but this time I could read it quickly. (I read Adopt Open JDK 13)
Inside the table, data was managed by the following classes. In short, it is implemented by Closed Addressing.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
/ ** Middle clothes * / }
As an aside, the Unified Map of Eclipse Collection (10.1) was also Open Addressing, but this was chained in an array instead of chaining with pointers. It seems that the reason is that you want to use the memory cache like Open Addressing.
Hash value calculation. When the number of elements is small, in order to avoid the storage location being determined only by the lower bits, the upper 16 bits are XORed to the lower 16 bits so that the upper bits can also be used.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
How to look up the hash table. The index was the value obtained by subtracting 1 from the number of elements n in the table and ANDing.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
By the way, the number of elements in the table (tab.length above) seems to be a multiple of 2, and when -1 is set from that, all bits are set, so it seems that the operation leaves the lower bits.
Recommended Posts