Description:
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
Example:
For key="abcd" and size=100, return 78
Link:
http://www.lintcode.com/en/problem/hash-function/#
解题思路：
代码很简单，但是int类型非常容易溢出，所以在这里有两个点需要注意：
1）1LL * 任何数，就可以转化成long long数据类型，防止单次计算上溢
2）每次计算以后%HASH_SIZE，与最后去模效果一样，而且可以防止上溢
Tips:
因为result一开始等于0，所以每次对其33，而不是直接对char33，这样达到指数递减效果。
Time Complexity：
O(N)
完整代码：
int hashCode(string key,int HASH_SIZE) { if(key.size() == 0) return 0; int result = 0; int len = key.size() - 1; for(char ch : key) result = (1LL * result * 33 + ch) % HASH_SIZE; return result; }
