ch 5 hashtables Flashcards

1
Q

key

A

what a search is performed on

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

hash function

A

what is applied to a key, determines where the key is applied
should avoid collisions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

separate chaining

A

keep a list of all elements that hash to the same value

disadvantage because it uses linked lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

linear probing

primary clustering

A

tries cells sequentially, wraps around

keys start clustering in one area, slows down algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

quadratic probing

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

reshashing

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

deletion

A

have to use lazy deletion

boolean thats true or false when you delete

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

delete min

A

very rightmost element goes into the hole

that element gets percolated down until it cant get moved any further

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

minheap properties

A

complete

top is smaller

How well did you know this?
1
Not at all
2
3
4
5
Perfectly