A Hash table is a data structure that accesses data stored in memory based on a Key. That is, it accesses records by computing a function on key values that maps the data for the desired query to a location in the table, which speeds up lookups. This mapping function is called a hash function, and the array of records is called a hash table
Hash indicates intent
- On the left is what we’re dealing with
- In the middle is the hash function, which generates an index based on the key that’s passed in
- On the right is an array calledHash table, which is used to store content. The index generated by the hash function is the index stored in the hash table (When you query the index, you can quickly find it)
-
When the index generated by the hash function is repeated, it is called a hash collision. So the quality of the hash function determines the quality of the hash table.
-
When a hash conflict occurs, the hash table does not simply store keys at the index. Instead, a linked list is created in the index (zipper operation), and keys are successively stored in the linked list. Since the query time complexity of linked lists is O(n), the query time complexity of hash tables is O(n) in the worst case.
The time complexity of a hash table
| / | Query (best) | Insert (optimal) | Delete (optimal) | Query (worst) | Insert (worst) | Delete (worst) |
|---|---|---|---|---|---|---|
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
The relationship of hash tables to other data structures
Hash tables are used at the bottom of many data structures, such as Maps and Dictionaries in Java
Reference code
Finally, there is a personal implementation of the code, interested can refer to
List: shimo. Im/docs/D8GPdT…
Hash table: shimo. Im /docs/Gdjg3C…