【题目描述】
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.
在数据结构中，哈希函数是用来将一个字符串（或任何其他类型）转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数算法是使用数值33，假设任何字符串都是基于33的一个大整数，比如：
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
其中HASH_SIZE表示哈希表的大小(可以假设一个哈希表就是一个索引0 ~ HASH_SIZE-1的数组)。
给出一个字符串作为key和一个哈希表的大小，返回这个字符串的哈希值
【题目链接】
www.lintcode.com/en/problem/hash-function/
【题目解析】
基本实现题，大多数人看到题目的直觉是按照定义来递推，但其实这里面大有玄机，因为在字符串较长时使用long 型来计算33的幂会溢出！所以这道题的关键在于如何处理大整数溢出。对于整数求模，(a * b) % m = a % m * b % m这个基本公式务必牢记。根据这个公式我们可以大大降低时间复杂度和规避溢出。
【参考答案】
