Hash Table Flashcards
What is Robin Hood Hash Table main goal?
To scatter the biggest distance elements
What is double hash table?
using two hash functions
What is linear hash table?
inserting elements in linear sequence; when an index is taken, you add one to it and going again
What is open-addressing?
When you directly add to the table; chaining is the opposite of that, because in chaining hash table you insert elements in the same index, but they are chained together
Which implementation is the fastest in hash tables?
chaining
linear
quadric
double
robin hood
cuckoo
Double hash table can be named as the fastest, but they all are very close, especially linear, quadric, double.
Robin Hood supposes to be good when we have big data demand.
What is Cuckoo hash table?
It is a hash table structure which uses two tables, when in the first one index is occupied then it searches for available place in the second table.
Important in this implementation is private function rehash, that rehashes both tables when they are nearly full ( size >= capacity * 0.7).
It is easy to manage.
What is the main reason to use hashing tables?
Search time is O(1), like is also amortized inserting and removing
What is the basic hash?
key modulo capacity
How you will prevent going beyond capacity in a second hash function?
1 + (key % (capacity - 1) → where the key should be the index from first hash
How would you handle the resize/rehash method?
Firstly, I will implement it private. It should have a pointer to old table and old capacity. Next step is to make new table with different capacity, fill it with -1 or NULL it depends. You have to traverse elements from old table to new table with increased or decreased capacity.
