문제

LeetCode 705-Design HashMap
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.

예시

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

풀이

class ListNode {
    int key, val;  // 각각 저장된 키와 값
    ListNode next; // 체이닝 방식으로 다음 노드를 가리키는 링크
    public ListNode(int key, int val, ListNode next) {
        this.key = key;
        this.val = val;
        this.next = next;
    }
}

class MyHashMap {
    static final int size = 19997; // 해시 테이블의 크기 (소수 사용 -> 충돌 줄이기)
    static final int mult = 12582917; // 해시 함수 성능 향상용 큰 소수 (곱셈 해시)
    ListNode[] data; // 각 해시 인덱스에 연결리스트를 저장하는 배열

    public MyHashMap() {
        this.data = new ListNode[size];
    }

	//곱셈 후 모듈러 연산으로 해시 인덱스 계산
    //일반적인 key % size보다 충돌이 훨씬 적은 고성능 해시 함수
    private int hash(int key) {
    	// long으로 캐스팅한 이유는 key * mult가 int 범위를 넘을 수 있어서
        return (int)((long)key * mult % size);
    }

    public void put(int key, int val) {
        remove(key); // 같은 키 있으면 먼저 지움
        int h = hash(key);
        ListNode node = new ListNode(key, val, data[h]); // 새로운 노드를 헤드에 삽입(속도 빠름)
        data[h] = node;
    }

    public int get(int key) {
        int h = hash(key);
        ListNode node = data[h];
        //해당 인덱스(버킷)에 연결된 노드들 순회
        for(; node != null; node = node.next) {
            if (node.key == key) {
                return node.val;
            }
        }
        return -1;
    }

	//헤드 노드가 삭제 대상이면 바로 다음 노드를 넣음
    //중간 노드는 node.next로 탐색하면서 삭제
    public void remove(int key) {
        int h = hash(key);
        ListNode node = data[h];
        if (node == null) {
            return;
        }
        if (node.key == key) {
            data[h] = node.next;
        } else for (; node.next != null; node = node.next) {
            if (node.next.key == key) {
                node.next = node.next.next;
                return;
            }
        }
    }
}

회고

처음에는 output을 보고 배열로 풀었으나 HashMap을 구현하라는 문제의 취지와는 어긋나는 것 같아서 제일 좋아요 많이 받은 코드를 대신한다.