Hash Function · 數據結構與算法/leetcode/lintcode題解

# Hash Function ### Source - lintcode: [(128) Hash Function](http://www.lintcode.com/en/problem/hash-function/) ~~~ 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 Have you met this question in a real interview? Yes 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. ~~~ ### 題解1 基本實現題，大多數人看到題目的直覺是按照定義來遞推不就得了嘛，但其實這里面大有玄機，因為在字符串較長時使用 long 型來計算33的冪會溢出！所以這道題的關鍵在于如何處理**大整數溢出**。對于整數求模，`(a * b) % m = a % m * b % m` 這個基本公式務必牢記。根據這個公式我們可以大大降低時間復雜度和規避溢出。 ### Java ~~~ 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) { if (key == null || key.length == 0) return -1; long hashSum = 0; for (int i = 0; i < key.length; i++) { hashSum += key[i] * modPow(33, key.length - i - 1, HASH_SIZE); hashSum %= HASH_SIZE; } return (int)hashSum; } private long modPow(int base, int n, int mod) { if (n == 0) { return 1; } else if (n == 1) { return base % mod; } else if (n % 2 == 0) { long temp = modPow(base, n / 2, mod); return (temp % mod) * (temp % mod) % mod; } else { return (base % mod) * modPow(base, n - 1, mod) % mod; } } } ~~~ ### 源碼分析題解1屬于較為直觀的解法，只不過在計算33的冪時使用了私有方法`modPow`, 這個方法使用了對數級別復雜度的算法，可防止 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。") 的產生。注意兩個 int 型數據在相乘時可能會溢出，故對中間結果的存儲需要使用 long. ### 復雜度分析遍歷加求`modPow`，時間復雜度 O(nlogn)O(n \log n)O(nlogn), 空間復雜度 O(1)O(1)O(1). 當然也可以使用哈希表的方法將冪求模的結果保存起來，這樣一來空間復雜度就是 O(n)O(n)O(n), 不過時間復雜度為 O(n)O(n)O(n). ### 題解2 - 巧用求模公式從題解1中我們可以看到其時間復雜度還是比較高的，作為基本庫來使用是比較低效的。我們從范例`hashcode("abc")`為例進行說明。 hashcode(abc)=(a×332+b×33+c)%M=(33(33×a+b)+c)%M=(33(33(33×0+a)+b)+c)%M\begin{array}{cl}hashcode(abc) & = & (a \times 33^{2} + b \times 33 + c)\% M\\ & = & (33(33\times a+b)+c)\% M\\ & = & (33(33(33\times0+a)+b)+c)\% M\end{array}hashcode(abc)===(a×332+b×33+c)%M(33(33×a+b)+c)%M(33(33(33×0+a)+b)+c)%M 再根據 (a×b)%M=(a%M)×(b%M)(a \times b) \% M = (a \% M) \times (b \% M)(a×b)%M=(a%M)×(b%M) 從中可以看出使用迭代的方法較容易實現。 ### Java ~~~ 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) { if (key == null || key.length == 0) return -1; long hashSum = 0; for (int i = 0; i < key.length; i++) { hashSum = 33 * hashSum + key[i]; hashSum %= HASH_SIZE; } return (int)hashSum; } } ~~~ ### 源碼分析精華在`hashSum = 33 * hashSum + key[i];` ### 復雜度分析時間復雜度 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1).