Hash

Introduction

A hash table is a data structure that carries out associative array abstract type, it is a structure that can map keys to values. A hash table uses a hash function to compute hash codes, also known as an index into an array of buckets or slots, from which the needed values can be found.

Source: eduCBA

Recommended Topic - hash function in data structure

MCQs

Q1. What is a hash function?

a. A function that creates an array

b. It is a function that computes the location of the key in an array

c. It is a function that has allocated memory to keys

d. It is a function that computes the location of the values in an array

Ans: b

In a hash table, array positions are less than keys, so the position in an array must be computed using the hash function.

Q2. Which of the following statements about hash functions is true?

1. A hash function takes a random length and generates a fixed-length code
2. A hash function may give the same hash values for random messages.
3. A hash function takes a fixed-sized message and generates a code of variable length.

a. I only

b. I and III only

c. I and II only

d. II only

Ans: b

The hash function is a function that can be used to map data of the random size of data to fixed-size data. The values that the hash function returns are called hash values, digest, etc. A hash function may map a value to the same location in memory due to which collision occurs; therefore, statement I is correct. Statement II is also accurate because no matter what, the value of the hash function results in a fixed mapping location; according to this statement, the hash function can result in the same mapping location for different values, although collision occurs.

Q3. An advantage of external hashing(chained hash table) as compared to an open addressing scheme is :

a. Less space is used

b. Worst-case complexity is less of the search operation

c. Deletion is easier

d. None of the above

Ans: c

In an open addressing scheme, sometimes, if an empty bucket comes in between while searching the element, we cannot delete it even if that element is present, while external hashing is free from all these limitations.

Q4. A hash table contains ten buckets and uses linear probing to resolve collisions. The key values are integer, and the hash function used is key % 10. If the values 43,165,62,123,142 are inserted in a table, in which location key value 142 should be inserted? (GATE 2005)

a. 2

b. 3

c. 4

d. 6

Ans:  d

Here, 43 ->3, 

165 ->5,

 62 ->2, 

123 -> 3, but here 3 is already occupied, so according to linear probing 3+1 = 4, 

142 -> 2 is occupied 3 is occupied 4 is also occupied 5; therefore, 6 is the answer.

Q5. A hash function is h(key)= key mod 7, with linear probing is used to insert the keys indexed from 0 to 6 in the table; keys are 44,45,79,55,91,18,63. The location of key 18 will be?

a. 3

b. 4

c. 6

d. 5

Ans: d

Here, h(k)= k mod 7

h(44)= 44 mod 7 = 2

h(45) = 45 mod 7 = 3

h(79) = 79 mod 7 = 2 but 2 is already occupied by 44, therefore according to linear probation it will go to 3 but 3 is also occupied, so it will occupy 4.

h(55)= 55 mod 7 = 6

h(91)= 91 mod 7= 0

h(18) = 18 mod 7= 4 but is occupied so it will occupy 5 therefore 5 is the answer.

Q6. A hash table H has 25 slots which store 2000 elements; load factor α for H is :

a. 8000

b. 80

c. 1,25

d. 0.0125

Ans:  b

Formula for load factor is number of elements / number of table slots 

So, 2000/25 = 80,option b is correct.

Q7. A hash table contains 13 elements for which f(k)=k mod 13 is used with integer keys. For collision resolution, linear probing is used. At which location the key 103 would be inserted if the keys 661,182,24 and 103 are inserted in that order?

a.11

b.12

c. 0

d. 1

Ans: d

Here, 661 mod 13 = 11

182 mod 13 = 0

24 mod 13 = 11, but 11 is already filled; according to linear probing, it will become 12

103 mod 13 = 12, but 12 is already occupied, so it will become 1.

Q8. A hash table size of 20 distributes keys uniformly. After hashing, what is the probability that any new key hashed collides with an existing one that exceeds 0.5?

a. 7

b. 6

c. 5

d. 10

Ans: d

The probability of collision for each entry is 1/20; let's say after inserting x values probability becomes ½

(1/20)x= ½

x = 10. 

Q9. What is the search complexity in simple uniform hashing?

a. O(nlogn)

b. O(n)

c. O(1)

d. O(logn)

Ans: c

For successful search as well as unsuccessful search, the complexity is O(1 + alpha), where 1 is for computing the hash function, and alpha is the load factor.

Q10. In the direct addressing table, the time complexity to delete an element is:

a. O(n)

b. O(1)

c. O(nlogn)

d. O(logn)

Ans: b

In the direct addressing table, every key has a unique array position for deleting an element; constant time is required, despite the fact that deleted positions are specified by nil.