배열array은 인덱스로 데이터를 빠르게 찾는 데이터 구조data structure입니다. 그런데 인덱스는 숫자이기 때문에, 배열은 숫자를 데이터로 보내는 매핑mapping, 즉 숫자가 도메인domain인 함수로 바라볼 수도 있습니다.

배열을 이용해서 출석부를 만든다고 해봅시다. $n$ 명의 학생들에게 $1$번부터 $n$번까지 순번을 매긴다면, 순번을 인덱스로 써서 배열로 출석부를 구현할 수 있습니다. 즉 $i$ 번째 원소가 $i$ 번 학생의 출석 여부를 기억하는 것입니다. 이때 배열은 순번 집합 $\{1, \dots, n\}$을 출석 여부 $\{\textit{true}, \textit{false}\}$로 보내는 함수 $f$의 구현으로도 볼 수 있습니다.

그런데 어떤 사람이 출석부를 쓰다가 이런 요구를 했다고 해봅시다.

• 전학 때문에 학생을 줄이거나 늘릴 수 있어야 한다.

• 순번 대신 이름을 쓸 수 있어야 한다.

첫 번째 요구사항은, $f$를 바꿀 수 있게끔 요구하는 것입니다. 두 번째 요구사항은, $f$의 도메인이 이름이기를 바라는 것입니다. 즉 배열로 말하자면, 이름을 일종의 인덱스로 쓸 수 있어야 합니다. 여기서는 나아가서 이름 뿐만 아니라 다른 것도 인덱스가 될 수 있어야 한다고 문제를 일반화해보겠습니다.

위와 같은 요구를 만족하는 데이터 구조는, 인덱스를 임의의 타입으로 일반화한 배열로 생각할 수 있습니다. 그래서 연관 배열associative array이라고도 하고, 인덱스 대신 키key라고 부릅니다. 다른 이름으로는 딕셔너리dictionary가 있는데, 파이썬Python에서 같은 이름으로 존재하는 데이터 타입이 바로 그것입니다. 여기서는 이 이름으로 부르겠습니다.

출석부 문제는 딕셔너리로 해결할 수 있습니다. 딕셔너리는 다음 연산을 갖는 ADTabstract data type로 정의합니다.

• get(key): 키 key와 연관된 값을 가져옵니다.

• set(key, value): 키 key를 값 value에 연관시킵니다. 기존에 연관된 값이 있었다면 버리고 value로 바꿉니다.

• remove(key): 키 key와 연관된 값을 없앱니다.

• getSize(): 연관된 값의 개수를 가져옵니다.

앞으로의 내용을 통해, 딕셔너리를 구현해보며 내부 동작을 이해할 수 있게 됩니다. 여기서는 세 가지 방법으로 구현해볼 것인데, 첫 번째는 링크드 리스트linked list로 만드는 것입니다. 연관 리스트association list라고도 부르며 비교적 간단합니다. 두 번째와 세 번째는 배열을 이용하는데, 각각 체이닝chaining과 오픈 어드레싱open addressing이라는 방법으로 구현할 것입니다. 이를 통해 각 방법을 비교해보며 장단점을 알 수 있을 것입니다. 마지막으로, 다양한 프로그래밍 언어에서 지원하는 맵map과 셋set이라는 데이터 구조를 어떻게 딕셔너리로 만들 수 있는지 볼 것입니다.

연관 리스트로 만드는 딕셔너리

딕셔너리는 데이터를 일렬로 둬서 간단히 만들 수 있습니다. 데이터의 추가는 맨 앞에 놓는 것으로 하고, 데이터를 찾는 것은 처음부터 끝까지 하나씩 확인하는 시퀀셜 서치sequential search를 이용합니다.

이 방법의 특징은 랜덤 엑세스가 필요 없고, 데이터 추가를 위해 첫 자리를 기억해야 한다는 것입니다. 따라서 링크드 리스트linked list를 사용하기 적합한 자리입니다.

여기서 리스트의 연산을 다음과 같이 정의합시다.

• get(predicate): 조건 predicate를 만족하는 첫 번째 데이터를 가져옵니다.

• has(predicate): 조건 predicate를 만족하는 데이터가 있으면 참, 아니면 거짓을 가져옵니다.

• prepend(data): 리스트 앞에 데이터 data를 추가합니다.

• change(predicate, data): 조건 predicate를 만족하는 첫 번째 데이터를 data로 수정합니다.

• remove(predicate): 조건 predicate를 만족하는 첫 번째 데이터를 삭제합니다.

• getSize(): 데이터의 개수를 가져옵니다.

• isEmpty(): 데이터가 하나도 없는지 여부를 가져옵니다.

구현 시 노드의 존재를 감춰서 사용자가 데이터에 신경쓸 수 있도록 만들겠습니다. 이러한 연산을 사용하는 예시는 다음 그림과 같습니다.

그러면 이것으로 딕셔너리의 ADT를 어떻게 만들 수 있을까요? 먼저, 딕셔너리의 get() 연산은 다음 수도코드처럼 리스트의 get() 연산에 맡길 수 있습니다.

set()은 다음과 같이 두 가지 역할을 맡습니다. 이미 키와 연관된 값이 있으면 새 값에 연관시키고, 없으면 새롭게 추가합니다.

remove()는 단순히 리스트 조작에 맡깁니다. 간단하므로 직접 만들어보는 것으로 하고 넘어가겠습니다.

이렇게 만드는 딕셔너리는 키와 연관된 값이 리스트로 존재하므로 연관 리스트association list라고 부릅니다. 연관 리스트에 $n$ 개의 데이터가 있다면, 모든 연산은 최악의 경우에 $n$ 개의 노드를 방문하므로 $\Theta(n)$의 시간이 걸립니다.

링크드 리스트 구현하기

링크드 리스트는 이전 글에서도 구현해봤지만, 이번에는 서큘러 링크드 리스트circular linked list라고 하는 다른 종류를 만들어보려고 합니다. 모든 노드를 순환시켜 연결하기 때문에 이런 이름을 가집니다.

서큘러 리스트는 맨 뒤의 노드가 맨 앞의 노드를 가리키기 때문에, 모든 노드가 다음 노드를 가리킵니다 이러한 일관성 덕분에 다음 노드가 존재하는지 따로 확인할 필요가 없어지므로 구현이 간단해집니다.

