[Think Data Structures] Java Map 인터페이스 구현 및 분석_2

Map 인터페이스 구현 (MyBetterMap)

---

MyLinearMap클래스보다 Map 인터페이스를 더 잘 구현한 MyBetterMap 정의

MyBetterMap을 좀 더 효율적으로 만든 해싱(hashing)을 소개

해싱(hashing)

MyLinearMap 클래스의 성능 향상을 위해 MyLinearMap 객체의 컬렉션을 포함하는 MyBetterMap이라는 새로운 클래스를 정의

내장된 맵에 따라 키를 나누므로 각 맵의 엔트리 개수는 더 줄어들고, 이 것은 findEntry 메서드와 그 것을 호출하는 메서드의 속도를 빠르게 함.

public class MyBetterMap<K, V> implements Map<K, V> {
    
    protected List<MyLinearMap<K, V>> maps;
 
    MyBetterMap(int k){
        makeMaps(k);
    }
 
    protected void makeMaps(int k){
        maps = new ArrayList<>(k);
        for(int i=0; i<k; i++){
            maps.add(new MyLinearMap<>());
        }
    }
 
    ..
 
}

k를 인자로 받아 얼마나 많은 맵을 사용할지 정의.

makeMaps는 내장된 맵을 생성하고, 생성된 맵을 ArrayList에 저장

새로운 키를 추가하면(put) 맵 중에서 하나를 고르고, 같은 키가 있다면(get) 그 키를 어느 맵에 넣었는지 기억해야 한다.

이 기능일 하기 위해 가장 최선의 접근 법은 해시 함수(hash function)을 사용하는 것이다.

해시함수 : Object 객체를 인자로 받아 해시 코드라는 정수를 반환. 같은 Object 객체는 항상 같은 해시 코드를 반환

주어진 키에 대한 적합한 하위 맵을 고르는 헬퍼 메서드 (chooseMap)

protected MyLinearMap<K, V> chooseMap(Object key){
    int index = 0;
    if(key != null){
        index = Math.abs(key.hashCode()) % maps.size();
    }
    return maps.get(index);
}

hashCode를 구한 후 나머지 연산자(%)를 사용하여 결과가 0 ~ size() -1 사이에 있음을 보장한다.

따라서 index는 항상 maps의 유효한 인덱스가 되고 chooseMap 메서드는 선택한 맵의 참조를 반환한다.

put과 get 메서드의 구현

@Override
public V get(Object key) {
    MyLinearMap<K, V> map = chooseMap(key);
    return map.get(key);
}
 
@Override
public V put(K key, V value) {
    MyLinearMap<K, V> map = chooseMap(key);
    return map.put(key, value);
}

두 메서드는 chooseMap 메서드를 호출하여 맵을 찾고 하위 맵의 메서드를 호출한다.

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

MyBetterMap에 있는 엔트리 목록은 MyLinearMap에 있는 엔트리목록보다 1/k 작으므로, 검색도 k 배 빠를 수 있다고 기대가 된다. 하지만 실행시간은 여전히 n에 비례하므로 MyBetterMap 클래스는 여전히 선형이다.

다음 MyHashMap 클래스 구현에서 이 문제점을 해결해 보도록한다.

※나머지 구현은 https://github.com/ksh901016/thinkDataStructure/ 에서 확인