Teaching Kids Programming – Design a Hash Table | Algorithms, Blockchain and Cloud

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 1:
Input

1 2	["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output

1	[null, null, null, 1, -1, null, 1, null, -1]

[null, null, null, 1, -1, null, 1, null, -1]

Explanation

MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:
0 <= key, value <= 10^6
At most 10^4 calls will be made to put, get, and remove.

Design a Hash Table Class in Python

We need a hash function that allows to distribute keys “evenly” to the fixed-size hash table (less collision). If there is a collision, i.e. h(a)=h(b) if a is not equal to b, we need to append them to a list.

To get the value of a key, we first compute the hash key, then go through the list to find if the original key exists.

To update the value of a key, similarly, we need to locate the entry if it exists, update it. Otherwise, the pair (key, value) should be appended to the list (or linked list).

To remove a key-value pair, we locate it if it exists and remove it by copying over the last element of the list, and shrink it by pop().

class MyHashMap:
    def __init__(self):
        self.TABLE_SIZE = 65537
        self.data = [[] for _ in range(self.TABLE_SIZE)]
 
    def getKey(self, key: int) -> int:
        return key % self.TABLE_SIZE
           
    def put(self, akey: int, value: int) -> None:
        key = self.getKey(akey)    
        for i in range(len(self.data[key])):
            if self.data[key][i][0] == akey:
                self.data[key][i][1] = value
                return
        self.data[key].append([akey, value])
 
    def get(self, akey: int) -> int:
        key = self.getKey(akey)
        for i in range(len(self.data[key])):
            if self.data[key][i][0] == akey:
                return self.data[key][i][1]
        return -1
    
    def remove(self, akey: int) -> None:
        key = self.getKey(akey)
        for i in range(len(self.data[key])):
            if self.data[key][i][0] == akey:
                self.data[key][i] = self.data[key][-1][:]
                self.data[key].pop()
                break

class MyHashMap:
    def __init__(self):
        self.TABLE_SIZE = 65537
        self.data = [[] for _ in range(self.TABLE_SIZE)]

    def getKey(self, key: int) -> int:
        return key % self.TABLE_SIZE
           
    def put(self, akey: int, value: int) -> None:
        key = self.getKey(akey)    
        for i in range(len(self.data[key])):
            if self.data[key][i][0] == akey:
                self.data[key][i][1] = value
                return
        self.data[key].append([akey, value])

    def get(self, akey: int) -> int:
        key = self.getKey(akey)
        for i in range(len(self.data[key])):
            if self.data[key][i][0] == akey:
                return self.data[key][i][1]
        return -1
    
    def remove(self, akey: int) -> None:
        key = self.getKey(akey)
        for i in range(len(self.data[key])):
            if self.data[key][i][0] == akey:
                self.data[key][i] = self.data[key][-1][:]
                self.data[key].pop()
                break

If the hash function is practically fast enough and does not incur much collision, the complexity of Get, Update and Remove for a hash table is O(1) constant.

Design a Container with O(1) Add, Remove and GetRandomElement

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

698 words
Last Post: Teaching Kids Programming - Introduction to Hashing Function
Next Post: Teaching Kids Programming - One-way Jump Game via Backtracking, DP and Greedy Algorithm

The Permanent URL is: Teaching Kids Programming – Design a Hash Table