Test: Hashing - Computer Science Engineering (CSE) MCQ

The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.
The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.
The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.
The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.

For the above hash table to occur, collision occurs for 52 and 33. That means, 42 and 23 must always appear before 52 and 33. Also note that 34 should always come before 52 and 33, else 52 and 33 may occupy 34's place. Therefore 42,23, and 34 should appear before 52 and 33. Hence 42, 23 and 34 can occur in 3! ways.
Now notice that 52 should come before, and finally 46 can appear at 5 different places.

Therefore, total number of different sequences = 3! x 5 = 30

• Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table.
• Well known probe sequences include: linear probing in which the interval between probes is fixed--often at 1. quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function). double hashing in which the interval between probes is fixed for each record but is computed by another hash function.

Let us put values 1, 3, 8, 10 in the hash of size 7. Initially, hash table is empty

The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0

The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6

The value of function (3x + 4)mod 7 for 8 is 0, but 0 is already occupied, let us put the value(8) at next available space(1)

The value of function (3x + 4)mod 7 for 10 is 6, but 6 is already occupied, let us put the value(10) at next available space(2)

Hash function given is mod(10).
9679, 1989 and 4199 all these give same hash value i.e 9.
1471 and 6171 give hash value 1.

Simple Uniform hashing function is a hypothetical hashing function that evenly distributes items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. 

► Probability that the first 3 slots are unfilled after the first 3 insertions =(probability that first item doesn't go in any of the first 3 slots)*
(probability that second item doesn't go in any of the first 3 slots)*
(probability that third item doesn't go in any of the first 3 slots)

= (97/100) * (97/100) * (97/100)

Since mod 10 is used, the last digit matters. If you do cube all numbers from 0 to 9, you get following

Therefore all numbers from 0 to 2020 are equally divided in 10 buckets. If we make a table for square, we don't get equal distribution. In the following table. 1, 4, 6 and 9 are repeated, so these buckets would have more entries and buckets 2, 3, 7 and 8 would be empty.

load factor = (no. of elements) / (no. of table slots) = 2000/25 = 80

Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes  : Statement 1 is correct Yes, it is possible that a Hash Function maps a value to a same location in the memmory that's why collision occurs and we have different technique to handle  this problem : Statement 3 is coorect. eg : we have hash function, h(x) = x mod 3 Acc to Statement 1, no matter what the value of 'x' is h(x) results in a fixed mapping location. Acc. to Statement 3, h(x) can result in same mapping mapping location for different value of 'x' e.g. if x = 4 or x = 7 , h(x) = 1 in both the cases, although collision occurs.

For each entry probability of collision is 1/20 {as possible total spaces = 20, and an entry will go into only 1 place}
Say after inserting x values probability becomes ½
(1/20).x = ½
X = 10