5 popular hash functions..?

Question

I will be appearing for Google onsite interview in a week time.I understand that hash tables,hash maps,hash functions are very useful and come handy in many interview questions like dictionary,bucket sort,to check duplicacy of one whole document, duplicacy of a URL etc , be it on strings or be it on integers. I am wondering what are some of the popular hash functions both on integers and strings.

One I can think of is h(n)=n for integers, where say we want to rank students depending on their marks i.e. very limited possible values range.

Please help with more popular choices esp for strings,documents.

Thanks,

Answer 1

For strings, one may use the string's cryptographic hash as the key for a hash table. This will usually lead to a uniform distribution of the hash keys, which is a good hash table property.

If you want to narrow the size of the key (for example only 32 bit), you can still select a cryptographic hash function such as SHA-256 and use the lower 32 bits.

One can also represent a number as a string or as binary data and calculate its cryptographic hash to ensure a uniform key distribution.

Once your keys are uniformally distributed, you don't need to use a complex hash function- you can just map the key range into equally-sized bins.

To prepare yourself better for the interview, you may want to read this as well.