해시. 정의 없음. 아무도 뭔지 모름.

Hash, x. There is no definition for this word—nobody knows what hash is.

— The Devil’s Dictionary (1906)

이전 글에서 딕셔너리dictionary라는 데이터 구조를 만들 때 해시 충돌hash collision을 해결하기 위해 체이닝chaining을 이용했습니다. 그런데 간단하게 배열만 사용해서 해소할 수도 있습니다. 슬롯이 비어있지 않다면 그 다음 슬롯을 보는 것입니다. 이것이 여기서 알아볼 오픈 어드레싱open addressing 방식입니다.

다음 슬롯이 비어있을 때까지 찾아보는 이 과정을 프로브probe라고 부릅니다. 여기서 다음이란 단순히 인덱스 상으로 다음일 수도 있고, 아니면 다른 규칙을 따르는 걸 수도 있습니다. 이렇게 프로브가 거치는 인덱스는, 슬롯의 개수 $m$ 에 대해, 길이가 $m$ 인 나열로 표현할 수 있습니다.

i_1, i_2, i_3, \dots, i_m

이를 프로브 시퀀스probe sequence라고 부릅니다. 예를 들어, $m = 3$ 이라면, $0, 1, 2$ 또는 $1, 0, 2$ 등이 될 수 있습니다. 따라서 get() 연산은 프로브 시퀀스로 다음 슬롯을 찾게 됩니다.

get ( $\textit{slots}$ , $\textit{key}$ ) // 슬롯 배열 $\textit{slots}$ 에서 키 $\textit{key}$ 로 값을 찾아 리턴

$\textit{hash}$ $\leftarrow$ $\textit{key}$ 의 해시 값

$\textit{seq}$ $\leftarrow$ $\textit{hash}$ 로 시작하는 프로브 시퀀스

다음을

\textit{seq}

의 인덱스

i

마다 반복

$\textit{slot}$ $\leftarrow$ $\textit{slots}[i]$

만약

\textit{slot}

이 빈 경우이면

리턴 null // 키와 연관된 값 없음

만약

\textit{slot}

의 값

\textit{value}

가

\textit{key}

와 연관된 경우이면

리턴

\textit{value}

오류 던짐 // 빈 슬롯이나 해당 슬롯이 없음

앞으로의 내용을 통해, 오픈 어드레싱으로 어떻게 해시 테이블을 만들 수 있을지 알아볼 것입니다. 곧 보겠지만 프로브 시퀀스를 어떻게 만드느냐에 따라 특징과 성능이 달라집니다.

만약 프로브 시퀀스가 $0, 1, 2, \dots$ 처럼 다음 인덱스로 나열된다면 리니어 프로빙linear probing이라고 부릅니다. 그런데 그 시작이 키의 해시 값으로 시작하기 때문에, 이것이 충돌한다면 시퀀스의 나머지 부분 또한 똑같으므로 연이어 충돌이 발생합니다. 따라서 이런 현상을 피하기 위해 프로브 시퀀스를 다르게 설계할 수 있는데, 해시 함수를 두 개 이용하는 더블 해싱double hashing도 만들어 볼 것입니다.

리니어 프로빙으로 만드는 해시 테이블

이전 글에서 다음과 같이 딕셔너리의 ADT를 정의했습니다.

get(key): 키 key와 연관된 값을 가져옵니다.
set(key, value): 키 key를 값 value에 연관시킵니다.
remove(key): 키 key와 연관된 값을 없앱니다.

앞서 본 get()의 수도코드와 비슷하게 나머지 또한 만들어볼 것입니다.

오픈 어드레싱은 슬롯보다 많은 값을 가질 수는 없습니다. 즉 set()을 슬롯보다 많이 할 수 없게 됩니다. 하지만 이런 횟수의 제한을 없애고 싶다면, 값이 많아졌을 때 슬롯의 크기가 늘어나도록 만들 수도 있습니다. 이것 또한 이전 글에서 리사이징resizing 체이닝 해시 테이블을 만들었던 것과 비슷합니다.

여기서도 해시 테이블에 $m$ 개의 슬롯과 $n$ 개의 값이 있을 때 로드 팩터 $\alpha$ 를 $n/m$ 로 정의하겠습니다. 그러면 $\alpha$ 가 일정 수준 이상일 때 크기를 늘려서, 해시 테이블의 사용자가 크기를 신경쓰지 않을 수 있습니다.

따라서 set() 연산은 다음과 같이, 값을 넣는 작업과 동시에 리사이징을 맡도록 만듭시다.

set ( $\textit{slots}$ , $\textit{key}$ , $\textit{value}$ ) // 슬롯 배열 $\textit{slots}$ 에서 키 $\textit{key}$ 를 값 $\textit{value}$ 에 연관시키고 슬롯 크기 조절

setValue( $\textit{slots}$ , $\textit{key}$ ) // 실제로 값을 넣는 연산

