Design a HashMap


  • 0
    C

    I got this question in an interview. Can anyone help me with the best approach to solve this question?


  • 0
    B

    Look up separate chaining and linear probing. The latter is more efficient.


  • 4
    C

    Sharing my Java solution using array with linked list. I tested a few cases and it works OK. Any suggestions/comments are welcome.

    class MyHashMap {
        private static final int SIZE = 32;
    
        class Entry {
            String key;
            String value;
            Entry next;
            Entry(String key, String value) {
                this.key = key;
                this.value = value;
                next = null;
            }
        }
    
        private Entry[] table;
    
        public MyHashMap() {
            table = new Entry[SIZE];
        }
    
        public void put(String key, String value) {
            Entry entry = new Entry(key, value);
            int code = key.hashCode() % SIZE;
            if (table[code] == null) {
                table[code] = entry;
            } else {
                addOrUpdateNode(table[code], entry);
            }
        }
    
        public String get(String key) {
            int code = key.hashCode() % SIZE;
            Entry head = table[code];
            while (head != null) {
                if (head.key.equals(key)) return head.value;
                head = head.next;
            }
            return null;
        }
    
        public void remove(String key) {
            int code = key.hashCode() % SIZE;
            Entry head = table[code];
            Entry dummy = new Entry("0", "0");
            dummy.next = head;
            Entry prev = dummy;
            while (head != null) {
                if (head.key.equals(key)) prev.next = head.next;
                prev = head;
                head = head.next;
            }
            table[code] = dummy.next;
        }
    
        public boolean containsKey(String key) {
            int code = key.hashCode() % SIZE;
            Entry head = table[code];
            while (head != null) {
                if (head.key.equals(key)) return true;
                head = head.next;
            }
            return false;
        }
    
        private void addOrUpdateNode(Entry head, Entry node) {
            Entry prev = head;
            while (head != null) {
                if (head.key.equals(node.key)) {
                    head.value = node.value;
                    return;
                }
                prev = head;
                head = head.next;
            }
            prev.next = node;
        }
    }
    

  • 0
    B

    @ccyjoshua nicely done!


  • -1
    M

    @ccyjoshua it seems your solution has a fixed bucket size. The efficiency will drop quickly when the size is increasing. So it's better to adjust (increasing or decreasing) the bucket size on the fly based on a load factor. For example, the LF = 0.75, if the size of the HashMap > 0.75 * size of Bucket, we should double the size of the bucket. Then cut the bucket by half when size of the HashMap < 0.75 * half size of Bucket.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.