Suppose we wish to search a linked list of length n, where each element contains a key k along with a hash value h(k). Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key?
首先计算出给定关键字的hash值. 对列表中的每个元素,先验证hash值对不对,再进行字符串的比较.
Suppose that a string of r characters is hashed into m slots by treating it as a radix-128 number and then using the division method. The number m is easily represented as a 32-bit computer word, but the string of r characters, treated as a radix-128 number, takes many words. How can we apply the division method to compute the hash value of the character string without using more than a constant number of words of storage outside the string itself?
One easy approach would adding the values of each character to get a sum and then take a modulo 128. Another way would be using n-degree equation with each character value acting as a co-efficient for the nth term. Example: S[0] * x^n + S[1] * x^(n-1)+ …. + S[n-1], for better result substitute x = 33 or 37 or 39. This is the famous Horner’s method for finding a hash value.
Consider a version of the division method in which h(k) = k mod m, where m = 2p - 1 and k is a character string interpreted in radix 2p. Show that if string x can be derived from string y by permuting its characters, then x and y hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.
有一个很简单的数论知识.先举个例子
3 * 128^3 mod 127 = 3 * 128^2 * (128 mod 127) mod 127 = 3 * 128^2 mod 127 = 3 mod 127 = 3
无论怎么交换字符串的order,radix的影响都会消失. 因为2p^n mod 2p-1 === 1.
Consider a hash table of size m = 1000 and a corresponding hash function h(k) = ⌊m(k A mod 1)⌋ for   . Compute the locations to which the keys 61, 62, 63, 64, and 65 are mapped.
| key | value |
|---|---|
| 61 | 700 |
| 62 | 318 |
| 63 | 936 |
| 64 | 554 |
| 65 | 172 |
Define a family
of hash functions from a finite set U to a finite set B to be ϵ-universal if for all pairs of distinct elements k and l in U,
 = h(l)\} \le \epsilon)
where the probability is over the choice of the hash function h drawn at random from the family . Show that an ϵ-universal family of hash functions must have
UNSOLVED
Let U be the set of n-tuples of values drawn from Zp, and let B = Zp, where p is prime. Define the hash function hb : U → B for b in Zp on an input n-tuple [a0, a1, ..., an-1] from U as
 = \sum_{j=0}^{n-1} a_j b^j})
and let H={hb:b∈Zp}. Argue that H is ((n−1)/p)-universal according to the definition of ϵ-universal in Exercise 11.3-5. (Hint: See Exercise 31.4-4.)
UNSOLVED
Follow @louis1992 on github to help finish this task.