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/#
解題思路：
代碼很簡(jiǎn)單沾凄，但是int類(lèi)型非常容易溢出榨汤，所以在這里有兩個(gè)點(diǎn)需要注意：
1）1LL * 任何數(shù)，就可以轉(zhuǎn)化成long long數(shù)據(jù)類(lèi)型规婆，防止單次計(jì)算上溢
2）每次計(jì)算以后%HASH_SIZE挠唆，與最后去模效果一樣糙申，而且可以防止上溢
Tips:
因?yàn)閞esult一開(kāi)始等于0齐佳，所以每次對(duì)其33，而不是直接對(duì)char33填硕，這樣達(dá)到指數(shù)遞減效果麦萤。
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; }