만약

\textit{slots}

의 로드 팩터가 일정 수준 이상이면

슬롯을 늘림

해시 함수가 슬롯의 크기에 의존한다면, 이전 글의 경우와 마찬가지로 슬롯을 늘릴 때 리해싱rehashing이 필요합니다. 그리고 시간 복잡도는 아모타이즈드amortized $\Theta(1)$ 을 가지므로, set()의 시간 복잡도는 곧 setValue()를 따르게 됩니다.

setValue() 연산은 슬롯이 비었으면 새롭게 값을 넣고, 이미 키와 연관된 값이 있으면 새 값으로 바꿉니다.

setValue ( $\textit{slots}$ , $\textit{key}$ , $\textit{value}$ ) // 슬롯 배열 $\textit{slots}$ 에서 키 $\textit{key}$ 를 값 $\textit{value}$ 에 연관시킴

$\textit{hash}$ $\leftarrow$ $\textit{key}$ 의 해시 값

$\textit{seq}$ $\leftarrow$ $\textit{hash}$ 로 시작하는 프로브 시퀀스

다음을

\textit{seq}

의 인덱스

i

마다 반복

$\textit{slot}$ $\leftarrow$ $\textit{slots}[i]$

만약

\textit{slot}

이 빈 경우이면

$\textit{slot}[i]$ $\leftarrow$ $\textit{value}$

리턴

만약

\textit{slot}

의 값이

\textit{key}

와 연관된 경우이면

$\textit{slot}[i]$ $\leftarrow$ $\textit{value}$

리턴

오류 던짐 // 빈 슬롯이나 해당 슬롯이 없음

remove() 연산은 생각보다 복잡합니다. 단순히 슬롯을 비우는 것으로 만들 수는 없습니다.

왜일까요? 만약 set()으로 어떤 값 $\textrm{C}$ 를 넣을 때, 프로브 시퀀스가 $\textrm{B}$ 를 거친다고 해봅시다. 이제 $\textrm{B}$ 를 그냥 지워버리면 $\textrm{C}$ 은 없는 값이 되어버립니다.

wrong get — 그림 2. 빈 슬롯으로 삭제했을 경우. B를 삭제하기 위해 비운 슬롯 때문에, 이전에 넣었던 값 C를 찾지 못하게 됩니다.

해결 방법으로, 삭제 연산이 일종의 삭제 표시를 하는 걸로 대신해봅시다. 즉 다음 removeValue() 연산과 같습니다.

removeValue ( $\textit{slots}$ , $\textit{key}$ ) // 슬롯 배열 $\textit{slots}$ 에서 키 $\textit{key}$ 에 연관된 값을 삭제하고 슬롯 크기 조절

// removed: 삭제되었음을 표현하는 값

$\textit{hash}$ $\leftarrow$ $\textit{key}$ 의 해시 값

$\textit{seq}$ $\leftarrow$ $\textit{hash}$ 로 시작하는 프로브 시퀀스

다음을

\textit{seq}

의 인덱스

i

마다 반복

$\textit{slot}$ $\leftarrow$ $\textit{slots}[i]$

만약

\textit{slot}

이 빈 경우이면

리턴 // 아무것도 안 하고 끝냄

만약

\textit{slot} =

removed이면

다음 반복으로 건너 뜀

만약

\textit{slot}

의 값이

\textit{key}

와 연관된 경우이면

$\textit{slot}[i]$ $\leftarrow$ removed

리턴

오류 던짐 // 빈 슬롯이나 해당 슬롯이 없음

사용자의 인터페이스인 remove() 연산은 이를 통해 값을 지웁니다. 그리고 로드 팩터가 작으면 슬롯을 줄입니다.

remove ( $\textit{slots}$ , $\textit{key}$ ) // 슬롯 배열 $\textit{slots}$ 에서 키 $\textit{key}$ 에 연관된 값을 삭제

removeValue( $\textit{slots}$ , $\textit{key}$ ) // 실제로 값을 삭제하는 연산

만약

\textit{slots}

의 로드 팩터가 일정 수준 이하이면

슬롯을 줄임

그런데 이렇게 삭제를 구현했기 때문에, 앞서 만들었던 get()과 setValue() 연산 또한 삭제된 슬롯을 신경써야 합니다. 즉 두 연산의 수도코드는 removed 값을 만나면 다음 슬롯으로 건너뛰도록 수정해야 합니다. 간단한 문제이므로 직접 고쳐보는 것으로 남기고 넘어가겠습니다.

리니어 프로빙

리니어 프로빙의 프로브 시퀀스 $S$ 는 키의 해시 값이 $h$ 라면 다음과 같이 주어집니다.

S = h, h+1, h+2, \dots, n-1, 0, 1, 2, \dots, h-1

여기서 $n$ 은 슬롯의 개수입니다.

