Formatted question description: https://leetcode.ca/all/706.html

706. Design HashMap

Level

Easy

Description

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

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found) 

Note:

All values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

Solution

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?

public class Design_HashMap {
    class MyHashMap {
        private DoublyLinkedList[] buckets;
        private int capacity;

        /**
         * Initialize your data structure here.
         */
        public MyHashMap() {
            this.capacity = 10000;
            this.buckets = new DoublyLinkedList[capacity];
            for (int i = 0; i < capacity; i++) {
                buckets[i] = new DoublyLinkedList();
            }
        }

        /**
         * value will always be non-negative.
         */
        public void put(int key, int value) {
            int bucketIdx = hashCode(key);
            buckets[bucketIdx].insertToHead(key, value);
        }

        /**
         * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
         */
        public int get(int key) {
            int bucketIdx = hashCode(key);
            return buckets[bucketIdx].get(key);
        }

        /**
         * Removes the mapping of the specified value key if this map contains a mapping for the key
         */
        public void remove(int key) {
            int bucketIdx = hashCode(key);
            buckets[bucketIdx].remove(key);
        }

        private int hashCode(int key) {
            return Integer.hashCode(key) % capacity;
        }
    }

    class ListNode {
        ListNode next, prev;
        int key;
        int val;

        public ListNode(int key, int val) {
            next = prev = null;
            this.key = key;
            this.val = val;
        }
    }

    class DoublyLinkedList {
        ListNode dummyHead;
        ListNode dummyTail;

        public DoublyLinkedList() {
            dummyHead = new ListNode(-1, -1);
            dummyTail = new ListNode(-1, -1);
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }

        public void insertToHead(int key, int val) {
            ListNode existNode = search(key);
            if (existNode != null) {
                existNode.val = val;
            } else {
                ListNode newNode = new ListNode(key, val);
                ListNode nextNode = dummyHead.next;
                dummyHead.next = newNode;
                newNode.next = nextNode;
                nextNode.prev = newNode;
                newNode.prev = dummyHead;
            }
        }

        private ListNode search(int key) {
            ListNode p = dummyHead.next;
            while (p != dummyTail) {
                if (p.key == key) {
                    return p;
                }

                p = p.next;
            }

            return null;
        }

        public int get(int key) {
            ListNode node = search(key);

            return node == null ? -1 : node.val;
        }

        public void remove(int key) {
            ListNode currNode = search(key);
            if (currNode != null) {
                ListNode prevNode = currNode.prev;
                ListNode nextNode = currNode.next;
                prevNode.next = nextNode;
                nextNode.prev = prevNode;
            }
        }
    }

/**
  * 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 {

    int[] hash;

    /** Initialize your data structure here. */
    public MyHashMap() {
        hash = new int[1000001];
        Arrays.fill(hash, -1);
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        hash[key] = value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return hash[key];
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        hash[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 {
    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);
 */

// OJ: https://leetcode.com/problems/design-hashmap/
// Time: O(1)
// Space: O(1)
class MyHashMap {
    const static int N = 1000001;
    int m[N];
public:
    MyHashMap() {
        for (int i = 0; i < N; ++i) m[i] = -1;
    }
    void put(int key, int value) {
        m[key] = value;
    }
    int get(int key) {
        return m[key];
    }
    void remove(int key) {
        m[key] = -1;
    }
};

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:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.buckets = 1000
        self.itemsPerBuckect = 1001
        self.hashmap = [[] for _ in range(self.buckets)]

    def hash(self, key):
        return key % self.buckets
    
    def pos(self, key):
        return key // self.buckets

    def put(self, key, value):
        """
        value will always be positive.
        :type key: int
        :type value: int
        :rtype: void
        """
        hashkey = self.hash(key)
        if not self.hashmap[hashkey]:
            self.hashmap[hashkey] = [None] * self.itemsPerBuckect
        self.hashmap[hashkey][self.pos(key)] = value

    def get(self, key):
        """
        Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
        :type key: int
        :rtype: int
        """
        hashkey = self.hash(key)
        if (not self.hashmap[hashkey]) or self.hashmap[hashkey][self.pos(key)] == None:
            return -1
        else:
            return self.hashmap[hashkey][self.pos(key)]

    def remove(self, key):
        """
        Removes the mapping of the specified value key if this map contains a mapping for the key
        :type key: int
        :rtype: void
        """
        hashkey = self.hash(key)
        if self.hashmap[hashkey]:
            self.hashmap[hashkey][self.pos(key)] = None


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

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

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

706. Design HashMap

Level

Description

Solution

All Problems

All Solutions