여기서는 리스트의 끝을 나타내는 더미dummy 노드를 만들 것입니다. 센티넬sentinel이라고도 부르는 이것 또한 구현 코드를 줄여줍니다. 왜냐면 리스트가 적어도 하나의 노드를 갖게 되므로, 구현 시 노드가 없는 경우를 따로 확인해야 할 필요가 사라지기 때문입니다.

이제 앞서 정의한 리스트의 연산을 만들어볼 차례입니다.

리스트 맨 앞에 값을 추가하는 prepend() 연산은, 새 노드를 마지막 노드 다음에 끼워넣는 것으로 만들 수 있습니다.

노드 삭제는 그 이전의 노드를 찾아서, 삭제할 노드의 다음 노드에 연결합니다.

따라서 이전 노드를 찾는 연산을 준비해봅시다. 다음 수도코드는 조건을 만족하는 노드의 이전 노드를 찾습니다.

이를 통해 노드 삭제를 만듭니다.

이와 비슷한 방식으로 남은 get(), has(), change() 연산 또한 만들 수 있습니다. 이것은 직접 해보는 것으로 남기고 넘어가겠습니다.

링크드 리스트 구현하기

자바로 링크드 리스트를 구현해봅시다. 먼저, 노드는 이전 글에서 만든 클래스를 그대로 이용합니다. 즉 아래와 같이 데이터와 다음 노드를 가집니다.

class LinkedNode<T> {
  private T data;
  private LinkedNode<T> next;

  public LinkedNode(T data, LinkedNode<T> next) {
    this.data = data;
    this.next = next;
  }

  public LinkedNode() {
    this(null, null);
  }

  public T getData() {
    return this.data;
  }

  public LinkedNode<T> getNext() {
    return this.next;
  }

  public void setData(T data) {
    this.data = data;
  }

  public void setNext(LinkedNode<T> next) {
    this.next = next;
  }
}

이 노드를 이용해 서큘러 링크드 리스트 클래스를 만들 수 있습니다. 생성자에서는 마지막 노드를 나타내는 더미 노드를 초기화합니다.

public class CircularLinkedList<T> {
  private LinkedNode<T> end;

  public CircularLinkedList() {
    // sentinel
    this.end = new LinkedNode<>();
    // the next of the end is always the head
    this.end.setNext(this.end);
  }

  // ...
}

prepend(), findPrev(), remove() 연산은 수도코드를 그대로 옮겨서 구현합니다. 그 중에 findPrev() 연산은 이렇게 만들 수 있습니다.

  private LinkedNode<T> findPrev(Predicate<T> pred) {
    LinkedNode<T> prev = this.end; // end is just before the head

    while (true) {
      LinkedNode<T> node = prev.getNext();
      if (node == this.end) {
        return null;
      }

      if (pred.test(node.getData())) {
        return prev;
      }

      prev = node;
    }
  }

이 메소드를 이용해 get(), has(), change() 연산도 만들 수 있습니다. 이것들은 직접 만들어보는 것으로 남기고 넘어가겠습니다.

노드의 개수를 나타내는 size 필드를 추가해서 getSize() 연산과 isEmpty() 연산을 만들 수 있습니다.

public class CircularLinkedList<T> {
  // ...

  private int size; 

  // ...
}

노드를 추가하거나 삭제할 때도 size 필드에 반영합니다.

  public void prepend(T data) {
    // ...

    this.size++; 
  }

  public void remove(Predicate<T> pred) {
    // ...

    this.size--; 
  }

이제 getSize()과 isEmpty() 메소드를 구현할 수 있습니다.

  public int getSize() {
    return this.size;
  }

  public boolean isEmpty() {
    return this.size == 0;
  }

각 메소드는 다음과 같이 테스트할 수 있습니다.

  @Test
  public void testStringList() {
    // initailize
    CircularLinkedList<String> list = new CircularLinkedList<>();
    list.prepend("foo");
    list.prepend("bar");
    list.prepend("quux");

    // query
    assertEquals("quux", list.get(data -> true)); // first data
    assertEquals(true, list.has(data -> data.length() == 4));

    // size
    assertEquals(3, list.getSize());
    assertEquals(false, list.isEmpty());

    // modify
    list.change(data -> data.equals("bar"), "baz");
    assertEquals(true, list.has(data -> data.equals("baz")));
    list.remove(data -> data.equals("quux"));
    assertEquals(false, list.has(data -> data.equals("quux")));
  }

연관 리스트로 딕셔너리 만들기

이렇게 만든 링크드 리스트로 연관 리스트를 만들어 딕셔너리를 구현해보겠습니다. 먼저, 딕셔너리의 ADT를 그대로 따라서 인터페이스를 정의합니다.

public interface Dictionary<K, V> {
  public void set(V value);
  public V get(K key);
  public void remove(K key);
  public int getSize();
}

인터페이스의 set() 연산을 보면, 수도코드와는 달리 키를 받지 않습니다. 그 이유는 인터페이스를 좀더 간단히 하기 위함입니다. 대신 키는 값에서 알아낼 수 있다고 가정하고, 연관 리스트를 초기화할 때 값에서 키를 찾는 함수 getKey를 받도록 하겠습니다. 나중에 이런 제한 조건을 없앤 맵과 셋을 만들어볼 것입니다.

public class AssocList<K, V> implements Dictionary<K, V> {
  private CircularLinkedList<V> list;
  private Function<V, K> getKey;

  public AssocList(Function<V, K> getKey) {
    this.list = new CircularLinkedList<>();
    this.getKey = getKey;
  }

  // ...
}

연관 리스트의 각 연산은 수도코드를 그대로 옮겨 만들 수 있습니다. 예를 들어, set() 연산은 다음과 같습니다.

  public void set(V value) {
    K key = this.getKey.apply(value);

    if (this.list.has(this.hasEqualKey(key))) {
      this.list.change(this.hasEqualKey(key), value);
    } else {
      this.list.prepend(value);
    }
  }

방금 언급했듯이, 키는 생성자에서 받았던 getKey로 알아냅니다. 이렇게 키 key와 연관된 값을 찾아야 합니다. 보조 메소드 hasEqualKey()는 값을 받아 키와 연관되어 있는지 확인하는 함수를 리턴합니다. 즉 함수를 리턴하는 고차 함수higher-order function입니다.

  private Predicate<V> hasEqualKey(K key) {
    return element -> this.getKey.apply(element).equals(key);
  }

