week 8 must recap before exam

Question 1

linear probing

Answer 1

h’(x) = [ h(x) + i ] % N N - size i= 1,2,3 … N-1 (iterate when theres is a collision increasing value of i until you reach an empty cell)

Question 2

chaining

Answer 2

uses link lists

Question 3

hash function

Answer 3

h(k) = K Mod N ( k- value of key) and N - size

N is preferably prime to reduce likelihood of collision

Question 4

MAD hash function

Answer 4

((ay+b) ModP ) Mod N

N - size and prefrably prime
p - prime greater than n
a and b - random integers [0, p-1] a > 0

Question 5

In worst case search , insertions, removals on a hashtable is o(n) everything collides ( chaining where linked list is best example if everything collides you would have to traverse across every element in linked list

Question 6

double hashing

Answer 6

h(k) = K Mod N
h’(k) = q - k Mod q

Q should be a prime less than N

if collision :
A[ ((h(k) + j x h’(k) ) Mod N ]

Question 7

load factor alpha

Answer 7

m / N gives expected keys per slot

m - the no of keys
N - the size of the array

if load factor is close 100 percent

m ( no of keys )is approximately N

hashing will be slow

Question 8

how to keep load factor small

Answer 8

Keeping the load factor down
 To keep hashing performance up, we need to
keep the load factor a down
 We use rehashing to do so:
 Whenever load factor becomes too large (e.g., >
0.5)
 Create new bucket array approx. double the size
of the old one
 Iterate all elements in the old bucket array and
use put to add them to the new bucket array