99클럽 코테 스터디 9일차 TIL ✒️체이닝 방식으로 HashMap 구현하기

✅ 오늘의 학습 키워드

• 체이닝이란
• HashMap 직접 구현하기

---

🔍 오늘의 문제 분석

↘️ 오늘의 문제 바로가기 ↘️

 

오늘의 문제는 HashMap의 주요 메서드인 put, get, remove를 HashMap 클래스를 쓰지 않고 구현하는 문제이다. 실제 자바에서 HashMap가 구현되는 방식으로 구현해보고 싶은 욕심이 생겨서 (내부 구조를 배우고 싶달까..🤔) 동영상을 참고해서 풀어 보았다.

 

---

✨ 오늘의 회고

📌내가 적은 답안📌

class Node {
    int key;
    int val;
    Node next;

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

    
class MyHashMap {
    private Node[] map;

    public MyHashMap() {
        map = new Node[1000];
        for (int i = 0; i < 1000; i++){
            map[i] = new Node(-1, -1);
        }
    }
    
    public void put(int key, int value) {
        int hash = key % 1000;
        Node cur = map[hash];
        
        while (cur.next != null) {
            if (cur.next.key == key) {
                cur.next.val = value;
                return;
            }
            cur = cur.next;
        }

        cur.next = new Node(key, value);
    }
    
    public int get(int key) {
        int hash = key % 1000;
        Node cur = map[hash].next;

        while(cur != null) {
            if (cur.key == key) return cur.val;
            cur = cur.next;
        }
        return -1;
    }
    
    public void remove(int key) {
        int hash = key % 1000;
        Node cur = map[hash];

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

위 코드에서 키 값이 같을 경우, 기존 Node의 val 값을 바꿔준다. 키 값은 다르지만 해시 인덱스(key % 1000)가 같을 경우 Node를 새로 추가해서 연결하는 방식을 사용하고 있다. 이런 새로운 Node를 연결하는 것을 체이닝 방식이라고 하는데 체이닝은 해시 충돌을 해결하는 방법이다.

해시 충돌이란 해시 테이블에서 서로 다른 키가 같은 해시 인덱스를 가질 때 발생한다. 체이닝은 하나의 인덱스에 여러 값을 LinkedList 형태로 저장하는 방식이다. 만약 해시 충돌이 발생하면, 그 인덱스에 새로 들어온 값을 리스트의 마지막에 추가하고 검색/삭제 시 해당 리스트를 순회하면서 값을 찾는다.

map[5] → [5:100] → [15:200] → [25:300]

 

충돌이 많으면 리스트 길이가 길어지고 이에 따른 단점(시간이 오래 걸림)이 있다. 이러한 단점을 Java 8 이상에서 LinkedList를 TreeNode 트리 구조로 변경해서 성능을 개선시켰다고 한다. 체인 길이가 8 이상이면 트리로 변환을 한다고 한다. LinkedList의 탐색 성능은 O(n), 트리는 O(log n). 이 트리화를 위해서 Red-Black Tree라는 균형 이진 탐색 트리를 사용한다. 

 

코딩 스터디를 시작하고 til을 작성하면서 처음으로 자료구조를 깊이 파보는 것 같다. 그리고 파면 팔수록 내가 이해할 수 없는 수준의 개념이 나와서 이런 게 있구나~하고 넘어가는 것이 많다. 오늘 배운 내용도 혼자 코딩하라고 하면 못할 것 같다. 하지만 이런저런 구조를 익혀나가는 것이 재밌고 아직도 배울 게 많구나라는 생각이 든다.