[JAVA] Map 구현

학습 내용

Map의 구조를 알수 있습니다.

 

• 추가
  • key, value 추가
• 조회
  • key 에 해당하는 value 값 조회
• 삭제
  • key 에 해당하는 entry 값 삭제

---

MyEntry.class

    private K key;
    private V value;

    public MyEntry(K key, V value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public K getKey() {
        return key;
    }

    @Override
    public V getValue() {
        return value;
    }

    @Override
    public V setValue(V value) {
        return this.value = value;
    }

}

Entry 인터페이스를 구현하였습니다.

 

---

MyMap 구현

 

필드

List<MyEntry> entries = new ArrayList<>();

Entry 타입으로만 받는 인스턴스를 생성합니다.

 

---

기능 구현하기 앞서 헬퍼 메서드를 구현

private MyEntry findEntry(Object target) {
    for (MyEntry 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);
}

List에 담겨 있는 entry의 정보 key 를 target 객체와 비교하여 리턴하는 기능입니다.

 

시간 복잡도는 O(n) 으로 보여집니다.

---

추가

1. key, value 추가하기

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

입력 받은 key 가 존재 하는 지 검사를 하고 null 이라면 List 에 새로운 Entry를 생성하고 key, value 를 저장합니다.

key 가 존재 한다면 입력 받은 value 값만 entry 에 저장합니다.

 

findEntry() 메서드가 선형이므로 O(n) 이라는 시간 복잡도를 가집니다.

---

조회

1. key 에 해당하는 value 값 조회

public V get(Object key) {
    MyEntry entry = findEntry(key);
    if (entry == null) {
        return null;
    }
    return (V) entry.getValue();
}

중복된 key 가 있는지 검사하고 null 이면 null 을 리턴 합니다.

그렇지 않다면 해당 key 의 value 를 리턴 합니다.

 

시간 복잡도는 O(n) 입니다.

---

삭제

1. key 에 해당하는 entry 값 삭제

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

해당 key 를 찾고 List 에 담겨져있는 entry 의 정보를 삭제합니다.

 

시간 복잡도는 O(n) 입니다.