ch 5 hashtables Flashcards
key
what a search is performed on
hash function
what is applied to a key, determines where the key is applied
should avoid collisions
separate chaining
keep a list of all elements that hash to the same value
disadvantage because it uses linked lists
linear probing
primary clustering
tries cells sequentially, wraps around
keys start clustering in one area, slows down algorithm
quadratic probing
first try 1^2 away
if not, try 2^2 away
table size must be prime (table size * 2 up to the next prime)
you always start from the original index
secondary clustering, everything hashes to the same element
reshashing
if table gets too full, double table size
dont add deleted elements
rehash values with the new table size (dont put them in the same index)
deletion
have to use lazy deletion
boolean thats true or false when you delete
delete min
very rightmost element goes into the hole
that element gets percolated down until it cant get moved any further
minheap properties
complete
top is smaller