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?
  • 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);
     */
    
  • // 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):
            """
            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)
    

Or, use bucket strategy.

  • 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);
      */
    }
    
  • // 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):
            """
            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)
    

List<int[]>

  • class MyHashMap {
        //Load factor = 10000/size = 0.75
        List<int[]>[] lists; //using List<List<int[]>> lists is fine as well.
        int size = 13000;
    
        //O(size)
        /** Initialize your data structure here. */
        public MyHashMap() {
            lists = new ArrayList[size];
            for(int i=0; i<lists.length; i++)
                lists[i] = new ArrayList<>(); //don't use linkedlist in my version which makes put() O(L^2)
        }
        
        public int getHashcode(int key)
        {
            return key%size;
        }
        
        //O(L)
        /** value will always be non-negative. */
        public void put(int key, int value) {
            int index = getHashcode(key);
            for(int i=0; i<lists[index].size(); i++)
            {
                if(lists[index].get(i)[0]==key)
                {
                    lists[index].get(i)[1]=value;
                    return;
                }
            }
            lists[index].add(new int[]{key, value});
        }
        
        //O(L)
        /** 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 index = getHashcode(key);
            for(int i=0; i<lists[index].size(); i++)
            {
                if(lists[index].get(i)[0]==key)
                    return lists[index].get(i)[1];
            }
            return -1;    
        }
        
        //O(L)
        /** Removes the mapping of the specified value key if this map contains a mapping for the key */
        public void remove(int key) {
            int index = getHashcode(key);
            for(int i=0; i<lists[index].size(); i++)
            {
                if(lists[index].get(i)[0]==key)
                    lists[index].remove(i);
            }
            return;
        }
    }
    
    
  • // 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):
            """
            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)
    

List<List<Integer>> not passing OJ large dataset, possibly some collisions

test case:

["MyHashMap","put","get","put","get"]
[[],[1000000,1],[1000000],[0,2],[0]]

if matrix 1000*1000, then 0 and 1000000 will colide, so make it 1001

  • class MyHashMap {
    
        int bucketSize = 1000;
        int eachBucketLength = 1001;
        List<List<Integer>> data;
    
        /** Initialize your data structure here. */
        public MyHashMap() {
            data = new ArrayList<>();
            IntStream.range(0,bucketSize).forEach(i -> data.add(new ArrayList<>()));
        }
    
        /** value will always be non-negative. */
        public void put(int key, int value) {
            if (data.get(hash(key)).isEmpty()) {
                IntStream.range(0,bucketSize).forEach(i -> data.get(hash(key)).add(-1));
            }
    
            data.get(hash(key)).set(position(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) {
            if (!data.get(hash(key)).isEmpty()) {
                return data.get(hash(key)).get(position(key));
            }
    
            return -1;
        }
    
        /** Removes the mapping of the specified value key if this map contains a mapping for the key */
        public void remove(int key) {
            if (!data.get(hash(key)).isEmpty()) {
                data.get(hash(key)).set(position(key), -1);
            }
        }
    
        private int hash(int key) {
            return key % bucketSize;
        }
    
        private int position(int key) {
            return key / eachBucketLength;
        }
    }
    
    /**
     * 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):
            """
            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)
    

All Problems

All Solutions