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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s