이것은 리스트의 메소드에서 조건으로 활용할 수 있으므로, 구현이 다음과 같이 간단해집니다.

  public V get(K key) {
    return this.list.get(this.hasEqualKey(key));
  }

remove()도 이와 비슷하므로, 직접 만들어보는 것으로 남기겠습니다. getSize()도 어렵지 않으므로 마찬가지입니다.

이렇게 만든 연관 리스트는 딕셔너리로서 기능하고, 출석부를 만들 수 있는 데이터 구조가 됩니다. 실제로 테스트 코드를 통해 출석부를 만들어보겠습니다. 먼저, 학생 클래스가 이름과 출석 여부를 갖도록 정의합니다.

  private class Student {
    private String name;
    private boolean attended;

    public Student(String name, boolean attended) {
      this.name = name;
      this.attended = attended;
    }

    public String getName() {
      return this.name;
    }

    public boolean getAttended() {
      return this.attended;
    }
  }

그러면 출석부는 다음과 같이 딕셔너리로 나타낼 수 있습니다.

  @Test
  public void testAttendance() {
    // initialize students
    Dictionary<String, Student> table = new AssocList<>(Student::getName);
    table.set(new Student("John", false));
    table.set(new Student("Jane", false));
    table.set(new Student("Tom", false));

    // query
    assertEquals(false, table.get("John").getAttended());

    // update
    table.set(new Student("Jane", true));
    assertEquals(true, table.get("Jane").getAttended());

    // remove
    table.remove("Tom");
    assertEquals(null, table.get("Tom"));

    // size
    assertEquals(2, table.getSize());
  }

이렇게 출석부 문제를 해결했습니다. 이 출석부는 얼마든지 줄이거나 늘일 수 있고, 순번 대신 이름으로 출석 여부를 알 수 있습니다.

더 빠른 딕셔너리 생각해보기

연관 리스트로 딕셔너리를 만들긴 했지만, 앞서 설명한대로 get(), set(), remove() 연산 모두 최악의 경우 $\Theta(n)$의 시간이 걸립니다.

혹시 더 빠르게 만들 수는 없을까요? 만약 시퀀셜 서치 대신 바이너리 서치를 쓴다면 어떨까요? 바이너리 서치는 랜덤 엑세스가 필요하므로, 내부적으로 링크드 리스트 대신 배열이 필요합니다. 이렇게 만든 딕셔너리의 get() 연산은 $\Theta(\lg n)$의 시간으로 줄어들 수 있습니다. 하지만 데이터를 소트된 채로 유지해야 하므로, 이런 결과를 가져옵니다.

• 키의 순서를 생각할 필요가 생깁니다. 소트는 순서가 주어져야 하기 때문입니다. 단순히 이름으로 학생을 찾고 싶은 출석부의 경우, 굳이 이름의 순서까지 신경써야 할 이유는 없습니다. 연관 리스트로 구현할 때는 이런 걸 생각할 필요가 없었습니다.

• set(), remove() 연산은 여전히 최악의 경우에 $\Theta(n)$의 시간이 걸립니다. 예를 들어, set()으로 추가할 값이 맨 앞에 와야할 때, 배열에서 나머지 값을 한 자리씩 뒤로 옮겨야 하기 때문입니다. remove()로 맨 앞의 값을 삭제할 때도 비슷한 일이 일어납니다.

한편, 배열을 다른 식으로 사용해서, 세 연산들이 전부 평균적으로 $\Theta(1)$의 시간이 들도록 만들 수 있습니다. 이후 알아볼 딕셔너리의 구현 방법은 이런 특징을 가지는 것입니다.

체이닝으로 만드는 딕셔너리

앞으로의 내용을 통해, 딕셔너리를 어떻게 배열로 만들 수 있을지 알아볼 것입니다. 그리고 먼저 간단한 구현부터 시작해 개선을 이어서 해볼 것입니다.

딕셔너리를 배열로 만든다면, 두 가지 문제를 해결해야 합니다.

1. 키를 인덱스로 바꿔야 합니다. 배열은 인덱스로 접근할 수 밖에 없기 때문입니다. 이 문제는 키를 인덱스로 바꾸는 해시 함수hash function로 해결할 것입니다. 키 $k$에 대한 해시 함수 $h$의 결과값 $h(k)$는 해시 값hash value이라고 부릅니다. 그리고 해시 값을 이용해 구현한 딕셔너리를 해시 테이블hash table이라고 부릅니다.

2. 그렇다면, 키가 다르지만 해시 값이 같을 때를 처리해야 합니다. 다시 말해, 배열 상 접근할 인덱스가 같더라도, 그 중에 키와 연관된 하나의 값을 찾을 방법이 필요합니다. 이렇게 해시 값이 같은 경우를 해시 충돌hash collision이라고 하고, 올바른 값을 찾는 방법을 충돌 해소collision resolution이라고 부릅니다.

충돌 해소가 중요한 이유는, 해시 충돌이 비교적 빈번하게 일어나기 때문입니다. 키가 배열의 6% 남짓 있더라도 그 확률은 50%를 넘게 되기 때문입니다. (생일 문제birthday problem라고 알려져 있는 것이기도 합니다.)

충돌 해소의 한 방법인 체이닝chaining은, 같은 해시를 가지는 값을 링크드 리스트로 모아서 보관하는 것입니다. 먼저 용어 정리를 하자면, 배열의 각 원소를 슬롯slot이라고 부르고, 슬롯에 있는 링크드 리스트를 체인chain이라고 부릅니다. 체이닝이란 딕셔너리에 값을 추가할 때마다, 키의 해시 값에 해당하는 슬롯으로 가서 체인에 넣는 것입니다. 이후 값을 찾기 위해서는 해시 값으로 슬롯에 접근하고, 체인에 있는 키를 일일이 확인하며 값을 가져오게 됩니다.

그런데 체인에서 값을 찾는 과정은 연관 리스트의 경우와 같습니다. 사실 체이닝이란, 시퀀셜 서치로 찾을 대상을 해시값으로 좁힌 것입니다. 따라서 체인을 연관 리스트로 구현하면, 딕셔너리 또한 여러 개의 연관 리스트에 불과하게 됩니다.

예를 들어, 딕셔너리의 get() 연산은 연관 리스트의 get() 연산에 맡길 수 있습니다.

set() 연산도 이와 같습니다.

remove() 연산 또한 비슷하므로, 직접 해보는 것으로 남기고 넘어가겠습니다.

시간 복잡도 구하기

