Hashing

Which data structure uses hashing to store information with constant lookup time?

• Hash table
• 1D Array
• Linked List
• 2D Array
• Stack

What is the load factor?

• Average array size

• Average key size

• Average chain length

• Average hash table length

In simple chaining, what data structure is appropriate?

• Singly linked list

• Doubly linked list

• Circular linked list

• Binary trees

The case in which a key other than the desired one is kept at the identified location is called?

• Hashing

• Collision

• Chaining

• Open addressing

Which of the following is not a collision resolution technique?

• Separate chaining

• Linear probing

• Quadratic probing

• Hashing

Hashing is not the problem of finding an appropriate mapping of keys into addresses.

• True

• False

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown above.

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

• 46, 42, 34, 52, 23, 33

• 34, 42, 23, 52, 33, 46

• 46, 34, 42, 23, 52, 33

• 42, 46, 33, 23, 34, 52

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

• h(i) =i^2 mod 10

• h(i) =i^3 mod 10

• h(i) = (11 ∗ i^2) mod 10

• h(i) = (12 ∗ i) mod 10

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i. 9679, 1989, 4199 hash to the same value

ii. 1471, 6171 has to the same value

iii. All elements hash to the same value

iv. Each element hashes to a different value

• i only

• ii only

• i and ii only

• iii or iv

What is the worst case search time of a hashing using separate chaining algorithm?

• O(N log N)

• O(N)

• O(N^2)

• O(N^3)