706. Design HashMap

Description

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
["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]

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]]

Constraints:

0 <= key, value <= 10⁶
At most 10⁴ calls will be made to put, get, and remove.

Solutions

A straightforward approach to implement a hash map is to use chaining with a list of buckets, where each bucket is a list (or linked list) of tuples representing key-value pairs.

Since all keys and values are in the range of [0, 1000000], create an array with length 1000001, which has int type. Initially, all the elements in the array are -1.

For the put function, set the value at index key in the array to be value.

For the remove function, set the value at index key in the array to be -1.

For the get function, simply return the element at index key.

Some of the questions which can be asked to the interviewer before implementing the solution:

For simplicity, are the keys integers only?
For collision resolution, can we use chaining?
Do we have to worry about load factors?
Can we assume inputs are valid or do we have to validate them?
Can we assume this fits memory?

Open addressing with linear probing

There are other ways to implement a HashMap beyond the chaining method with buckets. One alternative approach is to use open addressing with linear probing for collision resolution. In this method, when a collision occurs (i.e., two keys hash to the same index), the algorithm probes subsequent indices in the array (wrapping around to the beginning if necessary) until an empty slot (or the key itself, if already present) is found.

Key Differences and Features:

Initialization (__init__): The HashMap is initialized with a fixed-size array (self.data) that stores key-value pairs directly. A special marker (self.DELETED) is used to indicate deleted entries, which is necessary for linear probing to function correctly.
Linear Probing in put: To insert a new key-value pair, the method computes the index for the key using the _hash function. If the computed index is occupied (by a different key), it linearly probes subsequent indices until an empty slot or the key itself is found.
Retrieving Values (get): To retrieve a value, the _find helper method is used to locate the key in the array. If found, it returns the associated value; otherwise, -1 is returned.
Removing Entries (remove): To remove a key-value pair, the _find method locates the key, and its slot is marked as deleted using the self.DELETED marker. This allows linear probing to continue working correctly for other keys.
Finding Entries (_find): A helper method that attempts to find the slot containing the specified key, taking into account linear probing and deleted entries. It returns both the index and a boolean indicating whether the key was found.

Advantages and Considerations:

Space Efficiency: This approach tends to be more space-efficient compared to chaining, especially when the load factor is low to moderate.
Performance: While open addressing with linear probing can offer good performance for lookups, inserts, and deletions, it may suffer from clustering effects, where consecutive slots become filled, leading to longer probe sequences. Careful management of the load factor and capacity is crucial.
Resizing: To maintain efficient operations, the capacity of the array may need to be increased (and all keys rehashed) when the load factor gets too high. This resizing logic is not included in the above implementation but would be necessary for a production-level HashMap to ensure performance does not degrade with many entries.

class MyHashMap {
    private int[] data = new int[1000001];

    public MyHashMap() {
        Arrays.fill(data, -1);
    }

    public void put(int key, int value) {
        data[key] = value;
    }

    public int get(int key) {
        return data[key];
    }

    public void remove(int key) {
        data[key] = -1;
    }
}

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

class MyHashMap {
public:
    int data[1000001];

    MyHashMap() {
        memset(data, -1, sizeof data);
    }

    void put(int key, int value) {
        data[key] = value;
    }

    int get(int key) {
        return data[key];
    }

    void remove(int key) {
        data[key] = -1;
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

class MyHashMap:
    def __init__(self):
        self.data = [-1] * 1000001

    def put(self, key: int, value: int) -> None:
        self.data[key] = value

    def get(self, key: int) -> int:
        return self.data[key]

    def remove(self, key: int) -> None:
        self.data[key] = -1


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

#############

class MyHashMap: # hash to bucket
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key: int) -> int:
        """
        Generate a hash for a given key.
        """
        return key % self.size

    def put(self, key: int, value: int) -> None:
        """
        Value will always be non-negative.
        """
        hash_key = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[hash_key]):
            if k == key:
                self.buckets[hash_key][i] = (key, value)
                return
        self.buckets[hash_key].append((key, value))

    def get(self, key: int) -> int:
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
        """
        hash_key = self._hash(key)
        for k, v in self.buckets[hash_key]:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key.
        """
        hash_key = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[hash_key]):
            if k == key:
                del self.buckets[hash_key][i]
                return

###############

class MyHashMap: # open addressing with linear probing
    def __init__(self):
        self.capacity = 10000
        self.data = [None] * self.capacity
        self.DELETED = (None, None)  # Marker for deleted entries

    def _hash(self, key):
        return key % self.capacity

    def put(self, key: int, value: int) -> None:
        idx = self._hash(key)
        while self.data[idx] not in (None, self.DELETED, key):
            idx = (idx + 1) % self.capacity
        self.data[idx] = (key, value)

    def get(self, key: int) -> int:
        idx, found_key = self._find(key)
        if found_key:
            return self.data[idx][1]
        return -1

    def remove(self, key: int) -> None:
        idx, found_key = self._find(key)
        if found_key:
            self.data[idx] = self.DELETED

    def _find(self, key):
        original_idx = idx = self._hash(key)
        while self.data[idx] is not None:
            if self.data[idx] != self.DELETED and self.data[idx][0] == key:
                return idx, True
            idx = (idx + 1) % self.capacity
            if idx == original_idx:  # Came full circle
                break
        return original_idx, False

type MyHashMap struct {
	data []int
}

func Constructor() MyHashMap {
	data := make([]int, 1000010)
	for i := range data {
		data[i] = -1
	}
	return MyHashMap{data}
}

func (this *MyHashMap) Put(key int, value int) {
	this.data[key] = value
}

func (this *MyHashMap) Get(key int) int {
	return this.data[key]
}

func (this *MyHashMap) Remove(key int) {
	this.data[key] = -1
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Put(key,value);
 * param_2 := obj.Get(key);
 * obj.Remove(key);
 */

class MyHashMap {
    data: Array<number>;
    constructor() {
        this.data = new Array(10 ** 6 + 1).fill(-1);
    }

    put(key: number, value: number): void {
        this.data[key] = value;
    }

    get(key: number): number {
        return this.data[key];
    }

    remove(key: number): void {
        this.data[key] = -1;
    }
}

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

706 - Design HashMap

706. Design HashMap

Description

Solutions

Open addressing with linear probing

Key Differences and Features:

Advantages and Considerations:

All Problems

All Solutions

Welcome to Subscribe On Youtube

706. Design HashMap

Description

Solutions

Open addressing with linear probing

Key Differences and Features:

Advantages and Considerations:

All Problems

All Solutions