체이닝으로 딕셔너리는 시간 복잡도가 얼마나 될까요? 결론부터 말하면, $n$ 개의 값에 대해 get()은 평균의 경우 $\Theta(n)$을 갖습니다. (물론 나중에 $\Theta(1)$로 개선할 것입니다.)

그런데 평균의 경우를 말하려면, 먼저 그 평균이란 무엇인지, 즉 입력값의 어떤 분포를 말하는 것인지 정해야 합니다. 체이닝의 경우 입력값은 곧 해시 값이므로, 해시 함수가 어떻게 동작하는지 결정해야 할 필요가 있습니다.

여기선 문제를 간단히 하기 위해, 해시 함수가 두 가지 이상적인 성질을 가진다고 가정할 것입니다.

• 해시 함수는 해시 값을 균등하게 분포시킵니다. 즉 가능한 $m$ 가지의 해시 값이 있다면, 그 중 하나로 선택할 확률은 전부 $1/m$입니다. 이때 해시 함수가 유니폼uniform하다고 부릅니다. (확률 분포가 균등uniform하기 때문입니다.)

• 어떤 키로부터 해시 값을 구했다고 하더라도, 이것이 다른 키의 해시 값을 결정하는 데에 영향을 미치지 않습니다. 즉 하나의 해시 값은 다른 키의 해시 값을 미리 유추하기 위한 어떤 정보도 주지 못한다는 뜻입니다. 즉 확률론probability theory 용어로 독립independence이라는 뜻입니다.

해시 함수의 가정에서 확률을 말했기 때문에, 시간 복잡도 분석은 이전 글처럼 확률적 분석probabilistic analysis이 됩니다. 그리고 유니폼하다는 가정으로부터, 딕셔너리에 있는 값 $v$와 체인 $m$ 개에 대해, 어떤 체인이 $v$를 갖고있을 확률도 $1/m$이 됩니다. 왜냐면 그 값의 키가 그 체인의 인덱스를 해시 값으로 가질 확률이 $1/m$이기 때문입니다.

위 사실을 기호로 나타내봅시다. 딕셔너리에 $n$ 개의 값과 $m$ 개의 체인이 있다고 하고, 각 값에 딕셔너리에 추가된 순서대로 순번을 매기고, 체인에는 임의로 순번을 매겼다고 합시다. 그러면 $1 \leq i \leq n$과 $1 \leq j \leq m$에 대해, 방금의 확률 $1/m$은 $i$ 번째 값이 $j$ 번째 체인에 속할 확률을 말하는 것입니다.

그리고 바로 그런 경우에 인디케이터 랜덤 변수 $I_{ij}$가 $1$이고, 그렇지 않으면 $0$이라고 합시다. 즉 $I_{12}$란 첫 번째 값이 두 번째 체인에 있을 때만 $1$인 인디케이터입니다. 그러면 인디케이터는 기댓값이 확률과 같다는 특징이 있으므로, 인디케이터의 기댓값 $E[I_{ij}]$은 $1/m$이 됩니다.

이어서 체인의 길이는 기댓값이 $n/m$이라는 사실도 알 수 있습니다. $j$ 번째 슬롯의 길이를 $l_j$라고 합시다. 이것은 $j$ 번째 슬롯에 속한 값의 개수와 같으므로 $l_j = \sum_{i=1}^{n} I_{ij}$ 입니다. 따라서 길이의 기댓값 $E[l_j]$를 다음과 같이 얻게 됩니다.

즉 평균 길이 $E[l_j]$는 값의 개수 $n$을 체인의 개수 $m$으로 나눈 것이라는 뜻이고, 직관적으로 이해되는 결과이기도 합니다.

한편, $m$은 딕셔너리가 내부적으로 쓰는 배열의 크기이기도 합니다. 따라서, 이전 글에서 알아봤던 다이나믹 배열dynamic array처럼, 배열의 크기 대비 값의 개수를 나타내는 로드 팩터load factor $\alpha$를 $n/m$으로 정의할 수 있습니다. 그러면 $E[l_i] = \alpha$, 즉 길이의 기댓값은 곧 로드 팩터가 됩니다. 즉, 값의 개수가 $n=30$이고 체인의 개수가 $m=10$이면, 로드 팩터는 $\alpha = 30/10 = 300\%$이고, 평균 길이도 이와 같다는 뜻입니다.

이제 get() 연산의 시간 복잡도를 구해봅시다. 해시 함수가 해시 값을 구할 때 시간 복잡도는 $c_h = \Theta(1)$, 키를 비교할 때는 $c_k = \Theta(1)$이라고 하겠습니다. 여기서는 두 가지 경우의 시간 복잡도에 관심이 있는데, get() 연산이 값을 찾는 경우의 $T_s$와 못 찾는 경우의 $T_f$입니다.

값을 못 찾는 경우의 $T_f$는 기댓값을 간단히 구할 수 있습니다. get() 연산은 해시 값을 계산해 슬롯에 접근하고, 체인의 모든 노드마다 키를 확인합니다. 체인의 길이는 기댓값이 $\alpha$ 이므로 시간 복잡도는 다음과 같습니다.

값을 찾는 경우의 $T_s$는, 체인에서 거쳐가는 노드의 개수를 알아야 합니다. 그런데 값에는 딕셔너리에 추가한 순서대로 순번을 매겼고, 연관 리스트는 나중에 들어간 것이 앞에 오기 때문에, 찾는 값보다 나중에 들어간 것이 체인에 몇 개인지 세는 문제가 됩니다. 그 개수를 $X$라고 합시다. 그러면 다음과 같이 표현할 수 있습니다.

한편, $i$ 번째와 $j$ 번째 값이 $k$ 번째 체인에 있을 때 $1$인 인디케이터는 $I_{ik} I_{jk}$로 쓸 수 있습니다. 그러면 같은 체인에서 $i$ 번째 보다 나중에 들어온 것의 개수는 이렇게 표현됩니다.

$i$ 번째보다 나중에 들어온 $j$ 번째에 대해 더한 것이기 때문입니다.

그런데 위 식은 $k$ 번째 체인에 $i$ 번째 값이 있는 경우에만 의미가 있는 것이고, 그렇지 않으면 $0$인 것입니다. 하지만 일반적으로 그 값이 어떤 체인에 있을지는 모릅니다. 따라서 모든 체인에 대해 합을 구한 $L_i$는 특정 체인에 의존하지 않는 랜덤 변수가 됩니다.

