706. Design HashMap

Problem Statement

link: LeetCode.cn LeetCode

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map. void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value. int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example:

Input: ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"][[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] Output: [null, null, null, 1, -1, null, 1, null, -1]

Solution Approach

The solution utilizes an array of linked lists to handle collisions and implements basic hash map operations such as put, get, and remove by computing hash values for keys and storing key-value pairs accordingly.

Algorithm

1. Initialization: The class MyHashMap is initialized with an empty map. It sets up an array of lists, where each index in the array corresponds to a hash value and each list stores key-value pairs that have the same hash value.
2. Hashing Function: Utilizes a hashing function to convert keys into indices within the array. This function distributes keys uniformly across the array, minimizing collisions.
3. Put Operation: Inserts a key-value pair into the HashMap. If the key already exists, it updates the corresponding value. It calculates the hash value of the key and stores the key-value pair in the appropriate list.
4. Get Operation: Retrieves the value associated with a given key. Calculates the hash value of the key to determine the list where the key-value pair might be stored. Searches through the list to find the key and returns its associated value.
5. Remove Operation: Removes a key-value pair from the HashMap. Calculates the hash value of the key to locate the correct list. Searches for the key within the list and removes it if found.
6. Handling Collisions: In case of hash collisions (i.e., multiple keys hash to the same index), the solution uses separate chaining. Each index in the array contains a linked list, allowing multiple key-value pairs with the same hash value to coexist peacefully.
7. Efficiency Considerations: The efficiency of the solution heavily depends on the quality of the hashing function and the load factor. Choosing a good hashing function and managing the load factor ensures balanced performance across different operations.

Implement

    class MyHashMap:

        def __init__(self):
            self.buckets = 1009
            self.table = [[] for _ in range(self.buckets)]
        
        def hash(self, key):
            return key % self.buckets

        def put(self, key: int, value: int) -> None:
            hashkey = self.hash(key)
            for item in self.table[hashkey]:
                if item[0] == key:
                    item[1] = value
                    return
            self.table[hashkey].append([key, value])
        
        def get(self, key: int) -> int:
            hashkey = self.hash(key)
            for item in self.table[hashkey]:
                if item[0] == key:
                    return item[1]
            return -1

        def remove(self, key: int) -> None:
            hashkey = self.hash(key)
            for i, item in enumerate(self.table[hashkey]):
                if item[0] == key:
                    self.table[hashkey].pop(i)
                    return

    
    

Twitter  facebook  Email