Hash Function

• LintCode: No.128-Hash Function
• Problem:

  In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. 
  The objective of designing a hash function is to "hash" the key as unreasonable as possible.  
  A good hash function can avoid collision as less as possible.   
  A widely used hash function algorithm is using a magic number 33,   
  consider any string as a 33 based big integer like follow:
  hashcode("abcd") = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33 + ascii(d)) % HASH_SIZE   
                   = (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
                   = 3595978 % HASH_SIZE
  here HASH_SIZE is the capacity of the hash table 
  (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).
  Given a string as a key and the size of hash table, return the hash value of this key.
  

• Example:

  For key="abcd" and size=100, return 78
  

• Clarification:

  For this problem, you are not necessary to design your own hash algorithm or consider any   
  collision issue, you just need to implement the algorithm as described.
  

• Analysis:

  The formula in Problem is   
    hashcode("abcd") = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33 + ascii(d)) % HASH_SIZE  
  We can make it equal to   
    hashcode("abcd") = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33 + ascii(d) * 1) % HASH_SIZE
                     = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33 + ascii(d) * 33^0) % HASH_SIZE
  Asssume that a, b, c are integers,  
  (a + b + c) % d = a % d + b % d + c % d.
  Besides, needed to concern overflow issues.
  

• Java:

    public class Solution {
        public int hashCode(char[] key,int HASH_SIZE) {
            long res = 0;
            for (int i = 0; i < key.length; i++){
                res = 33 * res + (int)key[i];
                res = res % HASH_SIZE;
            }
            return (int)res;
        }
    }
  

• Time Complexity:

  • O(n), n is key length