이 결과는 특정한 $i$ 번째 값에 대한 것인데, 앞으로 구할 $X$는 모든 $i$를 고려한 기댓값입니다. 이를 위해, 또다른 인디케이터 $S_i$를 $i$가 찾으려는 값의 순번일 때 $1$, 아니면 $0$으로 정의하겠습니다. 그러면 $X$의 기댓값 $E[X]$는 다음과 같습니다.

이로부터 기대 수행 시간 $E[T_s]$를 구하게 됩니다.

즉 값을 못 찾는 경우의 $T_f$와 같습니다. 따라서 정리하면 get() 연산은 $\Theta(n)$의 시간이 듭니다.

set()과 remove() 연산 또한 비슷한 방법으로 $\Theta(n)$임을 보일 수 있습니다. 왜냐면 거치는 노드의 개수가 앞서 본 것과 같기 때문입니다.

구현하기

여기서는 체이닝을 자바로 구현해보고, 실제로 측정한 소요 시간이 방금의 시간 복잡도를 따르는지 확인해볼 것입니다.

먼저 체이닝으로 구현하는 해시 테이블 클래스를 만듭니다. 생성자는 키를 구하는 함수를 받고, 슬롯을 초기화합니다. 슬롯의 개수는 임의의 숫자로 정했습니다.

abstract class AbstractChainingTable<K, V> implements Dictionary<K, V> {
  protected static int INIT_NUM_SLOTS = 16;

  protected AssocList<K, V>[] slots;
  protected Function<V, K> getKey;
  protected int numValues;

  public AbstractChainingTable(Function<V, K> getKey) {
    this.slots = this.initSlots(INIT_NUM_SLOTS, getKey);
    this.getKey = getKey;
    this.numValues = 0;
  }

  // ...
}

여기서 슬롯을 초기화하는 initSlots() 메소드는 연관 리스트로 채워 리턴합니다.

  protected AssocList<K, V>[] initSlots(int numSlots, Function<V, K> getKey) {
    @SuppressWarnings("unchecked")
    AssocList<K, V>[] slots = new AssocList[numSlots];

    for (int i = 0; i < slots.length; ++i) {
      slots[i] = new AssocList<K, V>(getKey);
    }

    return slots;
  }

get() 메소드는 수도코드를 그대로 옮겨 구현합니다.

  public V get(K key) {
    int hash = this.getHash(key);
    AssocList<K, V> chain = this.slots[hash];

    return chain.get(key);
  }

여기서 해시 값을 계산하는 getHash() 메소드는 일단 구현 없이 추상 메소드로 남깁시다.

  abstract protected int getHash(K key);

set()과 remove() 메소드는 값의 개수를 바꾸는데, 그 변화를 numValues 필드에 반영해야 합니다. 이를 위한 보조 메소드 updateChain()은 set()과 같은 메소드를 updateFunc으로 받으면 자동으로 개수를 구합니다.

  protected void updateChain(int hash, Consumer<AssocList<K, V>> updateFunc) {
    AssocList<K, V> chain = this.slots[hash];
    int oldSize = chain.getSize();

    updateFunc.accept(chain);

    int deltaSize = chain.getSize() - oldSize;
    this.numValues += deltaSize;
  }

그러면 set()은 다음과 같습니다.

  public void set(V value) {
    K key = this.getKey.apply(value);
    int hash = this.getHash(key);

    this.updateChain(hash, chain -> chain.set(value));
  }

이와 같이 remove()도 쉽게 만들 수 있습니다. getSize() 또한 간단하므로, 이것들은 직접 만드는 것으로 남겨두겠습니다.

이렇게 만든 추상 클래스로부터 체이닝 클래스를 다음과 같이 만듭시다. 여기서 해시 값은 자바의 hashCode() 메소드를 이용합니다. 그런데 슬롯의 인덱스보다 큰 숫자가 될 수 있으므로, 대신 슬롯 개수로 나눈 나머지를 구합니다. 이 방법은 모듈러 해싱modular hashing이라고도 부릅니다.

public class FixedChainingTable<K, V> extends AbstractChainingTable<K, V> {
  public FixedChainingTable(Function<V, K> getKey) {
    super(getKey);
  }

  @Override
  protected int getHash(K key) {
    return key.hashCode() % this.slots.length;
  }
}

이렇게 만든 해시 테이블은 연관 리스트로 만든 딕셔너리와 같은 방식으로 사용할 수 있습니다.

소요 시간 측정

앞서 만든 get()과 set() 메소드의 소요 시간을 재봅시다. 다음은 배열의 크기가 $n$ 일 때 get()이 값을 성공적으로 찾는 데 소요되는 시간과, set()으로 $n$ 개의 값을 넣을 때까지의 시간을 측정한 것입니다. 여기서 해시 테이블을 채우는 set()의 경우는 $n = 1, 2, \dots, n$인 경우를 더한 것이기 때문에 이론적으로는 $\Theta(n^2)$의 시간 복잡도를 갖습니다.

위 결과는 실제 소요 시간이 이론적인 시간 복잡도를 따르는 것을 보여줍니다.

체이닝 해시 테이블 보완하기

앞서 체이닝으로 만든 해시 테이블은 잘 동작하기는 하지만, get() 연산은 예고했던 $\Theta(1)$의 시간 복잡도를 갖지는 않습니다. 사실 예상할 수 있는 결과였는데, 값이 많아질 수록 로드 팩터가 커지면 곧 체인의 길이가 길어지기 때문입니다.

값의 개수가 많지 않거나, 값이 많아져도 슬롯의 크기가 충분히 크다면, 시간 복잡도 $\Theta(1+\alpha)$에서 로드 팩터 $\alpha$가 그리 크지 않아 실제 소요 시간 또한 $\Theta(1)$에 가까워집니다.

하지만 값이 많아질 때도 $\Theta(1)$을 보장하고 싶다면, $\Theta(n)$의 시간을 만드는 로드 팩터 $\alpha = n/m$를 일정 수준 이하로 만들어야 할 것입니다. 다시 말해, 상수 $c$에 대해 로드 팩터를 $\alpha \leq c$로 제한하면, 시간 복잡도 다음과 같이 줄어듭니다.

