Contents
Hash Tables
Hash Table, Map, HashMap, Dictionary or Associative are all the names of the same data structure. It is a data structure that implements a set abstract data type, a structure that can map keys to values.
Visit the following resources to learn more:
- articleHash Tables and Hashmaps in Python
- articleBuild a Hash Table in Python
- videoHash Table Data Structure | Illustrated Data Structures
| Characteristic | Description |
|---|---|
| Definition | A hash table is a data structure that maps keys to values using a hash function to compute an index into an array of buckets or slots. |
| Hash Function | A function that converts a key into an index for the hash table. It helps in determining where to store the value associated with the key. |
| Collision Handling | Techniques like chaining (using linked lists) or open addressing (probing) are used to handle cases where multiple keys hash to the same index. |
| Access Time | Average-case O(1) for lookups, insertions, and deletions. Performance may degrade to O(n) in worst-case scenarios with poor hash functions or high collision rates. |
| Memory Usage | Hash tables typically use extra memory for the array and pointers (in case of chaining). The memory usage depends on the load factor and hash table size. |
| Dynamic Resizing | Many implementations resize the hash table when the load factor exceeds a threshold to maintain performance. |
| Applications | Used in various applications including caching, indexing, and associative arrays. |
| Python Libraries | Python’s built-in dictionary (dict) is a hash table implementation. Other libraries also provide hash table implementations for specialized use cases. |
Examples of Hash Table Implementations in Python
| Library | Example Usage |
|---|---|
Built-in dict | Python’s built-in dictionary is a hash table implementation. <br> Example: <br> python <br> my_dict = {} <br> my_dict['key'] = 'value' <br> print(my_dict['key']) # Outputs 'value' <br> |
collections.defaultdict | A subclass of the built-in dictionary that returns a default value if a key is not found. <br> Example: <br> python <br> from collections import defaultdict <br> dd = defaultdict(int) <br> dd['key'] += 1 <br> print(dd['key']) # Outputs 1 <br> |
hashlib | Provides hash functions to create hash values but does not directly implement hash tables. <br> Example: <br> python <br> import hashlib <br> hash_value = hashlib.md5(b'key').hexdigest() <br> print(hash_value) <br> |