Design HashMap

Designing a HashMap from scratch requires understanding the fundamental operations that a HashMap must perform: inserting, retrieving, and deleting key-value pairs. We can implement a simple version of a HashMap using a list of buckets, where each bucket contains a list of key-value pairs. Hashing the key will determine the index of the bucket.

Algorithm:

  1. Initialization: Create an array of buckets, each containing a list of key-value pairs.
  2. Put (Insert): a. Hash the key to find the appropriate bucket. b. Check if the key already exists in the bucket. If it does, update the value. c. Otherwise, add the key-value pair to the bucket.
  3. Get (Retrieve): a. Hash the key to find the appropriate bucket. b. Search the bucket for the key and return the corresponding value if found. c. Return -1 if the key is not found.
  4. Remove: a. Hash the key to find the appropriate bucket. b. Remove the key-value pair from the bucket if it exists.

Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class MyHashMap:
    def __init__(self):
        self.buckets = [[] for _ in range(1000)] # Size can be adjusted based on expected load

    def put(self, key: int, value: int) -> None:
        bucket_index = key % len(self.buckets)
        bucket = self.buckets[bucket_index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key: int) -> int:
        bucket_index = key % len(self.buckets)
        bucket = self.buckets[bucket_index]
        for k, v in bucket:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        bucket_index = key % len(self.buckets)
        bucket = self.buckets[bucket_index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return

Insights:

  • Hash Function: The modulus operator is used as a simple hash function, dividing the key by the number of buckets and taking the remainder. This determines the bucket index.
  • Handling Collisions: By using a list of key-value pairs within each bucket, this implementation handles collisions by allowing multiple key-value pairs to reside in the same bucket.
  • Time Complexity: The average time complexity for put, get, and remove operations is (O(1)). In the worst case, where all keys are mapped to the same bucket, the time complexity would be (O(n)), where (n) is the number of keys.
  • Space Complexity: The space complexity is (O(n + k)), where (n) is the number of keys, and (k) is the number of buckets.

This implementation demonstrates the basic principles of a HashMap, allowing you to explore further optimizations and improvements to suit specific use cases or constraints.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class MyHashMap

=begin
    Initialize your data structure here.
=end
    def initialize()
           @hash = [] 
    end


=begin
    value will always be non-negative.
    :type key: Integer
    :type value: Integer
    :rtype: Void
=end
    def put(key, value)
            @hash[key] = value    
    end


=begin
    Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
    :type key: Integer
    :rtype: Integer
=end
    def get(key)
                if @hash[key].nil?
      return -1
    else
      return @hash[key]
    end

    end

=begin
    Removes the mapping of the specified value key if this map contains a mapping for the key
    :type key: Integer
    :rtype: Void
=end
    def remove(key)
            @hash[key] = nil    
    end


end

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap.new()
# obj.put(key, value)
# param_2 = obj.get(key)
# obj.remove(key)

Identifying Problem Isomorphism

“Design HashMap” is related to the problem “Two Sum”. Both problems involve using a data structure to store and look up key-value pairs, but they are not precisely isomorphic.

“Design HashMap” requires you to implement a HashMap without using any built-in hash table libraries. It’s a problem about designing a data structure that can efficiently perform operations like adding, updating, and removing key-value pairs.

“Two Sum” involves finding two numbers in an array that add up to a target value. While the problem itself does not require a HashMap, a common solution involves storing the numbers of the array as keys in a HashMap and their indices as values. This allows for efficient look up when searching for the complement of a number.

“Two Sum” is simpler because it involves manipulating an existing data structure, while “Design HashMap” involves creating a new data structure from scratch. Being comfortable with “Two Sum” and the usage of HashMaps could serve as a starting point for understanding and designing your own HashMap for the more complex problem.

10 Prerequisite LeetCode Problems

These are selected based on the concepts they cover, such as array manipulation, linked list operations, and hashing, which are crucial for implementing hash maps.

  1. 1. Two Sum: It’s a simple problem that involves searching for a pair of elements in an array. It can be solved efficiently using a hash map.

  2. 204. Count Primes: This problem helps you understand basic number theory which is sometimes used in hash functions.

  3. 136. Single Number: This problem can be solved using a hash map and helps understand bit manipulation.

  4. 349. Intersection of Two Arrays: This problem can be solved using a set or a hash map to find common elements.

  5. 202. Happy Number: This problem involves finding a cycle in a sequence of numbers, which can be done efficiently using a hash set.

  6. 141. Linked List Cycle: This problem involves finding a cycle in a linked list. It is a good practice for handling pointers and understanding memory.

  7. 155. Min Stack: This problem involves designing a stack that supports retrieving the minimum element in constant time. It’s a good exercise in designing simple data structures.

  8. 232. Implement Queue using Stacks: This problem is about implementing one data structure using another. It helps understand the difference between stacks and queues.

  9. 383. Ransom Note: This problem can be solved using a hash map to count occurrences of each character.

  10. 242. Valid Anagram: This problem involves comparing two strings to see if one is an anagram of the other. It can be solved using a hash map to count characters.

You will learn hashing and basic data structure manipulation, which are necessary for implementing a hash map.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class ListNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.hash_table = [None] * self.size 

    def put(self, key: int, value: int) -> None:
        index = key % self.size 
    
        if self.hash_table[index] == None:
            self.hash_table[index] = ListNode(key, value)
        else:
            curr_node = self.hash_table[index]
            while True:
                if curr_node.key == key:
                    curr_node.value = value
                    return 
                if curr_node.next == None: break
                curr_node = curr_node.next 
            curr_node.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.size 
        curr_node = self.hash_table[index]

        while curr_node:
            if curr_node.key == key:
                return curr_node.value 
            else:
                curr_node = curr_node.next
        
        return -1

    def remove(self, key: int) -> None:
        index = key % self.size 
        curr_node = prev_node = self.hash_table[index]
        if not curr_node: return 
        
        if curr_node.key == key:
            self.hash_table[index] = curr_node.next
        else:
            curr_node = curr_node.next

            while curr_node:
                if curr_node.key == key:
                    prev_node.next = curr_node.next 
                    break
                else:
                    prev_node, curr_node = prev_node.next, curr_node.next        

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

Problem Classification

This problem falls under the domain of Data Structures, specifically Hash Maps or Dictionaries.

What:

  1. HashMap Design: The problem is about designing a custom HashMap data structure without using built-in hash table libraries. This is a common pattern in interview problems where the goal is to understand how well a candidate knows about the internal workings of common data structures.

  2. Inserting a Pair (Key, Value): The HashMap should have the capability to insert a pair of key and value. If the key already exists, it should update the existing value.

  3. Fetching a Value for a Key: The HashMap should have the capability to return a value for a given key. If the key doesn’t exist, it should return -1.

  4. Removing a Pair (Key, Value): The HashMap should have the capability to remove a pair based on the given key. If the key doesn’t exist, it should do nothing.

This problem can be further classified as a Data Structures Design problem, as the primary task is to design and implement the HashMap data structure with all the basic operations. The implementation should focus on creating a HashMap data structure from scratch, which requires a deep understanding of how this data structure works internally.

Language Agnostic Coding Drills

  1. Classes and Objects: Defining classes and creating objects is the first concept. The code defines two classes, ListNode and MyHashMap. Each ListNode represents a key-value pair and MyHashMap maintains an array of ListNodes (a hash table).

  2. Data Structure - Linked List: The Linked List data structure is used for each bucket in the hash table. Each ListNode holds a key-value pair and a reference to the next node. This is a foundational concept, but manipulating Linked Lists can sometimes be tricky, hence the higher difficulty level.

  3. Hash Function and Modulo Operation: The hash function used is the modulo operation which determines the index where a key-value pair should be placed in the hash table.

  4. Insertion in a Linked List: Insertion in the Linked List can be at the beginning (if the bucket is empty) or at the end (if the bucket is not empty and the key doesn’t already exist).

  5. Searching in a Linked List: The get and remove methods involve searching for a key in a Linked List. If a key exists, the associated value is returned or removed, respectively.

  6. Removing a node from a Linked List: Removing a node requires handling the node’s previous and next references correctly.

The problem-solving approach leading from the problem statement to the final solution can be broken down into the following steps:

  1. Understand the Problem: The first step is to understand the problem statement and the functionality that needs to be implemented. In this case, we need to create a HashMap with put, get and remove operations.

  2. Design the HashMap: Next, we design the HashMap data structure. We use an array of Linked Lists (also known as separate chaining) to handle hash collisions.

  3. Implement the HashMap Operations: Finally, we implement the operations:

    • For put, we first compute the index using the hash function, then insert a new node or update an existing node at that index.

    • For get, we compute the index using the hash function, then search for the key at that index and return the associated value.

    • For remove, we compute the index, search for the key, and if found, remove the associated node.

Each of the coding drills contributes to one or more steps in this process. By practicing these drills, you can become proficient at implementing these steps and can then combine them to solve similar problems involving HashMaps or other data structures.

Targeted Drills in Python

1. Classes and Objects

1
2
3
4
5
6

class Person:
    def __init__(self, name):
        self.name = name

p = Person("John")
print(p.name)  # Output: John

This drill teaches you how to define a class and create an instance of it.

2. Data Structure - Linked List

1
2
3
4
5
6
7

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2)

