Week 3: Hashing Flashcards
What are the different implementations of a Dictionary ADT in Java? What are the time complexities for their:
get(key)
put(key, data)
remove(key)
What are the design issues with a hash table?
In a hash table, what type are keys allowed to be?
What do hash functions do?
A hash function consists of…
How do you convert a character to an integer?
What is an example of bad hash code?
What is polynomial hash code?
What does a function with polynomial hash code look like? What is Horner’s rule?
\
What is the algorithm for computing the hash using a polynomial hash code and Horner’s rule?
What is separate chaining with regards to collision resolution?
What is the algorithm for the get(key) method using this approach?
What is the time complexity?
Drawbacks of this approach?
Seperate chaining uses an array containing linked lists at each possible index, it then iterates over the linked list at an index for the specific key.
Time complexity is O(n) for bad hash function
Time complexity is O(n/M) = O(1) for good hash function, where M>=n
What is Open Addressing with regards to collision resolution?
What is the algorithm for the get(key) method using this approach?
What is the time complexity?
Drawbacks of this approach?
What happens in this technique when an element is deleted?
Uses Linear Probing to fill next available empty spaces when collision occurs.
Time complexity is O(n)
When an element is removed/deleted, the array at that index is filled with “deleted” keyword to avoid returning NULL which is what is there when the list is first empty (when there are no elements with that hash key)
Linear Probing: a technique used in open addressing to find the next suitable position in a table
What is Double Hashing with regards to collision resolution?
What is the time complexity?
Drawbacks of this approach?
Double hashing: use another hash function in order to compute an OFFSET from the original hash.
Both the q value and the M value must be prime numbers
What is the algorithm for the Open Addressing put() method?
What is the algorithm for the Open Addressing’s put() method using double hashing?
What are the average time complexities of Linear probing, double hashing, and seperate chaining?
What are the use-case scenarios for each?
