Monday, May 08, 2017

About Hash

Hash table

This is a key-value look up data structure.

You can think it is an Array coupled with hash function. Hash function takes in key and output an integer as index in array, then it stores the key and value under the index.

Key is required to be stored for the reason of collision hanlding. Key's equals() function is used to determine a key that is in hash collision.

Hashtable is roughly same as HashMap in Java, except it's multi-thread safe and does not allow null key and null value.

Hash Set

In java it is a hash table that stores key itself as its look up value.

Hash Map

This is a hash table, but not thread safe and allow null key and null value.


Collision

solution is collision is linear probing and (separate) chaining, as well as doubling hashing. linear probing can lead to a problem of clustering (major drawback of linear probing) when a lot of collisions happen. chaining is a solution Java is using.

double hashing use a fomular with second hash function involved when first hash function has a collision.