24. Given a set of keys k0, k,, ... k 1,a perfect hashing function hf() is a has

Question

24. Given a set of keys k0, k,, ... k 1,a perfect hashing function hf() is a hash function that produces no collisions. It is not practical to find a perfect hashing function unless the set of keys is static. A situation for which a perfect hash function is desirable is a table of reserved words (such as while, template, and class in C-' +) that a compiler searches. When an identifier is read, only one probe is necessary to determine whether the identifier is a reserved word. It is difficult to find a perfect hash function for a particular set of keys, and a general discussion of the subject is beyond the scope of this book. Furthermore, if a new set of keys is added to the set, the hash function normally is no longer perfect. (a) Consider the set of integer keys 81, 129, 301, 38, 434, 216, 412, 487, 234 and the hashing function hf(x) = (x + 18)/63 Is hf() a perfect hashing function? (b) Consider the set of keys consisting of the strings Bret, Jane, Shirley, Bryce, Michelle, Heather Devise a perfect hash function for a table containing seven elements.

Explanation / Answer

a)

hf(x) is a perfect hashing function.

Because, the key value of each element is different from one another. That means no collision has happened.

The keys of the elements are as follows:

h(81) = (81+18) / 63

           =    99/63

            = 1 (quotient value)

similarly for

hf(129) = 2

hf(301) = 5

hf(38) = 0

hf(434) = 7

hf(216) = 3

hf(412) = 6

hf(487) = 8

hf(234) = 4

Since all key values are different, the hashfunction is perfect hash function.

----------------------------------------------------------------------------------------------------------------------------

b)

The hash function for the reserved(static) words provided in the question is

hf(string) = Ascii value of 3rd character of the string.

The Third character of the strings are as follows:

e (Bret)

n (Jane)

i (Shirley)

y (Bryce)

c (Michelle)

a (Heather)

Since all the characters are different, the hashfunctions works fine for the above static strings.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.