# Hash Function

## Question

> 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) * 333 + ascii(b) * 332 + 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.

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

**Example**

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

## Analysis

直白的实现方法就是按照定义对sum进行HASH\_SIZE取模运算，但是实际上这样会产生溢出。于是应用模运算的法则，每一次累加sum时，就可以取模HASH\_SIZE，这样就可以很显著地减小最终的sum值。

需要注意到是定义sum为long类型，最终返回时转化为int。

参考： <http://baike.baidu.com/view/2385246.htm> <https://en.wikipedia.org/wiki/Modular_arithmetic>

## Solutions

```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) {
        int N = key.length;
        long sum = 0;
        for (int i = 0; i < N; i++) {
            sum = (sum * 33 + (int) (key[i])) % HASH_SIZE;
        }

        return (int) (sum);
    }
};
```