리니어 프로빙의 경우 시간 복잡도를 계산하는 일은 간단하지 않으므로 결과만 정리하고 넘어가겠습니다. get() 연산이 값을 성공적으로 찾는 경우 시간 복잡도를 $T$ 라고 해봅시다. 프로브에서 거치는 슬롯의 개수를 $X$ 라고 하면, $E[X] = \Theta(1/(1-\alpha))$ 입니다. 반복문은 $X$ 번 수행되므로 $T = \Theta(X)$ 가 되고, 따라서 그 기댓값 $E[T]$ 는 다음과 같습니다.

E[T] = \Theta \left( \frac{1}{1-\alpha} \right) = \begin{cases} \Theta(1) & (\alpha \rightarrow 0) \\ \Theta(\infty) & (\alpha \rightarrow 1) \end{cases}

이를 통해, 시간 복잡도를 줄이려면 로드 팩터를 일정 수준 이하가 되어야 한다는 것을 알 수 있습니다. 그리고 앞서 언급한 리사이징이 그 방법이 됩니다.

구현하기

일반적인 프로브 시퀀스에 대한 오픈 어드레싱을 만들고 난 뒤 리니어 프로빙을 구현해보겠습니다. 먼저, 슬롯은 비었거나, 삭제됐거나, 값이 존재하는 세 가지 상태가 존재합니다. 이런 상태를 관리하기 위해 슬롯 클래스를 만듭시다. 이 슬롯은 값으로 초기화합니다.

class Slot<T> {
  T value;
  boolean removed;

  public Slot(T value) {
    this.value = value;
  }

  // ...
}

이 슬롯은 세 가지 메소드를 가질 것입니다. 먼저, 슬롯의 값을 가져오는 getValue() 메소드입니다.

  public T getValue() {
    return this.value;
  }

그 다음, 슬롯의 값을 삭제하는 remove() 메소드입니다. remove()의 수도코드에서 삭제 표시 부분을 맡습니다.

  public void remove() {
    this.value = null;
    this.removed = true;
  }

마지막으로, 값이 삭제됐는지 확인하는 isRemoved() 메소드입니다.

  public boolean isRemoved() {
    return this.removed;
  }

이제 딕셔너리 인터페이스를 구현하는 오픈 어드레싱 클래스를 만듭시다. 이전 글에서 만든 Dictionary 인터페이스를 이용할 것입니다.

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

이번에도 값에서 키를 항상 알아낼 수 있다고 가정하겠습니다. 해시 테이블은 키를 구하는 함수를 받아 초기화합니다. 그러면 set() 연산은 키와 값을 둘 다 받는 대신 값만 받게 됩니다.

abstract class AbstractOpenAddressingTable<K, V> implements Dictionary<K, V> {
  protected Slot<V>[] slots;
  protected Function<V, K> getKey;
  protected int numValues;
  protected int numRemoved;

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

  protected Slot<V>[] initSlots(int numSlots) {
    @SuppressWarnings("unchecked")
    Slot<V>[] slots = new Slot[numSlots];

    return slots;
  }

  // ...
}