그렇게 하려면 값의 개수 $n$이 커짐에 따라 슬롯의 개수 $m$도 그만큼 많아져야 합니다. 즉 $\alpha = n/m$에서 분모가 커져야 합니다. 따라서 이것은 다이나믹 배열의 경우처럼, 배열이 리사이징resizing할 수 있도록 만들어야 합니다. 이전 글에서 분석했던 것처럼, 배열 크기를 조절할 때 드는 시간은 아모타이즈드amortized $\Theta(1)$이므로, 이것을 포함해도 해시 테이블의 연산은 여전히 $\Theta(1)$의 시간이 듭니다.

리사이징은 새로운 크기의 배열을 할당해서 기존 값을 복사하는 것으로 만들게 됩니다. 그런데 여기서는 해시 값도 다시 계산해야 합니다. 만들었던 해시 함수가 슬롯 개수에 의존하기 때문입니다. 따라서 리사이징은 해시 값을 다시 계산하는 리해싱rehashing이 필요합니다.

리해싱은 체인의 각 값마다 계산해야 하지만, 앞서 만든 연관 리스트에는 각 노드마다 반복할 수 있는 인터페이스를 제공하지 않았습니다. 만약 그런 기능이 있으면 구현이 편해지지 않을까요? 사실 자바의 Iterator 인터페이스를 구현하면 for 문에 바로 사용할 수 있게 됩니다. 아래에서는 서큘러 리스트를 이용해 구현 방법을 알아볼 것입니다.

이터러블 구현하기

이 작업은 주로 기존의 코드를 수정하는 일이 될 것입니다. 먼저 다음과 같이 리스트 클래스를 Iterable 인터페이스의 구현으로 선언합니다.

public class CircularLinkedList<T> { 
public class CircularLinkedList<T> implements Iterable<T> { 
  // ...
}

이 인터페이스는 iterator() 메소드를 요구하는데, 여기서는 Iterator 인터페이스의 구현을 리턴해야 합니다. 따라서 클래스 내부에 Iterator를 구현하는 중첩 클래스nested class를 만들어봅시다. 이 클래스의 생성자는 반복을 시작할 첫 노드를 받습니다.

  private class ListIterator<U> implements Iterator<U> {
    private LinkedNode<U> node;

    public ListIterator(LinkedNode<U> head) {
      this.node = head;
    }

    // ...
  }

이 인터페이스는 다음이 있는지 확인하는 hasNext() 메소드와, 다음 값을 리턴하는 next() 메소드를 요구합니다. 먼저 hasNext() 메소드는 단순히 리스트가 끝났는지 확인합니다. 여기서는 끝을 나타내는 더미 노드 end를 활용합니다.

    public boolean hasNext() {
      return this.node != end;
    }

그리고 다음 값을 가져올 때, 값을 리턴하면서 다음 노드로 건너갑니다.

    public U next() {
      U data = this.node.getData();

      this.node = this.node.getNext();

      return data;
    }

이 내부 클래스를 이용해, 서큘러 리스트의 iterator() 메소드를 만듭니다.

public class CircularLinkedList<T> implements Iterable<T> {
  // ...

  public Iterator<T> iterator() {
    LinkedNode<T> head = this.end.getNext();
    return new ListIterator<>(head);
  }
}

체인으로 쓰는 연관 리스트도 이터러블로 만들 차례입니다. 아래과 같이 값을 이터러블로서 리턴하는 메소드 getValues()를 만듭니다.

public class AssocList<K, V> implements Dictionary<K, V> {
  // ...

  public Iterable<V> getValues() {
    return this.list;
  }
}

이제 다음 테스트 코드 처럼 for 문으로 반복할 수 있게 됩니다.

  @Test
  public void testIterable() {
    AssocList<Integer, Integer> list = new AssocList<>(v -> v);
    list.set(42);
    list.set(43);
    list.set(44);

    // value = 44, 43, 42
    int i = 44;
    for (int value : list.getValues()) {
      assertEquals(i--, value);
    }
  }

이 반복문에서는 값을 읽기만 했는데, 값의 변경 또한 막지 않았으니 얼마든지 가능합니다. 하지만 그런 코드는 동작을 파악하기 어렵게 만들고, 심지어 반복문이 끝나지 않는 무한 루프를 일으킬 수도 있습니다. (예를 들어, 반복문에서 맨뒤에 노드를 추가하는 코드가 그렇습니다.)

이런 경우를 원치 않는다면, 값이 변경될 때 바로 예외를 던지도록 만들 수 있습니다. 그리고 이런 이터레이터를 자바에서 페일 패스트fail-fast 이터레이터라고 부릅니다.

이것을 구현하는 방법은 변경 작업이 일어난 횟수를 세는 것입니다. 변경 작업의 횟수를 세는 modCount 필드를 만듭시다.

public class CircularLinkedList<T> implements Iterable<T> {
  // ...

  private int modCount; 

  public CircularLinkedList() {
    // ...

    this.modCount = 0; 
  }

  // ...
}

그리고 변경 작업을 수행하면 이 횟수를 하나씩 늘립니다.

  public void prepend(T data) {
    // ...

    this.modCount++; 
  }

  public void change(Predicate<T> pred, T data) {
    // ...

    this.modCount++; 
  }

  public void remove(Predicate<T> pred) {
    // ...

    this.modCount++; 
  }

이터레이터를 초기화할 때 이 횟수를 expectedModCount로 기억합니다.

  private class ListIterator<U> implements Iterator<U> {
    // ...

    private int expectedModCount; 

    public ListIterator(LinkedNode<U> head) {
      // ...

      this.expectedModCount = modCount; 
    }

    // ...
  }

반복에서 다음 값을 가져올 때, 이 modCount가 달라져 있는지 확인합니다. 만약 달라져 있으면, 반복 도중에 리스트에 변경이 일어난 것이므로, 예외를 던집니다.

    public U next() {
      this.throwIfModified(); 

      // ...
    }

    private void throwIfModified() {
      if (modCount != this.expectedModCount) {
        throw new ConcurrentModificationException();
      }
    }

ConcurrentModificationException는 자바에서 페일 패스트 이터레이터가 던져야 할 예외로 정해진 것입니다. 다음과 같은 테스트 코드처럼, 이터레이터는 반복 도중에 내용 변경을 시도하면 예외를 던집니다.

