Hash Table: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
An hash table is a key-value data structure. | An hash table is a key-value data structure whose main purpose is highly-efficient lookup. | ||
From the key, we derive a hash code and from a hash code an index that points to the value. | From the key, we derive a hash code and from a hash code an index that points to the value. | ||
Latest revision as of 16:49, 2 October 2020
An hash table is a key-value data structure whose main purpose is highly-efficient lookup.
From the key, we derive a hash code and from a hash code an index that points to the value.
When two value has the same hash code or index, there is a collision. One of the solution to fix a collision is chaining. For the same hash code or index, a chain of values is mapped.
There is multiple ways to chain values:
- linked list: the most common, the worst case lookup is O(n)
- binary search tree: rarely used except for non-uniform distribution, the worst case lookup is O(log(n))
- open addressing with linear probing: look for the next available spot in the table, sometimes at fixed offset; fast and space-efficient, but can cause clustering issue (when there is no available spot)
- quadratic probing with double hashing
The purpose of hash-table to provide a constant-time for insertion, find, or delete operations.
Resources
| https://www.youtube.com/watch?v=shs0KM3wKv8 |