본격적으로 연산을 구현합시다. 먼저, set() 메소드는 다음과 같이 수도코드를 그대로 옮겨 만들 수 있습니다.

  public void set(V value) {
    this.setValue(value);

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

setValue()는 수도코드 그대로 옮겨서 만들되, 크기를 기억하기 위한 필드 numValues를 조절합니다. 그리고 프로브 시퀀스를 구하는 부분은 일단 추상 메소드로 둡니다.

  protected static String EXCEPTION_FULL_MESSAGE = "Hash table is full";

  private void setValue(V value) {
    K key = this.getKey.apply(value);
    Iterable<Integer> probeSeq = this.getProbeSequence(key);

    for (int i : probeSeq) {
      Slot<V> slot = this.slots[i];

      if (slot == null) {
        this.slots[i] = new Slot<V>(value);
        this.numValues++;
        return;
      }

      if (slot.isRemoved()) {
        continue;
      }

      if (this.hasEqualKey(slot, key)) {
        this.slots[i] = new Slot<V>(value);
        return;
      }
    }

    throw new IllegalStateException(EXCEPTION_FULL_MESSAGE);
  }

  abstract protected Iterable<Integer> getProbeSequence(K key);

슬롯의 값이 주어진 키와 연관되어있는지 확인하는 메소드는, 키를 받아 그런 함수를 리턴하는 고차 함수입니다. (이전 글과 같습니다.)

  private boolean hasEqualKey(Slot<V> slot, K key) {
    K slotKey = this.getKey.apply(slot.getValue());

    return key.equals(slotKey);
  }

로드 팩터와 관련된 부분을 만듭시다. 로드 팩터를 계산할 때는 삭제된 슬롯의 개수, 즉 numRemoved 필드도 고려합니다.

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

  private double getLoadFactor() {
    int numOccupied = this.numValues + this.numRemoved;

    return (double)numOccupied / (double)this.slots.length;
  }

마지막으로, 슬롯의 크기를 조절하는 함수는 리해싱으로 슬롯을 다시 채웁니다.

  private void resizeSlots(int newSize) {
    Slot<V>[] oldSlots = this.slots;
    this.slots = this.initSlots(newSize);

    this.numValues = 0;
    this.numRemoved = 0;

    // rehash values
    for (int i = 0; i < oldSlots.length; ++i) {
      Slot<V> oldSlot = oldSlots[i];

      // skip if no value
      if (oldSlot == null || oldSlot.isRemoved()) {
        continue;
      }

      V value = oldSlots[i].getValue();
      this.setValue(value);
    }
  }

이와 비슷하게 get(), remove() 메소드도 만들 수 있으므로 직접 만들어보는 것으로 남기고 넘어가겠습니다. getSize() 메소드 또한 간단하므로 마찬가지입니다.

getValues() 메소드는 해시 테이블의 값을 이터러블에 모아 리턴합니다. 이전 글에서 했던 것과 비슷하게 만들 수 있습니다. 따라서 이 부분도 직접 해보는 것으로 남기고 넘어가겠습니다.

프로브 시퀀스는 이터러블 인터페이스를 구현하도록 만듭시다. 다음과 같이 시작 숫자 begin과 건너뛸 간격 step, 그리고 시퀀스의 길이 length로 초기화합니다.

class ProbeSequence<K> implements Iterable<Integer> {
  private int length;
  private int begin;
  private int step;

  public ProbeSequence(int begin, int step, int length) {
    this.begin = begin;
    this.length = length;
    this.step = step;
  }

  // ...
}

이어서, 이터러블을 구현하기 위해 이터레이터의 구현을 중첩 클래스nested class로 만듭니다. 다음 숫자로 step 만큼 떨어진 숫자를 리턴합니다.

  class ProbeSeqIterator implements Iterator<Integer> {
    private int i = 0;

    public ProbeSeqIterator() {
      this.i = 0;
    }

    public boolean hasNext() {
      return i < length;
    }

    public Integer next() {
      int next = (begin + i*step) % length;
      i++;

      return next;
    }
  }

  public Iterator<Integer> iterator() {
    return new ProbeSeqIterator();
  }

리니어 프로빙이란 그 간격을 1로 하면 간단하게 만들어집니다. 프로브 시퀀스의 시작은 모듈러 해싱modular hashing으로 구합니다.

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

  @Override
  protected Iterable<Integer> getProbeSequence(K key) {
    int n = key.hashCode();

    int length = this.slots.length;
    int begin = n % length; // modular hashing
    int step = 1;

    return new ProbeSequence<>(begin, step, length);
  }
}

다음 테스트 코드는 리니어 프로빙 해시 테이블을 출석부로 활용합니다. 출석한 학생은 해시 테이블에서 null이 아닌 값으로 나타납니다.

  @Test
  public void testAttendance() {
    LinearProbingTable<String, String> table = new LinearProbingTable<>(v -> v);

    table.set("John");
    table.set("Jane");

    assertNotEquals(null, table.get("John"));
    assertNotEquals(null, table.get("Jane"));
    assertEquals(null, table.get("Tom"));

    table.set("Tom");

    assertNotEquals(null, table.get("John"));
    assertNotEquals(null, table.get("Jane"));
    assertNotEquals(null, table.get("Tom"));

    table.remove("John");

    assertEquals(null, table.get("John"));
    assertNotEquals(null, table.get("Jane"));
    assertNotEquals(null, table.get("Tom"));
  }

피보나치 해싱

지금까지 해시 함수는 나머지 연산을 이용한 모듈러 해싱으로 간단히 구현했습니다. 한편, 이전 글에서 체이닝으로 만든 해시 테이블의 시간 복잡도를 계산할 때 이상적인 해시 함수를 가정했습니다. 그리고 그런 해시 함수의 특징 중에 두 해시 값이 독립independence이라는 것이 있었습니다. 다시 말해, 해시 값의 이상적인 분포는 마치 무작위로 나타나는 숫자처럼 보인다고 할 수 있습니다.

이런 점에서 볼 때, 모듈러 해싱은 이상적인 해시 함수와는 거리가 있습니다. 물론 이것이 정말 문제인지는 별개의 사안입니다. 왜냐면 이상적인 해시 함수에 가깝게 만들 수록, 대체로 더 많은 계산을 하게 되어 더 많은 시간이 들 수 있기 때문입니다. 그래서 경우에 따라서는 모듈러 해싱도 충분히 괜찮을 수 있습니다.

그럼에도 모듈러 해싱보다는 좀더 해시 값이 무작위처럼 보이는 것을 한번 만들어볼 것입니다. 이상적인 해시 함수는 실제로 만들기가 어렵지만, 곱셈을 비롯한 몇 번의 연산을 통해서 해시 값을 분산시킬 수 있습니다.

