# Hash Function

## Question

### Problem Statement

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 $33^3$ + 98 $33^2$ + 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.

## 题解1

### Java

class Solution {
/**
* @param key: A String you should hash
* @param HASH_SIZE: An integer
* @return an integer
*/
public int hashCode(char[] key,int HASH_SIZE) {
if (key == null || key.length == 0) return -1;

long hashSum = 0;
for (int i = 0; i < key.length; i++) {
hashSum += key[i] * modPow(33, key.length - i - 1, HASH_SIZE);
hashSum %= HASH_SIZE;
}

return (int)hashSum;
}

private long modPow(int base, int n, int mod) {
if (n == 0) {
return 1;
} else if (n == 1) {
return base % mod;
} else if (n % 2 == 0) {
long temp = modPow(base, n / 2, mod);
return (temp % mod) * (temp % mod) % mod;
} else {
return (base % mod) * modPow(base, n - 1, mod) % mod;
}
}
}


## 题解2 - 巧用求模公式

$\begin{array}{cl} hashcode(abc) & = & (a \times 33^{2} + b \times 33 + c)\% M\\ & = & (33(33\times a+b)+c)\% M\\ & = & (33(33(33\times0+a)+b)+c)\% M \end{array}$

### Java

class Solution {
/**
* @param key: A String you should hash
* @param HASH_SIZE: An integer
* @return an integer
*/
public int hashCode(char[] key,int HASH_SIZE) {
if (key == null || key.length == 0) return -1;

long hashSum = 0;
for (int i = 0; i < key.length; i++) {
hashSum = 33 * hashSum + key[i];
hashSum %= HASH_SIZE;
}

return (int)hashSum;
}
}