Uncategorized

Hash Table

That’s implemented as “map” class which we are really using for fast ‘key’/’value’ extraction.

We need a good hash function which evenly and randomly maps ‘key’ to an index.¬†And handling of collision is required in case that two separate keys are mapped to a single index. It can be done by such as separate chain (may be implemented as linked list) and open¬†addressing (linear probing, quadratic probing). Open addressing can cause clustering. (An index is visited repeatedly) Double hashing can avoid this issue. But a good (fast, even distribution) hash function is always needed.

Code below is a real implementation in android java, copied from Android/Sdk/sources/android-23/java/util/Collections.java.

private static int secondaryHash(int h) {
    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

And collision is handled by a linked list of HashMapEntry.