모듈러 해싱 다시 보기

앞서 만든 모듈러 해싱은, 자바의 hashCode() 메소드를 통해 일단 키를 정수integer 타입으로 보내놓고, 여기서 나머지를 구해 인덱스를 얻었습니다. 즉 두 부분으로 구성된 것입니다.

여기서 자바가 hashCode()로 각 타입에 해시 함수를 제공하므로, 임의의 데이터 타입을 어떻게 숫자로 표현할 지 신경쓰지 않을 수 있었습니다. 그러면 이 메소드는 실제로 어떻게 동작할까요? 자바의 구현인 OpenJDK를 보면 정수는 그대로 리턴합니다. 즉 42의 해시 값은 그대로 42입니다.

한편, 키가 스트링string일 때의 해시 함수는 다음 수도코드와 같습니다.

hash ( $\textit{string}$ ) // 스트링 $\textit{string}$ 의 해시 값을 구함

$h$ $\leftarrow$ $0$ // 해시 값

다음을

\textit{string}

의 문자

c

마다 반복

$n$ $\leftarrow$ $c$ 의 숫자 값 // 아스키 코드 등을 이용해 구함

$h$ $\leftarrow$ $31h + n$

리턴

h

이것은 길이가 $n$ 인 스트링을 $n$ 자리의 31진법 숫자처럼 바라보고 호너의 방법Horner’s method으로 계산한 것과 같습니다. 다시 말해, 각 문자의 숫자 값이 차례대로 $a_n, a_{n-1}, \dots, a_1$ 로 주어진다면, 다음과 같이 $\Theta(n)$ 의 시간 복잡도로 해시 값을 구하는 것입니다.

\begin{align*} \sum_{i=1}^n a_i 31^{i-1} &= a_n 31^{n-1} + a_{n-1} 31^{n-2} + \cdots + a_1 31^0 \\ &= (((a_n 31 + a_{n-1}) 31 + a_{n-2})31 + \cdots) 31 + a_1 \end{align*}

여기서 숫자 $31$ 은 소수prime number 중에 잘 동작하는 것을 고른 것입니다.

따라서 모듈러 해싱은 비슷한 키를 비슷한 해시 값으로 만들게 됩니다. 예를 들어, 모듈러 해싱이 $m$ 으로 나눈다면, $m$ 보다 작은 정수는 그대로 해시 값이 됩니다. 또한 foo1, foo2 같은 문자열도 해시 값이 하나의 차이를 갖게 됩니다.

곱셈을 이용한 피보나치 해시

해시 값을 좀더 분산시켜 보겠습니다. 여기서 $m$ 이 슬롯의 개수라고 합시다. 그리고 함수 $h(n)$ 을 다음과 같이 정의하면, 숫자 $n$ 을 인덱스로 보내는 해시 함수가 됩니다.

h(n) = \lfloor m (nA \bmod 1) \rfloor

여기서 $A$ 는 $0 < A < 1$ 중에 하나를 임의로 고른 것입니다. $nA \bmod 1$ 라는 표현은 $nA$ 의 소수 부분을 구하는 것과 같고, 바닥 함수인 $\lfloor x \rfloor$ 는 소수점을 버리기 위해 사용되었습니다.

이 해시 함수 $h$ 는 $A$ 를 잘 선택하면 키를 분산시키게 됩니다. 예를 들어, $A$ 를 $0.25$ 로 선택했다고 해봅시다. 그러면 $m=16$ 에 대해 해시 값은 다음과 같습니다.

\begin{aligned} h(1) &= 4 \\ h(2) &= 8 \\ h(3) &= 12 \\ h(4) &= 0 \\ h(5) &= 4 \\ &\vdots \end{aligned}

네 개의 숫자가 반복적으로 나타나기 때문에 별로 만족스럽지 않습니다. 반복이 나타나는 이유는, 이렇게 $A$ 를 유리수rational number로 고르면 $nA$ 의 소수 부분이 반복되기 때문입니다.

반면 $A$ 를 무리수irrational number로 고르면 이런 주기가 존재하지 않게 됩니다. 다시 말해, 모든 정수 $n$ 에 대해 $nA$ 의 소수 부분은 유일해집니다. 여기서는 $A$ 를 황금비 $\phi = (1+\sqrt{5})/2$ 의 역수, 즉 $\phi^{-1}=0.618\dots$ 로 선택하겠습니다. 이 해시 함수는 피보나치 해싱Fibonacci hashing이라고도 부릅니다.

결과를 보면 비슷한 키의 해시 값을 멀리 떨어뜨리면서 반복 주기가 나타나지 않게 됩니다. 따라서 해시 값이 모듈로 해싱보다 좀 더 무작위처럼 보이게 됩니다.

