hash tables

Question 1

what is a hash table

Answer 1

data structure where items are stored in a location determined by their content - content based inde

Question 2

what is every hash table fundamentally composed of?

Answer 2

array of items

hash function: that converts item to an index

Question 3

what is a hash function

Answer 3

is a mapping from an item to an integer

Question 4

what are the requirements for a good hash function?

Answer 4

fast compute
deterministic
spread keys evenly in hash table - no large gaps

Question 5

what is a perfect has function

Answer 5

maps an every distinct key onto a distinct integer

minimal perfect hash function has no holes in the array

Question 6

how are collisions addressed?

Answer 6

open addressing - linear and quadratic probing

closed addressing - chaining

Question 7

explain linear probing insert

Answer 7

generate hash code = h

while A[h] contains a key A[h] - {key, value}

Question 8

explain linear probing find

Answer 8

generate hash code = h
while A[h] contains a key:
-- if A[h]{key} == key  return value
-- h = (h+1)%table size
return not found

Question 9

issues with linear probing

Answer 9

• primary clustering - multiple adjacent items and slow performance
• uneven gaps in the table
• full table

Question 10

what to do when the table becomes full?

Answer 10

throw an error
create new and larger table
automatically make a larger array and then rehash every thing

Question 11

what is the load factor

Answer 11

the proportion of the table that is fill (λ)

Question 12

probability of a cell being empty

Answer 12

1 - load factor (lambda)

1-λ

Question 13

average number of cells to be examined for insert

Answer 13

T(λ) = (1+1/(1-λ)^2)/2

Question 14

average number of cells to be examined for successful find

Answer 14

T(λ) = (1+1/(1-λ))/2

Question 15

quadratic probing insert

Answer 15

generate hash code h = hash(key), i =1
while a[h] contains a key
h = h+i*i%table size
a[h] = key, value

Question 16

quadratic probing find

Answer 16

generate hash code h = hash(key), i =1
while a[h] contains a key
-- if A[h]{key} == key  return value
--- h = h+i*i%table size
--- i++

return not found

Question 17

basic idea of collision resolution by chaining

Answer 17

use a table of pointers/references

each new item must be added to a linked list at that position in the table

Question 18

insertion algorithm for chaining

Answer 18

generate hash code h = hash(key), p = new Node
p.data = {key, value}; p.next = A[h]
A[h] = p

Question 19

find algorithm for chaining

Answer 19

generate hash code h = hash(key), p = A[h]
while p != null and p{key} != key
— p = p.next
return p

Question 20

analyze the chaining technique

Answer 20

n items and m table size - even distribution of hash values and use of all possible hash values
on ave each linked list is of size n/m
average search time - 1/2 n/m

Question 21

complexity analysis of chaining

Answer 21

best - O(n/m)
ave - 1/2 n/m
worst - O(n)
m - tablesize
n - number of items

All dependent on choice of M relative to n

Question 22

handling deletions open addressing vs chaining

Answer 22

open addressing:

• deletion not easily possible
• add a flag to mark deleted items - skip deleted items during search, unmark and over write deleted items on insert

chaining:
- use linked list deletions

Question 23

other variations to chaining

Answer 23

double hashing - if there is a collision because of due to secondary clustering use a second hash function when there is a collision
h = H1 +H2 - where H2 is the rehashing function
a different sequence is checked for each key

chaining using BST or other data structures

Question 24

what is secondary clustering?

Answer 24

where a key generates the same sequence of locations to check