> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/128hash-function.md).

# 128.Hash Function

## 1.Description(Easy)--Hash

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

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

## 2.Code

基本实现题，大多数人看到题目的直觉是按照定义来递推不就得了嘛，但其实这里面大有玄机，因为在字符串较长时使用 long 型来计算33的幂会溢出！所以这道题的关键在于如何处理**大整数溢出**。对于整数求模，`(a * b) % m = a % m * b % m`这个基本公式务必牢记。根据这个公式我们可以大大降低时间复杂度和规避溢出。

于是应用模运算的法则，每一次累加sum时，就可以取模HASH\_SIZE，这样就可以很显著地减小最终的sum值。

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

(a + b) % p = (a % p + b % p) % p

(a \* b) % p = (a % p \* b % p) % p

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