hash collisions — 그림 3. 모듈러 해싱과 피보나치 해싱의 해시 충돌 다이어그램. 슬롯이 32 개일 때, 해시 값이 얼마나 충돌하는지 보여줍니다. 충돌 횟수가 많을 수록 더 큰 원으로 표현됩니다. 모듈러 해싱은 2의 배수에 대해 많은 해시 충돌을 보이는 반면, 피보나치 해싱은 비교적 분산된 해시 값을 보입니다.

리니어 프로빙에 적용하기

앞서 만든 피보나치 해싱으로 프로브 시퀀스의 시작을 결정하도록 리니어 프로빙을 수정하겠습니다.

먼저, 피보나치 해싱 $h$ 는 부동소수점 연산으로 만들 수도 있습니다. 그런데 앞으로의 구현에서 슬롯 개수 $m$ 은 항상 $2$ 의 제곱 꼴 $2^x$ 로 유지할 것입니다. 여기서 정수 타입의 최댓값을 $2^w$ 로 표현한다면, 상수 $a = A2^w$ 에 대해 $h$ 는 나눗셈 대신 다음과 같이 오른쪽 시프트 연산 $\gg$ 로 바꿀 수 있습니다.

h(n) = (n a \bmod 2^w) \gg (w - s)

증명은 직접 해보는 것으로 남기고 생략하겠습니다. (한번 해보세요.)

먼저, 다음과 같이 피보나치 해싱을 별도의 메소드로 만들겠습니다. 여기서는 정수의 최댓값이 $2^{31}$ 이므로, $a = A2^w$ 는 다음과 같습니다.

\begin{align*} a = A2^{31\mathstrut} = \phi^{-1} 2^{31} &= 1 \thinspace 327 \thinspace 217 \thinspace 884.749 \dots \\ &\approx 1 \thinspace 327 \thinspace 217 \thinspace 885 \end{align*}

여기서는 반올림한 값을 이용하겠습니다.

그러면 피보나치 해싱을 만들어봅시다.

public class Hashes {
  static public <T> int multShiftHash(T toHash, int bound) {
    int num = toHash.hashCode();
    int pow = getPowerOfTwo(bound);

    int hash = (((num * 1327217885) & 0x7FFFFFFF) >> (31 - pow)) % bound;
    return hash;
  }
}

여기서 $2^x$ 로부터 $x$ 를 구하는 함수를 이렇게 만듭니다.

  static private int getPowerOfTwo(int num) {
    int power = 0;
    while ((num & 1) == 0) {
      power++;
      num >>>= 1;
    }
    return power;
  }

이를 이용해 프로브 시퀀스의 시작을 결정하도록 수정합니다.

  @Override
  protected Iterable<Integer> getProbeSequence(K key) {
    int n = key.hashCode();

    int length = this.slots.length;
    int begin = n % length; // modular hashing
    int begin = multShiftHash(n, length); 
    int step = 1;

    return new ProbeSequence<>(begin, step, length);
  }

이 해시 테이블의 get() 연산에 걸리는 소요 시간을 재봅시다. 동일한 로드 팩터에 대해 슬롯의 크기에 따른 소요 시간과, 동일한 슬롯 크기에 대해 로드 팩터에 따른 것을 각각 측정하면 다음과 같습니다.

linear probing elapsed time — 그림 4. 리니어 프로빙의 소요 시간. 선은 회귀선.

이 그래프에서 볼 수 있듯이, 슬롯의 크기가 커질수록, 그리고 로드 팩터가 커질수록 소요 시간 또한 늘어납니다.

더블 해싱

리니어 프로빙은 인덱스를 차례로 확인하므로, 해시 충돌이 일어난 부근에 키가 모이는 클러스터cluster가 만들어집니다. 만약 비슷한 해시 값을 사용하게 된다면, 이 클러스터 때문에 비슷한 위치의 슬롯을 계속 거치게 되어 시간이 더 소요되는 원인이라고 예상해볼 수 있습니다.

다만 실제 소요 시간이 이 이론적인 시간 복잡도를 따르지 않을 수도 있는데, 분석에서 가정한 RAM 계산 모델은 캐싱과 같은 요소를 고려하지 않기 때문입니다. 클러스터는 메모리 상에서 모여있기 때문에, 리니어 프로빙은 실제로 캐싱의 도움을 받을 수도 있습니다.

그러나 이러한 클러스터가 문제라고 가정해봅시다. 그러면 프로브 시퀀스를 다르게 디자인해야 하는데, 바로 옆 슬롯 말고 좀더 멀리 떨어진 곳으로 보내면 어떨까요?

예를 들어, $k$ 번째 다음 슬롯의 인덱스는 $k^2$ 을 더하는 것입니다. 그러면 프로브 시퀀스는 $0, 1, 4, 9, \dots$ 와 같이 진행됩니다. 이 방법은 제곱 탐사, 또는 쿼드라틱 프로빙quadratic probing이라고 부릅니다.

