706. Design HashMap - Easy

前往題目

想法

• key-value，key是唯一的，那能用hashset嗎?題目說不能用built-in hash table，hashset算hash table嗎?維基:In computing, a hash table, also known as a hash map or a hash set，所以不能用hash set
• 那是要手動運算hashcode?
• 不用hash table又想要get可以O(1)時間完成，只能透過index直接取，如果是陣列的話

思路

簡單版:直接初始化陣列大小為題目的數字範圍

進階版:應用hashmap概念，hash與chaining

ListNode:每個hashcode的位置都使用鏈表來儲存多個不同的key
初始化:一個大小適合的陣列，放好ListNode
hash:key取餘map的大小，這樣就能保證每個key都映射到map裡不會出界
put:算出hash，根據hash定位，疊代ListNode，有找到相同key就更新值，沒有的話就在鏈表尾巴加入
get:算出hash，定位，疊代，沒找到就回傳-1
remove:算出hash，定位，找到就刪除並且拼接鏈表，沒找到無所謂

Code

簡單版

class MyHashMap {
    int[] map;
    public MyHashMap() {
        map = new int[1000001];
        Arrays.fill(map, -1);
    }
    
    public void put(int key, int value) {
        map[key] = value;
    }
    
    public int get(int key) {
        return map[key];
    }
    
    public void remove(int key) {
        map[key] = -1;
    }
}

進階版

class MyHashMap {
    class ListNode {
        int key;
        int val;
        ListNode next;

        public ListNode() {
        }

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

    ListNode[] map;

    public MyHashMap() {
        map = new ListNode[1000];
        Arrays.fill(map, new ListNode());
    }

    private int hash(int key) {
        return key % map.length;
    }

    public void put(int key, int value) {
        // 從dummy node開始
        ListNode cur = map[hash(key)];

        // 不要走到最後的null，這樣才能加入新的key
        while (cur.next != null) {
            // 找到相同key
            if (cur.next.key == key) {
                cur.next.val = value;
                return;
            }
            // 換下一個
            cur = cur.next;
        }
        // 沒找到，加入新的key-value
        cur.next = new ListNode(key, value, null);
    }

    public int get(int key) {
        // 從第一個node開始，不是dummynode
        ListNode cur = map[hash(key)].next;

        // 直到到null
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    public void remove(int key) {
        // 從dummynode開始
        ListNode cur = map[hash(key)];

        // 確保當前以及下一個不是null，這樣找到的時候要remove才方便
        while (cur != null && cur.next != null) {
            if (cur.next.key == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }
}