Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 46
Текст из файла (страница 46)
Use the upper bounds given by Theorems 11.6 and 11.8 forthese expected numbers of probes.11.5Perfect hashingAlthough hashing is most often used for its excellent expected performance, hashing can beused to obtain excellent worst-case performance when the set of keys is static: once the keysare stored in the table, the set of keys never changes. Some applications naturally have staticsets of keys: consider the set of reserved words in a programming language, or the set of filenames on a CD-ROM. We call a hashing technique perfect hashing if the worst-case numberof memory accesses required to perform a search is O(1).The basic idea to create a perfect hashing scheme is simple.
We use a two-level hashingscheme with universal hashing at each level. Figure 11.6 illustrates the approach.Figure 11.6: Using perfect hashing to store the set K = {10, 22, 37, 40, 60, 70, 75}. The outerhash function is h(k) = ((ak + b) mod p) mod m, where a = 3, b = 42, p = 101, and m = 9. Forexample, h(75) = 2, so key 75 hashes to slot 2 of table T . A secondary hash table Sj stores allkeys hashing to slot j .
The size of hash table Sj is mj , and the associated hash function is hj(k) = ((aj k + bj) mod p) mod mj. Since h2(75) = 1, key 75 is stored in slot 1 of secondary hashtable S2. There are no collisions in any of the secondary hash tables, and so searching takesconstant time in the worst case.The first level is essentially the same as for hashing with chaining: the n keys are hashed intom slots using a hash function h carefully selected from a family of universal hash functions.Instead of making a list of the keys hashing to slot j, however, we use a small secondary hashtable Sj with an associated hash function hj.
By choosing the hash functions hj carefully, wecan guarantee that there are no collisions at the secondary level.In order to guarantee that there are no collisions at the secondary level, however, we will needto let the size mj of hash table Sj be the square of the number nj of keys hashing to slot j.
Whilehaving such a quadratic dependence of mj on nj may seem likely to cause the overall storagerequirements to be excessive, we shall show that by choosing the first level hash functionwell, the expected total amount of space used is still O(n).We use hash functions chosen from the universal classes of hash functions of Section 11.3.3.The first-level hash function is chosen from the class ℋp,m, where as in Section 11.3.3, p is aprime number greater than any key value. Those keys hashing to slot j are re-hashed into asecondary hash table Sj of size mj using a hash function hj chosen from the class.[1]We shall proceed in two steps.
First, we shall determine how to ensure that the secondarytables have no collisions. Second, we shall show that the expected amount of memory usedoverall—for the primary hash table and all the secondary hash tables—is O(n).Theorem 11.9If we store n keys in a hash table of size m = n2 using a hash function h randomly chosen froma universal class of hash functions, then the probability of there being any collisions is lessthan 1/2.Proof There arepairs of keys that may collide; each pair collides with probability 1/m if h ischosen at random from a universal family ℋ of hash functions. Let X be a random variablethat counts the number of collisions. When m = n2, the expected number of collisions is(Note that this analysis is similar to the analysis of the birthday paradox in Section 5.4.1.)Applying Markov's inequality (C.29), Pr{X ≥ t} ≤ E[X] /t, with t = 1 completes the proof.In the situation described in Theorem 11.9, where m = n2, it follows that a hash function hchosen at random from ℋ is more likely than not to have no collisions.
Given the set K of nkeys to be hashed (remember that K is static), it is thus easy to find a collision-free hashfunction h with a few random trials.When n is large, however, a hash table of size m = n2 is excessive. Therefore, we adopt thetwo-level hashing approach, and we use the approach of Theorem 11.9 only to hash theentries within each slot. An outer, or first-level, hash function h is used to hash the keys intois used tom = n slots.
Then, if nj keys hash to slot j, a secondary hash table Sj of sizeprovide collision-free constant time lookup.We now turn to the issue of ensuring that the overall memory used is O(n). Since the size mjof the jth secondary hash table grows quadratically with the number nj of keys stored, there isa risk that the overall amount of storage could be excessive.If the first-level table size is m = n, then the amount of memory used is O(n) for the primaryhash table, for the storage of the sizes mj of the secondary hash tables, and for the storage ofthe parameters aj and bj defining the secondary hash functions hj drawn from the classofSection 11.3.3 (except when nj = 1 and we use a = b = 0). The following theorem and acorollary provide a bound on the expected combined sizes of all the secondary hash tables.
Asecond corollary bounds the probability that the combined size of all the secondary hashtables is superlinear.Theorem 11.10If we store n keys in a hash table of size m = n using a hash function h randomly chosen froma universal class of hash functions, thenwhere nj is the number of keys hashing to slot j.Proof We start with the following identity, which holds for any nonnegative integer a:(11.6)We haveTo evaluate the summation, we observe that it is just the total number of collisions.By the properties of universal hashing, the expected value of this summation is at mostsince m = n.
Thus,Corollary 11.11If we store n keys in a hash table of size m = n using a hash function h randomly chosen froma universal class of hash functions and we set the size of each secondary hash table tofor j = 0, 1, ..., m - 1, then the expected amount of storage required for all secondary hashtables in a perfect hashing scheme is less than 2n.Proof Sincefor j = 0, 1, ..., m - 1, Theorem 11.10 gives(11.7)which completes the proof.Corollary 11.12If we store n keys in a hash table of size m = n using a hash function h randomly chosen froma universal class of hash functions and we set the size of each secondary hash table tofor j = 0, 1, ..., m - 1, then the probability that the total storage used for secondary hash tablesexceeds 4n is less than 1/2.Proof Again we apply Markov's inequality (C.29), Pr {X ≥ t} ≤ E [X] /t, this time to inequality(11.7), withand t = 4n:From Corollary 11.12, we see that testing a few randomly chosen hash functions from theuniversal family will quickly yield one that uses a reasonable amount of storage.Exercises 11.5-1: ⋆Suppose that we insert n keys into a hash table of size m using open addressing and uniformhashing.
Let p(n, m) be the probability that no collisions occur. Show that p(n, m) ≤ e-n(n-1)/2m.(Hint: See equation (3.11).) Argue that when n exceeds , the probability of avoidingcollisions goes rapidly to zero.Problems 11-1: Longest-probe bound for hashingA hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used forcollision resolution.a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ithinsertion requires strictly more than k probes is at most 2-k.b.
Show that for i = 1, 2, ..., n, the probability that the ith insertion requires more than 2lg n probes is at most 1/n2.Let the random variable Xi denote the number of probes required by the ith insertion. Youhave shown in part (b) that Pr {Xi > 2lg n} ≤ 1/n2. Let the random variable X = max1≤i≤n Xidenote the maximum number of probes required by any of the n insertions.c. Show that Pr{X > 2lg n} ≤ 1/n.d. Show that the expected length E[X] of the longest probe sequence is O(lg n).Problems 11-2: Slot-size bound for chainingSuppose that we have a hash table with n slots, with collisions resolved by chaining, andsuppose that n keys are inserted into the table.
Each key is equally likely to be hashed to eachslot. Let M be the maximum number of keys in any slot after all the keys have been inserted.Your mission is to prove an O(lg n/lg lg n) upper bound on E[M], the expected value of M.a. Argue that the probability Qk that exactly k keys hash to a particular slot is given byb.
Let Pk be the probability that M = k, that is, the probability that the slot containing themost keys contains k keys. Show that Pk ≤ nQk.c. Use Stirling's approximation, equation (3.17), to show that Qk < ek/kk.d. Show that there exists a constant c > 1 such thatfor k0 = clg n/ lg lg n.2<Conclude that Pk < 1/n for k ≥ k0 = c lg n/ lg lg n.e.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