그런데 프로브 시퀀스가 시작이 같다면 전체가 같다는 문제는 리니어 프로빙과 다르지 않습니다. 따라서 이 방법 또한 클러스터를 만든다는 사실은 변하지 않게 됩니다.

그렇다면 그 간격을 정할 때 별도의 해시 함수를 쓰는 건 어떨까요? 즉 해시 함수 $h_1$ , $h_2$ 에 대해, 프로브 시퀀스의 시작은 $h_1$ 로, 간격은 $h_2$ 로 결정하는 것입니다. 따라서 두 키 $k_1$ , $k_2$ 가 $h_1(k_1) = h_1(k_2)$ 로 같은 해시 값을 가지더라도, $h_2(k_1) \neq h_2(k_2)$ 으로 다음 인덱스가 다를 수 있습니다.

double hashing diagram — 그림 5. 더블 해싱 다이어그램. 두 키의 프로브 시퀀스가 시작이 같더라도, 간격이 달라질 수 있으므로 나머지 부분은 달라질 수 있습니다. 따라서 그림처럼 세 개의 슬롯을 방문해 넣은 키가 있다면, 이후 해시 충돌 시 리니어 프로빙은 더 많은 슬롯을 방문해야 하지만, 더블 해싱은 꼭 그렇지는 않게 됩니다.

예를 들어, 숫자인 키 $k$ 와, $m$ 개의 슬롯에 대해 두 해시 함수를 이렇게 만들었다고 해봅시다.

\begin{align*} h_1(k) &= k \bmod m \\ h_2(k) &= 1 + 2 \left\lfloor \frac{k}{m} \right\rfloor \end{align*}

$m$ 이 짝수라면, 위와 같이 $h_2$ 가 홀수만 갖도록 만들어야 프로브 시퀀스가 $m$ 개의 인덱스를 모두 거칩니다. (확인해보세요.) 여기서 $h_2$ 는 $m/2$ 가지가 있으므로, 프로브 시퀀스는 총 $m (m/2) = \Theta(m^2)$ 가지가 존재하게 됩니다.

인덱스의 순열, 즉 퍼뮤테이션permutation은 총 $m!$ 개가 존재할 수 있고, 이것이 프로브 시퀀스가 이론적으로 존재할 수 있는 개수입니다. 한편, 리니어 프로빙의 경우는 프로브 시퀀스가 $m$ 개입니다. (프로브 시퀀스가 그 시작으로 결정되기 때문에 그렇습니다.) 따라서 더블 해싱의 경우는 이상적인 $m!$ 개보다는 적지만 리니어 프로빙의 경우보다는 많습니다.

시간 복잡도

한편, 프로브 시퀀스가 $m!$ 개일 때의 시간 복잡도를 계산해볼 것입니다. 즉 프로브 시퀀스에 나타나는 인덱스가 모두 같은 확률로 나타날 때입니다. 여기서도 get() 연산이 값을 찾는 경우의 $T_s$ 와 못 찾는 경우의 $T_f$ 로 나누어 구해볼 것입니다. 해시 테이블이 $m$ 개의 슬롯과 $n$ 개의 값이 있다고 가정하겠습니다.

먼저 값을 못찾는 경우의 $T_f$ 를 구해봅시다. 계산을 간단히 하기 위해, remove() 연산이 일어난 적이 없다고 합시다. get()이 거쳐가는 슬롯의 개수를 $X$ 라고 한다면, 반복문에서 각 슬롯을 확인할 때까지 드는 시간 $c$ 에 대해, 이 경우의 시간 복잡도 $T_f$ 는 다음과 같습니다.

T_f = 1 + cX

적어도 하나의 슬롯은 거치므로 $X$ 가 $1$ 이상일 확률은 $P(X \geq 1) = 1$ 입니다. 그리고 처음에 고른 슬롯에 값이 있어야 두 슬롯 이상을 거치게 됩니다. 그런데 퍼뮤테이션이 $m!$ 개라고 가정한 것은, 프로브 시퀀스 상 어느 자리든 인덱스는 모두 같은 확률로 나타난다는 의미입니다. 즉 $m$ 개의 슬롯에서 $n$ 개의 인덱스를 골라야 하므로, $P(X \geq 2) = n/m$ 이 됩니다. 세 개 이상인 경우, 남은 $m-1$ 개의 슬롯에서 $n-1$ 개의 인덱스를 골라야 하고, 나머지 경우도 이와 마찬가지입니다. 이를 일반화하면, $1 \leq k \leq n$ 에 대해, 슬롯을 $k$ 개 이상 거칠 확률 $P(X \geq k)$ 는 다음과 같습니다.

\begin{align*} P(X \geq k) &= \frac{n \mathstrut}{m} \frac{n-1}{m-1} \frac{n-2}{m-2} \cdots \frac{n-(k-2)}{m-(k-2)} \\ &\leq \left( \frac{n}{m} \right) ^{k-1} \\ &= \alpha^{k-1} \tag{Eq.1} \end{align*}

