# hash tables Flashcards

what is a hash table

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

what is every hash table fundamentally composed of?

array of items

hash function: that converts item to an index

what is a hash function

is a mapping from an item to an integer

what are the requirements for a good hash function?

fast compute

deterministic

spread keys evenly in hash table - no large gaps

what is a perfect has function

maps an every distinct key onto a distinct integer

minimal perfect hash function has no holes in the array

how are collisions addressed?

open addressing - linear and quadratic probing

closed addressing - chaining

explain linear probing insert

generate hash code = h

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

explain linear probing find

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

issues with linear probing

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

what to do when the table becomes full?

throw an error

create new and larger table

automatically make a larger array and then rehash every thing

what is the load factor

the proportion of the table that is fill (λ)

probability of a cell being empty

1 - load factor (lambda)

1-λ

average number of cells to be examined for insert

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

average number of cells to be examined for successful find

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

quadratic probing insert

generate hash code h = hash(key), i =1

while a[h] contains a key

h = h+i*i%table size

a[h] = key, value