  @Test
  public void testFailFastIterable() {
    CircularLinkedList<Integer> list = createList();

    assertThrows(ConcurrentModificationException.class, () -> {
      for (int value : list) {
        list.prepend(45);
      }
    });
  }

리해싱을 통한 리사이징

방금 만든 이터러블 인터페이스를 이용해, 체이닝 해시 테이블이 크기를 알아서 조절하도록 만들어 봅시다. 이를 통해 시간 복잡도를 $\Theta(1)$로 낮추게 될 것입니다.

먼저, 다음과 같이 상속으로 새 클래스를 만들겠습니다.

public class ChainingTable<K, V> extends AbstractChainingTable<K, V> {
  public ChainingTable(Function<V, K> getKey) {
    super(getKey);
  }
}

그러면 크기를 어떻게 조절할 것인지 결정해야 합니다. 여기서는 로드 팩터가 $\alpha \geq 4$이면 슬롯을 두 배로 늘리도록 하겠습니다. 이렇게 늘어나는 비율을 그로스 팩터growth factor라고 부릅니다. 반대로 $\alpha \leq 1$인 경우, 그로스 팩터의 역수로서 반으로 줄일 것입니다. 이 값을 상수로 둡시다.

public class ChainingTable<K, V> extends AbstractChainingTable<K, V> {
  private static double MAX_LOAD_FACTOR = 4.0;
  private static double MIN_LOAD_FACTOR = 1.0;
  private static double GROWTH_FACTOR = 2.0;

  // ...
}

리사이징하는 해시 테이블은, 값을 추가했을 때 로드 팩터가 정해진 기준에 다다르면 슬롯을 늘리도록 만듭니다.

  @Override
  public void set(V value) {
    super.set(value);

    if (this.isTooManyLoaded()) {
      int extendedSize = (int)(this.slots.length * GROWTH_FACTOR);
      this.resizeSlots(extendedSize);
    }
  }

값을 삭제할 때는 이와 반대로 슬롯을 줄입니다.

  @Override
  public void remove(K key) {
    super.remove(key);

    if (this.isTooFewLoaded()) {
      int reducedSize = (int)(this.slots.length / GROWTH_FACTOR);
      this.resizeSlots(reducedSize);
    }
  }

로드 팩터가 너무 커졌는지는 다음과 같이 확인합니다.

  private boolean isTooManyLoaded() {
    return this.getLoadFactor() >= MAX_LOAD_FACTOR;
  }

반대로 너무 작아졌는지는, 슬롯이 처음 사이즈보다 커졌는지 보면서 로드 팩터를 확인합니다. 즉 처음 사이즈보다 작아질 수는 없도록 합니다.

  private boolean isTooFewLoaded() {
    if (this.slots.length <= INIT_NUM_SLOTS) {
      return false;
    }

    return this.getLoadFactor() <= MIN_LOAD_FACTOR;
  }

로드 팩터를 계산하는 getLoadFactor() 메소드는 쉽게 만들 수 있으므로 직접 해보는 것으로 남기겠습니다.

리사이징은 곧 슬롯의 크기를 조절하는 것입니다. 이를 위해 슬롯 배열을 새롭게 만들고, 여기에 해시 값을 전부 다시 구해 체인에 넣습니다. 체인이 이터러블하다는 사실을 이용해 for 문으로 반복합시다.

  private void resizeSlots(int newSize) {
    AssocList<K, V>[] oldSlots = this.slots;

    AssocList<K, V>[] newSlots = this.initSlots(newSize, this.getKey);
    this.slots = newSlots;

    // rehash values
    for (int i = 0; i < oldSlots.length; ++i) {
      AssocList<K, V> oldChain = oldSlots[i];
      for (V values : oldChain.getValues()) {
        int hash = this.getHash(this.getKey.apply(values));
        this.slots[hash].set(values);
      }
    }
  }

마지막으로, 해시 함수는 기존과 같이 모듈러 해싱으로 만듭니다. 이렇게 완성한 해시 테이블은 기존 체이닝 해시 테이블과 같이 사용할 수 있게 됩니다.

이터러블 해시 테이블

체이닝 해시 테이블로 출석부를 만들 수 있지만, 지금보니 한 가지 부족한 점이 있습니다. 출석부에 어떤 학생들이 있는지 그 목록을 구할 방법이 없습니다. 하지만 이터러블 인터페이스를 딕셔너리에도 적용해본다면, 이 기능을 간단히 만들 수 있습니다.

먼저, 딕셔너리의 인터페이스에 모든 값을 리턴하는 메소드를 선언합시다.

public interface Dictionary<K, V> {
  // ...

  public Iterable<V> getValues(); 
}

이 인터페이스를 가지는 클래스도 수정해야 합니다. 연관 리스트의 경우, 내부의 링크드 리스트를 리턴하는 것으로 만들 수 있습니다.

public class AssocList<K, V> implements Dictionary<K, V> {
  // ...

  public Iterable<V> getValues() {
    return this.list;
  }
}

체이닝 해시 테이블의 경우, 모든 슬롯의 값을 링크드 리스트로 모아서 리턴하는 것으로 구현할 수 있습니다. 다음과 같이 상위 클래스에서 구현을 만들어 모든 체이닝 해시 테이블에 적용합니다.

abstract class AbstractChainingTable<K, V> implements Dictionary<K, V> {
  // ...

