HashFunction.md

##Hash Function

15% Accepted

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^1 + ascii(d)) % HASH_SIZE

                              = (97* 33^3 + 98 * 33^2 + 99 * 33^1 +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.

####Tags Expand

• Hash Table

####思路

• 字符串较长时使用 long 型来计算33的幂会溢出！所以这道题的关键在于如何处理大整数溢出
• (a * b) % m = (a % m * b % m) % m = ((a % m) * b) % m
• 多项式每次乘以33之后 就开始求模，就不会溢出
• 直接做是会溢出的

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) {
        // write your code here
        long hash = 0;
        for (int i = 0; i < key.length; i++) {
            hash = hash * 33 + (int) key[i];
            hash = hash % HASH_SIZE;
        }
        return (int)hash;
    }
};