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.f

**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.

Solution: Use a helper to avoid overflow. To calculate a*33%HASH_SIZE, instead of multiply by 33, we add a to itself 33 times. if(result+num>mod) we only add num-mod it to the result, otherwise, just need to add num to result. In this case, we are either adding or removing HASH_SIZE from the final result so it won’t overflow.

public int hashCode(char[] key, int HASH_SIZE) { int result = 0; for (int i = 0; i < key.length; i++) { result = helper(result, 33, HASH_SIZE); result += key[i]; result %= HASH_SIZE; } return result; } int helper(int num, int base, int mod) { int result = 0; for (int i = 0; i < base; i++) { if (result + num > mod) { result += num - mod; } else { result += num; } } return result; }