Hash Tables Flashcards
Purpose
Way of storing data to be retrieved with a constant time complexity of O(1).
Purpose
Way of storing data to be retrieved with a constant time complexity of O(1).
Hashing algorithm definition
Takes an input and returns a hash.
What is a hash?
Unique to its input and cannot be reversed to retrieve the input value.
Hashing algorithm example
Value
What is returned for each input?
The same hash is always returned for each input.
What do hash tables store?
A value alongside a key.
What happens when a value is inserted into a hash table?
The value is hashed to produce a key. The value is then stored in the table alongside its key.
What happens when a value is to be looked up in a hash table?
It is first hashed - after the hash is calculated, the position in the table corresponding to that hash is queried and the desired information is located.
What is a collision?
When different inputs produce the same hash.
What can a collision lead to?
Data being overwritten in a hash table in a poorly designed system.
How do well designed hash tables get around collisions?
Rehashing (finding an available position according to an agreed position).
What is rehashing?
finding an available position according to an agreed position.
What is an example of a rehashing technique?
Keep moving to the next position until an available one is found.
Hashing algorithm definition
Takes an input and returns a hash.
