Hash functions: Assume that you are hashing key K to a hash table of n slots (in

Question

Hash functions: Assume that you are hashing key K to a hash table of n slots (indexed from 0 to n - 1). For each of the following functions h(K) is the function acceptable as a hash function (i e, would the hash program work correctly for both insertions and searches), and if so, is it a good hash function? Function Random (n) returns a random integer between 0 and n - 1, inclusive. H(K) = k/n where k and n are integers h(K) = 1 h(K) = (k + Random(n)) mod n. h(K) = k mod n where n is a prime number.

Explanation / Answer

a hash function that maps each item into a unique slot is referred to as a perfect hash function.

For example:

insert(1, 20);

   insert(2, 70);

   insert(42, 80);

   insert(4, 25);

   insert(12, 44);

   insert(14, 32);

   insert(17, 11);

   insert(13, 78);

   insert(37, 97);

if you insert this elements in hash table by using different keys

If h(k)=key/ n than elements insertion

d)

If h(k)=key mod n than elements insertion

~~ (1,20) (2,70) (42,80) (4,25) ~~ ~~ ~~ ~~ ~~ ~~ ~~ (12,44) (13,78) (14,32) ~~ ~~ (17,11) (37,97) ~~

If h(k)=1 than elements insertion

c)If h(k)=(k+random(n)) mod n than elements insertion

h(k)=key/ n is best hash function.

In all the If h(k)=key/ n than elements insertion is best this all are in sequence. without gaps

All these needs best search time. because all are in sequence this all load factor is good

Load factor=

Search:

Insert:

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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