자바의 자료구조 (Collection)

Collection 정리

자바의 데이터를 다루는 자료구조를 모아놓은 인터페이스

• List : 순서가 있고 중복 저장이 가능하다.
• Set : 순서가 없고 중복 저장이 불가능하다.
• Map : Collection과 상속관계는 아님. Key-Value 형태로 자료를 저장한다.

특징은 위와 같고 오늘은 그동안 궁금했던 내용들을 정리해보겠다.

Iterable과 Iterator

자바를 처음 공부할 때 이 개념이 잘 이해가 안되었다. 다시 알아보자.

public interface Iterable<T> {
    ...
    Iterator<T> iterator();
    ...
}

Collection Framework의 최고 상위 인터페이스인 Collection이 Iterable 인터페이스를 상속받는다.
Iterable 인터페이스를 구현하면 반드시 iterator()를 구현해야 하는데 iterator()은 뭘까?
우선 iterator()의 반환타입인 Iterator 인터페이스의 구성을 살펴보자.

public interface Iterator<E> {

    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    ...
}

Iterator 인터페이스는 위와 같은 메서드를 포함하고 있다.
다음 값이 있는지 여부확인과 다음 값을 반환하는 메서드로 추정되는 추상 메서드가 정의되어 있다.

 

Iterable을 상속한 이유는 Collection의 자식 클래스에서 iterator()메서드를 구현하도록 하기 위해서다.
iterator()메서드를 구현하기 위해서는 Iterator 인터페이스도 구현해야 한다.

즉, Collection의 자식 클래스들은 각자 맞는 Iterator를 구현하여서 어떤 클래스든 동일한 방식으로 데이터를 읽어오기 위해서 Iterator를 사용하는 것이다. 모두가 Iterator를 구현하면 어떤 클래스든 hasNext()로 다음 노드에 데이터가 있는지 확인할 수 있다.

public class ArratList ... {
    ... 
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        // prevent creating a synthetic constructor
        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }
        ...
    }
}

ArrayList의 예시이다. iterator()를 호출하면 Itr객체를 생성한다.
Itr클래스는 Iterator를 구현한 클래스라는 것을 알 수 있다.

HashSet

Set을 사용하면 일반적으로 HashSet 클래스를 사용한다. HashSet은 어떤 구조로 되어있을까?

public class HashSet ... {
    ...
    public HashSet() {
        map = new HashMap<>();
    }
    ...
}

기본적으로 생성하면 HashMap 객체를 생성하는 모습을 볼 수 있다.
뒤에 추가나 삭제는 어떻게 이루어질까?

public class HashSet ... {
    ...
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    ...
}

마찬가지로 생성할 때 만든 HashMap 객체를 이용해서 put, remove를 하고있다.
이때 HashSet의 입력값인 e는 HashMap에서 Key의 자리에 들어가는 것을 볼 수있다.
Map의 Key값은 중복이 불가능하므로 이 특성을 이용해서 HashSet에서 중복을 막능 기능을 구현하였다.

HashMap

그렇다면 HashMap은 어떻게 구성되어 있을까?
HashMap의 코드는 아직 필자가 보기에는 조금 힘들었다. 그래서 간단히 작동원리만 알아보자.

 

우선 HashMap은 배열로 데이터를 저장한다.
배열의 index가 key역할을 하고 데이터가 value역할을 한다.
value는 그렇다쳐도 key는 정수일수도 있지만 문자열도 가능하다.
어떻게 key를 정수의 index로 변경할 수 있을까? 해시함수를 사용한다.

해시함수

임의의 길이를 가지는 임의의 데이터를 고정된 길이를 가지는 데이터로 매핑하는 단방향 함수다.

 

해시함수를 이용해서 index가 가능한 정수로 key값을 변경한다.
만약 다른 key값이 해시함수를 거쳐 같은 index로 출력되면 어떻게 할까?

그런 경우에는 LinkedList의 노드를 사용해서 데이터를 연결해서 저장한다.
index가 결정되고 그 인덱스에 저장된 데이터와 노드들에 중복된 값이 있으면 데이터를 덮어쓰고 없으면 가장 뒤에 노드를 생성해서 데이터를 저장한뒤 연결한다.

 

Map은 아직 분석이 더 필요하다고 생각된다.

List

List는 이전에 작성한 글이 있으니 그 글을 참고하자.

 

선형 자료구조