[Day 4] TIL

오늘도 leetcode의 문제가 나왔다.

Day3 문제와 비슷한 유형의 문제여서 조금 덜 어려웠다!

내장 라이브러리를 사용하지 않고, 기본적인 해시맵을 직접 구현하는 문제이다.

한창 풀고서 '오늘은 풀만한데?' 라고 생각하며 제출을 했고, 통과가 되어서 '작심큰일'에 그대로 제출했다.

그런데 해설을 확인한 뒤 아차싶었다..ㅎ

내장 라이브러리를 사용해버린 것이다😭

스파르타에서 제공해주는 시니어 개발자분의 해설을 볼 수 있어서 다행이다...

이 해설로 다시 공부해야겠다😓

---

 

[Leetcode: 706] Design HashMap

 

👨🏻‍💻 시니어 개발자의 코드

class MyHashMap {
    private static final int SIZE = 10000;
    private Node[] buckets;

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

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

    private int getIndex(int key) {
        return key % SIZE;
    }

    public void put(int key, int value) {
        int idx = getIndex(key);
        if (buckets[idx] == null) {
            buckets[idx] = new Node(key, value);
            return;
        }

        Node curr = buckets[idx];
        Node prev = null;
        while (curr != null) {
            if (curr.key == key) {
                curr.value = value; 
                return;
            }
            prev = curr;
            curr = curr.next;
        }
        prev.next = new Node(key, value); 
    }

    public int get(int key) {
        int idx = getIndex(key);
        Node curr = buckets[idx];
        while (curr != null) {
            if (curr.key == key) {
                return curr.value;
            }
            curr = curr.next;
        }
        return -1;
    }

    public void remove(int key) {
        int idx = getIndex(key);
        Node curr = buckets[idx];
        Node prev = null;
        while (curr != null) {
            if (curr.key == key) {
                if (prev == null) {
                    buckets[idx] = curr.next; 
                } else {
                    prev.next = curr.next; 
                }
                return;
            }
            prev = curr;
            curr = curr.next;
        }
    }
}

    
}

 

☝🏻 연결 리스트 대신 트리 구조로도 가능하다는 것을 인식하기

✌🏻 해시맵을 구현 할 때는 충돌을 꼭 염두에 두기  =>  키의 범위와 충돌 가능성을 판단해서 적합한 버킷 크기를 설정하기

 

✅ 다른 개발자의 코드

🔗 SGallivan 님의 솔루션 

=> 성능은 올리고, 충돌 가능성을 줄인 코드