Hashing

Question 1

worst case performance of hash search

Answer 1

Worst case:
T(n) = time hash + time linear search
T(n) = 0(1) + O(n)
T(n) = O(n)

Question 2

base case performance of hash search

Answer 2

Best case:
T(n) = time hash + time retrieve element
T(n) = 0(1) + O(1)
T(n) = O(1)

Question 3

Open addressing techniques

Answer 3

Linear Probing: If position h(key) is occupied, do a linear search in the table until you find a empty slot.
Quadratic probing: is a variant of the above where the term being added to the hash result is squared. h(key)+c2
Random probing: is another variant where the term being added to the hash function is a random number. h(key)+random()
Rehashing: is a technique where a sequence of hashing functions are defined
(h1, h2, … hk). If a collision occurs the functions are used in the this order

Question 4

Separate chaining techniques

Answer 4

The most common resolution mechanism is called separate chaining or just chaining,
It consists of mixing the concepts of linked lists and direct access structures like arrays
Each slot of a hash table is a pointer to a dynamic structure (say a linked list or a binary search tree)