Searching Flashcards
1
Q
What is a hash table?
A
Data structure that lets us find stored values more efficiently than sequential search O(n) or binary search O(log n) if using indices instead of slicing, which is O(n)
2
Q
What’s a slot in a hash table?
How is it named and what does it hold?
A
each position of a hash table, named by an integer value (starting at 0) - indices of the list
holds an item
3
Q
What maps an item with the slot it’ll be in in the hash table?
A
Hash function
4
Q
What is the load factor?
A
number of items in table / number of slots in the table
5
Q
Name 2 methods for a hash function
A
Remainder method
Folding method
6
Q
Name 2 main collision resolution tactics
A
Open Addressing
Chaining
