[DataStructure] 맵(Map) 구현

맵 인터페이스

/**
 * @author andpact
 * @param <K> the type of key elements in this map
 * @param <V> the type of value elements in this map
 */
public interface MapInterface<K, V> {
    /**
     * 지정된 Key를 가진 Value를 삽입합니다.
     * @param key Key로 사용할 요소
     * @param val Value로 사용할 요소
     */
    void add(K key, V val);

    /**
     * 지정된 Key를 가진 Value를 반환합니다.
     * @param key Key로 사용할 요소
     * @return 지정한 Key를 가진 Value
     */
    V get(K key);

    /**
     * 지정된 Key를 가진 Value를 지정된 Value로 변경합니다.
     * @param key Key로 사용할 요소
     * @param val 새 Value로 사용할 요소
     */
    void set(K key, V val);

    /**
     * 지정된 Key를 가진 Value를 제거합니다.
     * @param key Key로 사용할 요소
     */
    void remove(K key);

    /**
     * 모든 요소를 제거합니다.
     */
    void clear();

    /**
     * 지정된 Value를 포함하는지 조회합니다.
     * @param val 포함 여부를 조회할 요소
     * @return 지정된 요소르 포함하고 있다면 true를 반환
     */
    boolean contains(V val);

    /**
     * map이 비었는지 조회합니다.
     * @return map이 비었다면 true를 반환
     */
    boolean isEmpty();

    /**
     * 요소의 개수를 반환합니다.
     * @return 요소의 개수
     */
    int size();
}

생성자

public class Map<K, V> implements MapInterface<K, V>{
    private K[] keyArr;
    private V[] valArr;
    private final static int DEFAULT_CAPACITY = 10;
    private int size;

    public Map() {
        keyArr = (K[]) new Object[DEFAULT_CAPACITY];
        valArr = (V[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }
}

CREATE 메서드

@Override
public void add(K key, V val) {
    resize();
    for (int i = 0; i < size; i++) {
        if (keyArr[i].equals(key)) return;
    }
    keyArr[size] = key;
    valArr[size] = val;
    size++;
}

READ 메서드

@Override
public V get(K key) {
    for (int i = 0; i < size; i++) {
        if (keyArr[i].equals(key)) {
            return valArr[i];
        }
    }
    return null;
}

UPDATE 메서드

@Override
public void set(K key, V val) {
    for (int i = 0; i < size; i++) {
        if (keyArr[i].equals(key)) {
            valArr[i] = val;
        }
    }
}

DELETE 메서드

@Override
public void remove(K key) {
    for (int i = 0; i < size; i++) {
        if (keyArr[i].equals(key)) {
            for (int j = i; j < size - 1; j++) {
                keyArr[i] = keyArr[i + 1];
                valArr[i] = valArr[i + 1];
            } size--;
            resize();
            return;
        }
    }
}

@Override
public void clear() {
    keyArr = (K[]) new Object[DEFAULT_CAPACITY];
    valArr = (V[]) new Object[DEFAULT_CAPACITY];
    size = 0;
}

기타 메서드

@Override
public boolean contains(V val) {
    for (int i = 0; i < size; i++) {
        if (valArr[i].equals(val)) return true;
    }
    return false;
}

@Override
public boolean isEmpty() {
    return size == 0;
}

@Override
public int size() {
    return size;
}

private void resize() {
    if (size == keyArr.length){
        keyArr = Arrays.copyOf(keyArr, keyArr.length * 2);
        valArr = Arrays.copyOf(valArr, valArr.length * 2);
    }
    else if (size < keyArr.length / 2) {
        keyArr = Arrays.copyOf(keyArr, Math.max(DEFAULT_CAPACITY, keyArr.length / 2));
        valArr = Arrays.copyOf(valArr, Math.max(DEFAULT_CAPACITY, valArr.length / 2));
    }
}