This drill demonstrates creating a simple Linked List with nodes containing data and a next reference.

3. Hash Function and Modulo Operation

1
2
3
4

def hash_function(key, size):
    return key % size

print(hash_function(10, 5))  # Output: 0

This is a simple hash function using the modulo operation.

4. Insertion in a Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insert(head, data):
    if not head:
        return Node(data)
    else:
        current = head
        while current.next:
            current = current.next
        current.next = Node(data)
        return head

head = insert(None, 1)
head = insert(head, 2)

This drill demonstrates insertion in a Linked List at the beginning and at the end.

5. Searching in a Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def search(head, key):
    current = head
    while current:
        if current.data == key:
            return True
        current = current.next
    return False

print(search(head, 1))  # Output: True
print(search(head, 3))  # Output: False

This drill involves searching for a key in a Linked List.

6. Removing a node from a Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def remove(head, key):
    current = head
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next
    if prev is None:
        head = current.next
    elif current:
        prev.next = current.next
    return head

head = remove(head, 1)

This drill involves removing a node from a Linked List.

Each drill targets a fundamental coding concept used in the problem. For example, understanding classes and objects is crucial for creating the HashMap and ListNode classes. Similarly, understanding Linked List operations is critical for managing elements within each bucket of the HashMap.

To integrate these concepts into a final solution, begin by creating the classes (as per the first drill). Use the hash function (drill 3) to decide where to store elements. Implement insertion, searching, and removal within the HashMap class, using drills 4, 5, and 6. Each bucket in the HashMap is a Linked List, and thus the operations will require manipulating these lists. By combining these drills, you will reconstruct the original solution.

title: Using Array as Hashmap excerpt: This covers the basic building block Using Array as Hashmap. tags: using-array-as-hashmap

An array can be used as a hashmap to solve Problem: Design HashMap.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class MyHashMap
  def initialize
    @hash = []
  end

  def put(key, value)
    @hash[key] = value    
  end

  def get(key)
    if @hash[key].nil?
      return -1
    else
      return @hash[key]
    end
  end

  def remove(key)
    @hash[key] = nil    
  end
end