Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 44
Текст из файла (страница 44)
By linearity of expectation, therefore, the expected timefor the entire sequence of operations is O(n).Designing a universal class of hash functionsIt is quite easy to design a universal class of hash functions, as a little number theory will helpus prove. You may wish to consult Chapter 31 first if you are unfamiliar with number theory.We begin by choosing a prime number p large enough so that every possible key k is in therange 0 to p - 1, inclusive. Let Zp denote the set {0, 1, ..., p - 1}, and let denote the set {1, 2,..., p - 1}.
Since p is prime, we can solve equations modulo p with the methods given inChapter 31. Because we assume that the size of the universe of keys is greater than thenumber of slots in the hash table, we hav p > m.We now define the hash function ha,b for anyand any b Zp using a lineartransformation followed by reductions modulo p and then modulo m:(11.3)For example, with p = 17 and m = 6, we have h3,4(8) = 5. The family of all such hashfunctions is(11.4)Each hash function ha,b maps Zp to Zm. This class of hash functions has the nice property thatthe size m of the output range is arbitrary—not necessarily prime—a feature which we shalluse in Section 11.5.
Since there are p - 1 choices for a and there are p choices for b, there arep(p - 1) hash functions in ℋp,m.Theorem 11.5The class ℋp,m of hash functions defined by equations (11.3) and (11.4) is universal.Proof Consider two distinct keys k and l from Zp, so that k ≠ l. For a given hash function ha,bwe letr = (ak + b) mod p,s = (al + b) mod p.We first note that r ≠ s. Why? Observe thatr - s ≡ a(k - l) (mod p).It follows that r ≠ s because p is prime and both a and (k - l) are nonzero modulo p, and sotheir product must also be nonzero modulo p by Theorem 31.6.
Therefore, during thecomputation of any ha,b in ℋp,m, distinct inputs k and l map to distinct values r and s modulop; there are no collisions yet at the "mod p level." Moreover, each of the possible p(p - 1)choices for the pair (a, b) with a ≠ 0 yields a different resulting pair (r, s) with r ≠ s, since wecan solve for a and b given r and s:a = ((r - s)((k - l)-1 mod p)) mod p,b = (r - ak) mod p,where ((k - l)-1 mod p) denotes the unique multiplicative inverse, modulo p, of k - l. Sincethere are only p(p - 1) possible pairs (r, s) with r ≠ s, there is a one-to-one correspondencebetween pairs (a, b) with a ≠ = 0 and pairs (r, s) with r ≠ s. Thus, for any given pair of inputsk and l, if we pick (a, b) uniformly at random from, the resulting pair (r, s) is equallylikely to be any pair of distinct values modulo p.It then follows that the probability that distinct keys k and l collide is equal to the probabilitythat r ≡ s (mod m) when r and s are randomly chosen as distinct values modulo p.
For a givenvalue of r, of the p - 1 possible remaining values for s, the number of values s such that s ≠ rand s ≡ r (mod m) is at most⌈p/m⌉ - 1 ≤ ((p + m - 1)/m) - 1 (by inequality (3.7))= (p - 1)/m.The probability that s collides with r when reduced modulo m is at most ((p - 1)/m)/(p - 1) =1/m.Therefore, for any pair of distinct values k, lZp,Pr{ha,b(k) = ha,b(l)} ≤ 1/m,so that ℋp,m is indeed universal.Exercises 11.3-1Suppose we wish to search a linked list of length n, where each element contains a key kalong with a hash value h(k). Each key is a long character string. How might we takeadvantage of the hash values when searching the list for an element with a given key?Exercises 11.3-2Suppose that a string of r characters is hashed into m slots by treating it as a radix-128 numberand then using the division method.
The number m is easily represented as a 32-bit computerword, but the string of r characters, treated as a radix-128 number, takes many words. Howcan we apply the division method to compute the hash value of the character string withoutusing more than a constant number of words of storage outside the string itself?Exercises 11.3-3Consider a version of the division method in which h(k) = k mod m, where m = 2p - 1 and k isa character string interpreted in radix 2p. Show that if string x can be derived from string y bypermuting its characters, then x and y hash to the same value. Give an example of anapplication in which this property would be undesirable in a hash function.Exercises 11.3-4Consider a hash table of size m = 1000 and a corresponding hash function h(k) = ⌊m(k A mod1)⌋ formapped.. Compute the locations to which the keys 61, 62, 63, 64, and 65 areExercises 11.3-5: ⋆Define a family ℋ of hash functions from a finite set U to a finite set B to befor all pairs of distinct elements k and l in U,Pr {h(k) = h(l)} ≤-universal if,where the probability is taken over the drawing of hash function h at random from the familyℋ.
Show that an-universal family of hash functions must haveExercises 11.3-6: ⋆Let U be the set of n-tuples of values drawn from Zp, and let B = Zp, where p is prime. Definethe hash function hb : U → B for b Zp on an input n-tuple a0, a1, ..., an-1 from U asand let ℋ = {hb : b Zp}. Argue that ℋ is ((n - 1)/p)-universal according to the definition of-universal in Exercise 11.3-5. (Hint: See Exercise 31.4-4.)11.4 Open addressingIn open addressing, all elements are stored in the hash table itself.
That is, each table entrycontains either an element of the dynamic set or NIL. When searching for an element, wesystematically examine table slots until the desired element is found or it is clear that theelement is not in the table. There are no lists and no elements stored outside the table, as thereare in chaining. Thus, in open addressing, the hash table can "fill up" so that no furtherinsertions can be made; the load factor α can never exceed 1.Of course, we could store the linked lists for chaining inside the hash table, in the otherwiseunused hash-table slots (see Exercise 11.2-4), but the advantage of open addressing is that itavoids pointers altogether. Instead of following pointers, we compute the sequence of slots tobe examined.
The extra memory freed by not storing pointers provides the hash table with alarger number of slots for the same amount of memory, potentially yielding fewer collisionsand faster retrieval.To perform insertion using open addressing, we successively examine, or probe, the hashtable until we find an empty slot in which to put the key. Instead of being fixed in the order 0,1, ..., m - 1 (which requires Θ(n) search time), the sequence of positions probed depends uponthe key being inserted.
To determine which slots to probe, we extend the hash function toinclude the probe number (starting from 0) as a second input. Thus, the hash functionbecomesh : U × {0, 1, ..., m - 1} → {0, 1, ..., m - 1}.With open addressing, we require that for every key k, the probe sequenceh(k,0),h(k,1), ..., h(k,m - 1)be a permutation of 0, 1, ..., m -1 , so that every hash-table position is eventuallyconsidered as a slot for a new key as the table fills up. In the following pseudocode, weassume that the elements in the hash table T are keys with no satellite information; the key k isidentical to the element containing key k. Each slot contains either a key or NIL (if the slot isempty).HASH-INSERT(T, k)1 i ← 02 repeat j ← h(k, i)3if T[j] = NIL4then T[j] ← k5return j6else i ← i + 17until i = m8 error "hash table overflow"The algorithm for searching for key k probes the same sequence of slots that the insertionalgorithm examined when key k was inserted.
Therefore, the search can terminate(unsuccessfully) when it finds an empty slot, since k would have been inserted there and notlater in its probe sequence. (This argument assumes that keys are not deleted from the hashtable.) The procedure HASH-SEARCH takes as input a hash table T and a key k, returning j ifslot j is found to contain key k, or NIL if key k is not present in table T.HASH-SEARCH(T, k)1 i ← 02 repeat j ← h(k, i)3if T[j] = k4then return j5i ← i + 16until T[j] = NIL or i = m7return NILDeletion from an open-address hash table is difficult. When we delete a key from slot i, wecannot simply mark that slot as empty by storing NIL in it.
Doing so might make it impossibleto retrieve any key k during whose insertion we had probed slot i and found it occupied. Onesolution is to mark the slot by storing in it the special value DELETED instead of NIL. Wewould then modify the procedure HASH-INSERT to treat such a slot as if it were empty sothat a new key can be inserted. No modification of HASH-SEARCH is needed, since it willpass over DELETED values while searching. When we use the special value DELETED,however, search times are no longer dependent on the load factor α, and for this reasonchaining is more commonly selected as a collision resolution technique when keys must bedeleted.In our analysis, we make the assumption of uniform hashing: we assume that each key isequally likely to have any of the m! permutations of 0, 1, ..., m - 1 as its probe sequence.Uniform hashing generalizes the notion of simple uniform hashing defined earlier to thesituation in which the hash function produces not just a single number, but a whole probesequence.
True uniform hashing is difficult to implement, however, and in practice suitableapproximations (such as double hashing, defined below) are used.Three techniques are commonly used to compute the probe sequences required for openaddressing: linear probing, quadratic probing, and double hashing. These techniques allguarantee that h(k, 0), h(k, 1), ..., h(k, m - 1) is a permutation of 0, 1, ..., m - 1 for eachkey k. None of these techniques fulfills the assumption of uniform hashing, however, sincenone of them is capable of generating more than m2 different probe sequences (instead of them! that uniform hashing requires). Double hashing has the greatest number of probesequences and, as one might expect, seems to give the best results.Linear probingGiven an ordinary hash function h' : U → {0, 1, ..., m - 1}, which we refer to as an auxiliaryhash function, the method of linear probing uses the hash functionh(k, i) = (h'(k) + i) mod mfor i = 0, 1, ..., m - 1. Given key k, the first slot probed is T[h'(k)], i.e., the slot given by theauxiliary hash function.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
