A hash map (also known as a hash table) is a data structure that stores key-value pairs, allowing for efficient data retrieval based on keys. It is widely used for fast lookups, insertions, and deletions.
Key Concepts of a Hash Map:
-
Key-Value Pair: Each element in a hash map is stored as a pair, consisting of a key and a value. The key is unique, and it is used to access the corresponding value.
-
Hash Function: A hash function is used to convert the key into a hash code (an integer). This hash code determines where the key-value pair should be stored in the map (its index).
-
Buckets/Slots: The hash map uses an array of “buckets” or “slots” to store the key-value pairs. The hash code determines which bucket the data goes into. Ideally, each key gets mapped to a unique bucket.
-
Collision Handling: Sometimes two keys may produce the same hash code (known as a collision). There are various strategies to handle this:
- Chaining: Store multiple key-value pairs in the same bucket using a linked list or another data structure.
- Open Addressing: Find another empty slot in the array when a collision occurs (linear probing, quadratic probing, etc.).
-
Time Complexity:
- Lookups (searching for a key): On average, this is O(1) (constant time), meaning that it’s extremely fast.
- Insertions: On average, this is also O(1).
- Deletions: On average, O(1) as well.
Example in Dart (Using Map
):
In Dart, the Map
class is an implementation of a hash map. Here’s a simple example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void main() { // Creating a hash map in Dart (Map) Map<String, int> ageMap = { 'Alice': 25, 'Bob': 30, 'Charlie': 22, }; // Accessing value using a key print('Alice\'s age: ${ageMap['Alice']}'); // Output: Alice's age: 25 // Adding a new key-value pair ageMap['David'] = 28; // Removing a key-value pair ageMap.remove('Bob'); // Checking if a key exists if (ageMap.containsKey('Charlie')) { print('Charlie\'s age: ${ageMap['Charlie']}'); // Output: Charlie's age: 22 } } |
Key Features of a Hash Map:
- Fast Access: Hash maps provide constant-time access to data in ideal conditions.
- Dynamic Size: They can resize dynamically as the number of key-value pairs grows, although this may incur occasional performance overhead (when resizing occurs).
- Unordered: The order of key-value pairs is not guaranteed; the internal order is based on the hash codes.
Use Cases:
- Dictionary-like structures: Storing and retrieving items by key.
- Counting occurrences: Hash maps are often used for counting occurrences of items (e.g., words in a document).
- Caching: Quick lookup of previously computed results.
Limitations:
- Hash Collisions: Although hash maps are designed to handle collisions, poor hash functions or excessive collisions can degrade performance.
- Memory Overhead: Hash maps can consume more memory than other data structures like arrays or lists due to internal structures (e.g., linked lists in chaining).
In summary, a hash map is an efficient and widely used data structure for storing and retrieving key-value pairs quickly, with average time complexities of O(1) for most operations.