  public Iterable<V> getValues() {
    CircularLinkedList<V> list = new CircularLinkedList<>();

    for (int i = 0; i < this.slots.length; ++i) {
      for (V value : this.slots[i].getValues()) {
        list.prepend(value);
      }
    }

    return list;
  }
}

이제 딕셔너리는 값을 모두 가져오는 것까지도 할 수 있게 되었습니다. 다만 이렇게 가져온 값은 어떤 순서를 보장할 수는 없습니다. 딕셔너리를 설계할 때 키의 순서를 신경쓰지 않았기 때문에 나타난 결과입니다.

소요 시간 측정

리사이징 해시 테이블의 get(), set() 연산에 $\Theta(1)$의 시간이 걸리는지 측정해봅시다. 이번에도 크기가 $n$ 인 해시 테이블에서 get()에 소요되는 시간과, 해시 테이블에 $n$ 개의 값을 set()으로 채울 때의 소요 시간을 보겠습니다.

get()의 소요 시간은 크기가 커짐에 따라 늘어나긴 하지만, 리사이징이 없을 때와 비교하면 현저히 적습니다. (늘어나는 이유는 뭘까요?) 그리고 $n$ 번 수행하는 set()의 경우 $\Theta(n)$을 따르기 때문에, 한 번의 수행은 곧 $\Theta(1)$이 됩니다. 이 또한 리사이징이 없을 때와 비교하면 더 적은 소요 시간을 보입니다.

맵과 셋

맵과 셋은 그 이름처럼 각각 매핑과 집합을 표현하는 데이터 구조입니다. 이것은 많은 프로그래밍 언어에서 내장된 것이기도 한데, 대표적으로 자바스크립트JavaScript에 같은 이름을 가진 클래스가 존재하기도 합니다.

여기서는 앞서 만든 딕셔너리를 어떻게 확장해서 만들 수 있는지 볼 것입니다.

셋

셋은 집합을 구현하는 데이터 구조로서, 값을 신경쓰지 않는 딕셔너리와 같습니다. 그 특징은 다음 ADT에서도 잘 나타납니다.

• has(key): 키 key가 존재하는 지 확인합니다.

• set(key): 키 key를 셋에 넣습니다. 기존에 이미 있었다면 변화는 사실상 없습니다.

• remove(key): 키 key를 셋에서 없앱니다.

셋은 정말 몇 줄 안되는 코드로 금방 만들 수 있습니다. 키와 값이 같은 딕셔너리로 볼 수 있기 때문입니다.

예를 들어, has() 연산은 다음과 같이 키로 값을 찾을 수 있는지 여부를 불리언Boolean으로 리턴합니다.

set() 연산은 단순히 딕셔너리 연산에 맡깁니다.

remove() 연산도 이와 같이 만들 수 있습니다.

이렇게 만드는 셋은 모든 연산을 사실상 딕셔너리에 맡기므로, 시간 복잡도 또한 내부의 딕셔너리를 따르게 됩니다. 예를 들어 딕셔너리의 모든 연산이 $\Theta(1)$의 시간 복잡도를 가진다면, 셋은 거기에 고작 몇 줄의 코드를 더 수행할 뿐이기 때문에 이 또한 $\Theta(1)$을 갖습니다.

ADT를 따라 인터페이스를 다음과 같이 만듭니다. 여기에 getSize()는 키의 개수를, getKeys()는 모든 키를 이터레이터로 리턴합니다.

public interface Set<K> {
  public void set(K key);
  public boolean has(K key);
  public void remove(K key);
  public int getSize();
  public Iterable<K> getKeys();
}

앞서 언급했듯, 셋은 키와 값이 같은 딕셔너리로 만듭니다. 먼저, 셋의 생성자는 값을 키로 가지는 딕셔너리를 초기화합니다.

public class ChainingSet<K> implements Set<K> {
  private Dictionary<K, K> dict;

  public ChainingSet() {
    this.dict = new ChainingTable<>(v -> v);
  }

  // ...
}

이 셋의 메소드는 모두 딕셔너리에 맡길 수 있습니다. 예를 들어, has()는 다음과 같습니다.

  public boolean has(K key) {
    return this.dict.get(key) != null;
  }
}

나머지도 전부 한줄로 충분히 만들 수 있으므로, 직접 해보는 것으로 남기고 넘어가겠습니다.

이렇게 만든 셋은 다음과 같은 테스트 코드처럼 출석부 문제를 해결합니다. 이름을 추가하고 삭제해가며 출석 여부를 테스트합니다.

  @Test
  public void testSetAndHas() {
    Set<String> set = new ChainingSet<>();

    set.set("Jane");

    assertEquals(false, set.has("John"));
    assertEquals(true, set.has("Jane"));
    assertEquals(false, set.has("Tom"));

    set.set("John");

    assertEquals(true, set.has("John"));
    assertEquals(true, set.has("Jane"));
    assertEquals(false, set.has("Tom"));

    set.remove("John");

    assertEquals(false, set.has("John"));
    assertEquals(true, set.has("Jane"));
    assertEquals(false, set.has("Tom"));
  }

맵

맵 또한 딕셔너리처럼 매핑의 구현입니다. 그러나 앞서 만든 딕셔너리는 키에서 값을 구할 수 있다고 가정한 반면, 여기서 만들 맵은 그럴 필요 없이 자유롭게 연관시킬 수 있도록 개선할 것입니다.

맵은 페어pair, 즉 순서쌍을 값으로 갖는 딕셔너리로 만들 수 있습니다. 이때 키는 페어의 첫 번째 데이터로 정합니다. 예를 들어, get() 연산은 다음과 같습니다.

set() 연산은 단순히 딕셔너리에 페어를 넣는 것으로 만들 수 있습니다.

remove() 연산도 이와 같이 만들 수 있습니다.

맵을 만드는 것은 셋의 경우와 별 차이가 없습니다. 따라서 맵 또한 딕셔너리의 시간 복잡도를 따릅니다.

맵의 인터페이스를 다음과 같이 만듭니다.

public interface Map<K, V> {
  public void set(K key, V value);
  public V get(K key);
  public void remove(K key);
  public int getSize();
  public Iterable<Pair<K, V>> getEntries();
}

여기서 getEntries()는 모든 값을 연관된 키와 함께 페어로 리턴합니다.

페어 클래스는 다음과 같이 두 필드를 갖도록 만듭니다.

public class Pair<T, U> {
  private T first;
  private U second;

  public Pair(T first, U second) {
    this.first = first;
    this.second = second;
  }

  public T getFirst() {
    return this.first;
  }

  public U getSecond() {
    return this.second;
  }
}

맵 클래스는 페어의 첫 번째 데이터를 키로 가지는 딕셔너리로 만듭니다.

public class ChainingMap<K, V> implements Map<K, V> {
  private ChainingTable<K, Pair<K, V>> dict;

  public ChainingMap() {
    this.dict = new ChainingTable<>(Pair::getFirst);
  }

  // ...
}

그러면 키를 통해 값을 가져오는 get()은 다음과 같이 페어를 이용해 만들 수 있습니다.

  public V get(K key) {
    Pair<K, V> pair = this.dict.get(key);
    if (pair == null) {
      return null;
    }

    V value = pair.getSecond();
    return value;
  }

나머지 메소드는 구현이 간단하므로 직접 해보는 것으로 남기겠습니다. 테스트 또한 셋의 경우와 비슷하므로 마찬가지입니다.

마치며

본문의 자바 코드는 생략된 부분을 포함해 깃허브GitHub에서 확인할 수 있습니다.

레퍼런스

• Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)

• Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)

• Introduction to Probability with Statistical Applications (2nd ed., Géza Schay, 2016): 확률론.

• ConcurrentModificationException: 페일 패스트 이터레이터.