[알고리즘]706_Design HashMap

리트코드_706

• Separate Chaining(분리 체인법)
  • 충돌이 발생하면 link로 연결
• Coalesced Chaining(Open Addressing)(합병 체인법, 오픈 주소법)

class MyHashMap {

    // 노드 정의 (연결 리스트로 체이닝)
    private static class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private static final int SIZE = 10000;   // 버킷 수
    private Node[] table;                    // 해시 버킷 배열

    public MyHashMap() {
        table = new Node[SIZE];
    }

    // 해시 함수
    private int hash(int key) {
        return key % SIZE;
    }

    // idx는 table 인덱스, key는 해시하기 전 key. 
    // table[idx] 비어있으면 노드 추가, 있으면 순회 후 갱신 or 뒤에 추가
    public void put(int key, int value) {
        int idx = hash(key);

        // 버킷이 비어 있으면 새 노드 삽입
        if (table[idx] == null) {
            table[idx] = new Node(key, value, null);
            return;
        }

        // 연결 리스트 순회하면서 key 존재 여부 확인
        Node cur = table[idx];
        Node prev = null;

        while (cur != null) {
            if (cur.key == key) {
                // 이미 존재하는 key면 값만 갱신
                cur.value = value;
                return;
            }
            prev = cur;
            cur = cur.next;
        }

        // 존재하지 않으면 리스트 맨 뒤에 새 노드 추가
        prev.next = new Node(key, value, null);
    }

    public int get(int key) {
        int idx = hash(key);
        Node cur = table[idx];

        while (cur != null) {
            if (cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }

        return -1;  // key가 없을 때
    }

    public void remove(int key) {
        int idx = hash(key);
        Node cur = table[idx];
        Node prev = null;

        while (cur != null) {
            if (cur.key == key) {
                // 첫 번째 노드 삭제
                if (prev == null) {
                    table[idx] = cur.next;
                } else {
                    prev.next = cur.next;
                }
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}