[JAVA] 성능을 개선한 Map 구현 (해싱)

학습 내용

• MyMap 을 좀 더 개선하여 구현

---

해싱

• 내장된 맵에 따라 키를 나누므로 각 맵의 엔트리 개수는 줄어듭니다. 그러므로 메서드의 속도는 향상됩니다.

private List<MyMap<K, V>> maps;

public MyBetterMap(int k) {
    makeMaps(k);
}

protected void makeMaps(int k) {
    maps = new ArrayList<MyMap<K, V>>(k);
    for (int i = 0; i < k; i++) {
        maps.add(new MyMap<K, V>());
    }
}

 

• k 를 인자로 받아 k 개의 엔트리를 ArrayList 에 저장합니다.

 

핵심

1. 키를 살펴보고 어느 내장 맵에 투입할지를 결정하는 방법입니다.
2. 새로운 키를 추가하면 맵 중에서 하나를 고르고, 같은 키가 있다면 그키를 어느 맵에 넣었는지 기억해야 합니다.

---

 

접근 방법

 

private MyMap<K, V> chooseMap(Object key) {
    int index = 0;
    if (key != null) {
        index = Math.abs(key.hashCode()) % maps.size(); // Key 의 해시코드를 절대값으로 만든 다음 map 의 size로 나눈다.
    }
    return maps.get(index);
}

 

해시 함수를 사용하여 주어진 키의 대한 적합한 하위 맵을 고른다.

---

추가

public V put(K key, V value) {
    MyMap<K, V> map = chooseMap(key);
    return map.put(key, value);
}

 

• key의 해시코드를 계산한 값을 체크하여 해당 맵에 인자로 받는key 와 value 를 저장합니다.

---

조회

public V get(Object key) {
    MyMap<K, V> map = chooseMap(key);
    return map.get(key);
}

• key의 해시코드 계산한 값을 가지고 해당 맵을 참조하여 반환합니다.

---

정리

n개의 엔트리를 k개의 하위 맵으로 나누면 맵당 엔트리는 평균 n/k 개가 됩니다.

key 를 조회할 때 해시 코드를 조회 하는데 시간이 걸리고 그다음에 key 에 맞는 하위 맵들을 검색합니다.

여기서 기존의 MyMap 보다 MyBetterMap 의 엔트리 목록이 k 배 빠르므로 검색도 k 배 빠를 것이라 기대가 됩니다.

하지만 여전히 실행시간은 n에 비례하므로 시간 복잡도는 O(n)으로 보여집니다.