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

Map 인터페이스 구현 MyHashMap

---

hashing을 이용한 MyBetterMap은 여전히 성장차수는 선형이었다. (MyBetterMap 포스팅)

n개의 엔트리와 k개의 하위 맵이 있다면 하위 맵의 크기는 평균 n/k가 되고, 여전히 n에 비례하게 된다.

하지만, n과 함께 k를 늘려간다면 n/k의 크기를 제한할 수 있다.

하위 맵당 엔트리의 개수가 일정하면 단일 하위 맵은 상수시간으로 검색이 가능(해시 함수를 계산하는 것 => 상수시간)

MyHashMap 클래스는 MyBetterMap 클래스를 확장하므로 MyBetterMap에 정의된 메서드를 상속한다. 

public class MyHashMap<K, V> extends MyBetterMap<K, V> implements Map<K,V>{
 
    // 재해쉬하기 전 하위 맵당 평균 엔트리 개수
    protected static final double FACTOR = 1.0;
    
    @Override
    public V put(K key, V value){
        V oldValue = super.put(key, value);
        
        if(size() > maps.size() * FACTOR){
            rehash();
        }
        return oldValue;
    }
    
    public void rehash(){
        List<MyLinearMap<K,V>> oldMaps = maps;
        
        // make more maps
        makeMaps(maps.size() * 2);
        
        for(MyLinearMap<K,V> map : oldMaps){
            for(Map.Entry<K, V> entry : map.getEntires()){
                put(entry.getKey(), entry.getValue());
            }
        }
    }
    ...
 
}

유일한 오버라이드메소드는 put으로 부모클래스(MyBtterMap)의 put 메서드를 호출한 후 재해쉬(rehash)가 필요한지 확인한다.

size() => 엔트리의 전체 개수 n 반환

maps.size() => 내장된 맵의 개수 k를 반환

상수 FACTOR => 하위 맵당 최대 엔트리 개수를 결정함

n/k > FACTOR == n > k * FACTOR  (size() > maps.size() * FACTOR)

하위 맵당 엔트리의 개수가 임계치를 초과할 경우 rehash메서드를 호출

하위 맵의 엔트리 개수가 n/k에 비례하고, k가 n에 비례하여 늘어난다면 MyBetterMap 클래스의 핵심 메서드도 상수시간이 된다. (containsKey, get, remove ...)

put은 재해시 할 필요가 없으면 상수시간이지만, 재해시를 해야 한다면 선형의 시간을 갖는다.

하지만 호출을 평균하면 MyHashMap.put은 상수시간을 갖게 된다. ( ArrayList의 add 메서드의 분류법을 참고 )

MyHashMap 클래스 고치기

MyHashMap에는 MyBetterMap 에서 상속한 size 메서드가 있는데,  n이 증가함에 따라 선형의 시간복잡도를 갖기 때문에

size 메서드를 호출하는 put 메서드도 선형이 된다. (put 메서들르 상수 시간으로 만드려고 하는 일은 헛일이 됨)

=> 해결법 엔트리 개수를 인스턴스 변수에 저장하고, 엔트리 개수를 변경하는 메서드를 호출할때마다 그 값을 업데이트