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

Map 인터페이스의 구현 (MyLinearMap)

---

Map 인터페이스의 여러 구현 중 하나는 해시 테이블(hash table)에 기반을 두는데 지금까지 발명된 자료구조 중 단연 으뜸이다.

해시 테이블을 설명하기에 앞서 키-값 쌍으로 이루어진 리스트를 사용하여 간단한 Map 인터페이스를 구현해 본다.

MyLinearMap 객체에는 단일 인스턴스 변수 entries가 있는데 Entry객체들을 담은 ArrayList이다.

(Entry 클래스는 MyLinearMap의 inner class)

 

public class MyLinearMap<K, V> implements Map<K, V> {
    // MyLinearMap 기본 구현
    private List<Entry> entries = new ArrayList<>();
    
    public class Entry implements Map.Entry<K, V>{
        private K key;
        private V value;
        
        public Entry(K key, V value){
            this.key = key;
            this.value = value;
        }
        @Override
        public K getKey() {
            return this.key;
        }
        @Override
        public V getValue() {
            return this.value;
        }
        @Override
        public V setValue(V value) {
            this.value = value;
            return value;
        }
    }
 
    ....
 
}

 

MyLinearMap 분석하기

---

핵심메서드인 findEntry, equals 메서드 구현

private Entry findEntry(Object target){
    for(Entry entry : entries){
        if(equals(target, entry.getKey())){
            return entry;
        }
    }
    return null;
}
 
private boolean equals(Object target, Object obj){
    if(target == null){
        return obj == null;
    }
    return target.equals(obj);
}

 

findEntry메서드는 운이 좋으면 처음에 원하는 키를 얻을 수 있지만 일반적으로 검색해야 할 엔트리 개수는 n에 비례한다. 따라서 findEntry 메서드는 선형시간이다.

equals 메서드는 target크기에 의존하지만, 엔트리 개수에 해당하는 n에 의존하지 않기 때문에 상수시간이다.

 

put, get 메서드 구현

@Override
public V put(K key, V value) {
    Entry entry = findEntry(key);
    if(entry == null){
        entries.add(new Entry(key, value));
        return null;
    }else{
        V oldValue = entry.value;
        entry.setValue(value);
        return oldValue;
    }
}
 
@Override
public V get(Object key) {
    Entry entry = findEntry(key);
    if(entry == null){
        return null;
    }
    return entry.getValue();
}

 

put, get 메서드는 findEntry를 호출한 후 모두 상수 시간을 갖기 때문에 선형시간 O(n)을 갖게 된다.

 

remove 메서드 구현

@Override
public V remove(Object key) {
    Entry entry = findEntry(key);
    if(entry == null){
        return null;
    }else{
        V value = entry.getValue();
        entries.remove(entry);
        return value;
    }
}

 

findEntry 메서드가 선형시간을 갖고,

entries.remove 메서드가 ArrayList의 시작이나 중간에서 요소를 제거해야 할 수도 있고 이 메서드가 선형이 될수도 있다.

두 개의 선형 연산은 선형이기 때문에 여전히 선형시간이다. O(2n) -> O(n)

 

요약하면 핵심 메서드는 모두 실행시간이 선형이다. O(n) (그래서 책에선 이름을 MyLinearMap으로 지었다고 한다...)

엔트리 개수가 적다면 이 구현은 쓸만하지만 엔트리 개수가 늘어나면 개선되어야할 필요성이 있다.  사실 모든 핵심 메서드가 상수 시간인 Map의 구현도 존재한다.

상수시간이 어떻게 가능할까?

1. 엔트리를 하나의 커다란 List에 저장하는 대신에 다수의 작은 리스트로 쪼갬. 각 키에 대해서 해시 코드(hash code)를 사용하여 어느 리스트를 사용할지 선택
2. 하나의 큰 리스트 대신 다수의 작은 리스트를 사용하는 것이 더 빠르지만, 증가 차수를 개선하지는 못함. 핵심 연산은 여전히 선형. 하지만 다른 묘수가 있는데, 리스트의 개수를 늘려서 리스트당 엔트리 개수를 제한할 수 있다면 결과는 상수 시간 맵이 됨

지금 당장은 잘 와닿지가 않을 수도 있는데, 뒤에 이어지는 포스팅을 보면 이해하는데 도움이 될것이다.

 

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