mapping adt

Question 1

rehashing with dictionary

Answer 1

O(n);
bucket = hash(key) % m;
-# splits keys into m buckets

Question 2

hash(self, key):

Answer 2

return key % self._n_buckets

Question 3

rehashing

Answer 3

self._n_buckets *= 2;
new_L = [[] for i in range(self,_n_buckets];

for bucket in self._L;
> for entry in bucket:
» new_bucket = self.hash(entry.key);
»new_L[new_bucket].append(entry)

self._L = new_L[:]

Question 4

load factor

Answer 4

entries / table size

Question 5

separate chaining

Answer 5

collisions are resolved by storing all colliding keys in one slot using an ADT like linked list

Question 6

open addressing / closed hashing

Answer 6

collisions are resolved by storing the colliding key in the next best place

Question 7

linear probing

Answer 7

solve hash collision by storing the key in the closest following free location

Question 8

quadratic probing

Answer 8

search for the i^2 bucket in ith iteration

Question 9

double hashing

Answer 9

use a secondary hash function