【題目描述】
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.
在數(shù)據(jù)結(jié)構(gòu)中，哈希函數(shù)是用來將一個(gè)字符串（或任何其他類型）轉(zhuǎn)化為小于哈希表大小且大于等于零的整數(shù)。一個(gè)好的哈希函數(shù)可以盡可能少地產(chǎn)生沖突。一種廣泛使用的哈希函數(shù)算法是使用數(shù)值33，假設(shè)任何字符串都是基于33的一個(gè)大整數(shù)，比如：
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表示哈希表的大小(可以假設(shè)一個(gè)哈希表就是一個(gè)索引0 ~ HASH_SIZE-1的數(shù)組)。
給出一個(gè)字符串作為key和一個(gè)哈希表的大小，返回這個(gè)字符串的哈希值
【題目鏈接】
www.lintcode.com/en/problem/hash-function/
【題目解析】
基本實(shí)現(xiàn)題，大多數(shù)人看到題目的直覺是按照定義來遞推，但其實(shí)這里面大有玄機(jī)，因?yàn)樵谧址^長(zhǎng)時(shí)使用long 型來計(jì)算33的冪會(huì)溢出！所以這道題的關(guān)鍵在于如何處理大整數(shù)溢出。對(duì)于整數(shù)求模，(a * b) % m = a % m * b % m這個(gè)基本公式務(wù)必牢記。根據(jù)這個(gè)公式我們可以大大降低時(shí)間復(fù)雜度和規(guī)避溢出。
【參考答案】
