Hash Table: Difference between revisions
Jump to navigation
Jump to search
Created page with "An hash table is a key-value data structure. 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 cod..." |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| 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. | ||
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 | 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. | The purpose of hash-table to provide a constant-time for insertion, find, or delete operations. | ||
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 |