이로부터, 거치는 슬롯의 개수 $X$ 의 기댓값 $E[X]$ 를 다음과 같이 구할 수 있습니다. 먼저, 기대값의 정의로부터 다음이 나옵니다.

E[X] = \sum_{k=1}^{n} k P(X = k)

이 식은 다음과 같이 조작할 수 있습니다.

\begin{align*} \sum_{k=1}^{n} k P(X = k) &= \sum_{k=1}^{n} k \left( P(X \geq k) - P(X \geq k+1) \right) \\ &= \sum_{k=1}^{n} k P(X \geq k) - \sum_{k=2}^{n} (k-1) P(X \geq k) \\ &= \sum_{k=1}^{n} P(X \geq k) \end{align*}

여기에 식 $\textrm{Eq.1}$ 을 이용하면 다음을 얻습니다.

E[X] = \sum_{k=1}^{n} P(X \geq k) \leq \sum_{k=1}^{n} \alpha^{k-1} \leq \sum_{k=1}^{\infty} \alpha^{k-1} = \frac{1}{1-\alpha}

따라서 기대 수행 시간 $E[T_f]$ 은 다음과 같습니다.

E[T_f] = E[1 + cX] = 1 + \frac{c}{1 - \alpha} = O\! \left( \frac{1}{1-\alpha} \right)

set()과 remove() 연산이 거치는 슬롯의 개수 또한 앞서 얻은 $X$ 와 같으므로, 같은 시간 복잡도를 가집니다.

이제 get() 연산이 성공적으로 값을 찾는 경우의 시간 복잡도 $T_s$ 를 계산해봅시다. 슬롯에서 어떤 값을 찾았다면, 앞서 set() 연산으로 넣었던 것입니다. 그리고 값을 못 찾는 경우와 똑같은 프로브 시퀀스를 따랐을 것입니다.

set()이 $i$ 번째로 넣은 것을 get()이 찾는 것이라면, 거쳐가는 슬롯의 개수 $X$ 의 기댓값은 $E_i[X]$ 다음과 같습니다.

E_i[X] = \frac{1}{1 - \alpha} = \frac{m}{m - i}

왜냐면 당시의 로드 팩터가 $\alpha = i/m$ 이기 때문입니다. 그런데 $i$ 는 $0 \leq i < n$ 의 범위 중 하나이므로, 이에 대한 기댓값 $E[X]$ 를 구하면 다음과 같습니다.

\begin{align*} E[X] &= \frac{1}{n} \sum_{i=0}^{n-1} E_i[X] \\ &= \frac{1}{\alpha} \sum_{i=0}^{n-1} \frac{1}{m-i} \\ &= \frac{1}{\alpha} \sum_{i=m-n+1}^m \frac{1}{i} \\ &\leq \frac{1}{\alpha} \int_{m-n}^m \frac{dx}{x} \\ &= \frac{1}{\alpha} \ln \frac{1}{1-\alpha} \end{align*}

이로부터 기대 수행 시간 $E[T_s]$ 를 얻습니다.

E[T_s] = E[1 + cX] = 1 + cE[X] = O\! \left( \frac{1}{\alpha} \ln \frac{1}{1-\alpha} \right)

구현 및 소요 시간 측정

더블 해싱의 구현은 다음과 같이 상속으로 간단히 만들 수 있습니다. 이때 프로브 시퀀스의 시작과 간격은 앞서 만든 해시 함수로 구현합니다.

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

  @Override
  protected Iterable<Integer> getProbeSequence(K key) {
    int n = key.hashCode();

    int length = this.slots.length;
    int begin = multShiftHash(n, length);
    int step = 1 + 2*(n/length);

    return new ProbeSequence<>(begin, step, length);
  }
}

이제 연산의 소요 시간을 재봅시다. 리니어 프로빙의 경우와 같은 시나리오로 측정하면 다음과 같습니다.

더블 해싱 또한 리니어 프로빙처럼, 해시 테이블의 크기가 커질 수록, 그리고 로드 팩터가 커질 수록 소요 시간이 증가하는 모습을 보입니다.

이전 글에서 만들었던 맵map과 셋set 또한 오픈 어드레싱으로 구현할 수 있습니다. 비슷한 방법으로 만들 수 있기 때문에, 이 부분은 직접 해보는 것으로 남기겠습니다.

마치며

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

레퍼런스

Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
The Art of Computer Programming, Vol. 3 (2nd ed., Donald Knuth, 1998), 또는 The Art of Computer Programming 3 (한빛미디어, 2008): 리니어 프로빙의 시간 복잡도.
The Practice of Programming (Brian Kernighan, Rob Pike, 1999), 또는 프로그래밍 수련법 (인사이트, 2008): 스트링에 대한 해시 함수.