이 단어에는 정의가 없다. 해시가 뭔지는 아무도 모른다.

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

— The Devil’s Dictionary (1906)

이전 글에서 딕셔너리dictionary라는 데이터 구조를 해시 테이블hash table로 구현해보았습니다. 여기서 해시 함수hash function를 통해 키를 배열의 인덱스로 바꿀 때, 키가 다르더라도 같은 해시 함수를 가지는 해시 충돌hash collision 문제가 있었습니다. 이를 해소하는 방법으로 링크드 리스트linked list를 이용하는 체이닝chaining을 만들어보았습니다.

이 해시 충돌은 체이닝과 달리 링크드 리스트 없이도 해소할 수도 있습니다. 슬롯에 다른 키가 이미 차지하고 있다면 그 다음 슬롯을 알아보는 것입니다. 즉 시퀀셜 서치sequential search를 체인이 아니라 배열 자체에서 하는 것입니다. 이 방법은 오픈 어드레싱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이라고 부릅니다. 이 경우, 프로브 시퀀스는 키 $\textit{key}$ 의 해시 값으로 시작하기 때문에, 해시가 충돌한다면 프로브 시퀀스의 나머지 부분 또한 같게 됩니다. 이런 현상을 피하고 싶다면, 프로브 시퀀스의 간격을 별도의 해시 함수로 결정할 수 있고, 이를 더블 해싱double hashing이라고 부릅니다.

이 글에서는 오픈 어드레싱을 다른 라이브러리를 사용하지 않고 자바Java로 구현까지 해보겠습니다. 리니어 프로빙과 더블 해싱은 프로브 시퀀스만 다르게 해서 만들 수 있으므로, 공통적인 부분부터 살펴보겠습니다.

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

우선 오픈 어드레싱의 연산을 만들어보고, 이후 프로브 시퀀스가 순차적이게끔 만들어서 리니어 프로빙을 만들어봅시다.

오픈 어드레싱 연산

해시 테이블이란 딕셔너리의 구현으로, 그리고 딕셔너리란 다음과 같은 연산을 가지는 것으로 이전 글에서 정의했습니다.

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

여기서 get() 연산의 수도코드는 앞서 본 것과 같습니다. 그리고 비슷한 방법으로 나머지 연산 또한 만들어볼 것입니다. 세 연산 모두 공통적으로 프로브 시퀀스를 통해, 빈 슬롯에 도달했을 때와 값을 찾았을 때를 처리하도록 만듭니다.

오픈 어드레싱은 슬롯보다 많은 값을 가질 수는 없습니다. 따라서 슬롯의 개수가 고정되어 있다면, set() 연산 또한 슬롯보다 많이 할 수 없게 됩니다. 하지만 이런 횟수의 제한을 없애고 싶다면, 값이 많아졌을 때 슬롯의 크기가 늘어나도록, 즉 리사이징resizing하도록 만들 수 있습니다.

이전 글의 다이나믹 배열dynamic array에서 정의했던 것과 비슷하게, 해시 테이블에 $m$ 개의 슬롯과 $n$ 개의 값이 있을 때 로드 팩터load factor $\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}

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

슬롯을 늘림

여기서 리사이징resizing은 이전 글의 체이닝처럼 리해싱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()이 그 슬롯을 거쳤다면, 이를 통해 넣었던 값을 더 이상 찾을 수 없게 되기 때문입니다.

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

이를 해결하기 위한 방법으로, remove() 연산이 슬롯에 삭제된 적이 있다고 표시하는 것으로 대신해봅시다. 따라서 실제로 삭제 역할을 맡는 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() 연산 또한 삭제된 슬롯을 신경써야 합니다. 그러므로 두 연산의 수도코드를 수정할 필요가 있습니다. 다음과 같이 반복문에서 삭제된 슬롯를 처리하는 조건문을 추가합시다.

만약

\textit{slot}

이 빈 경우이면

// …

// 다음을 새롭게 추가

만약

\textit{slot} =

removed이면

다음 반복으로 건너 뜀

리니어 프로빙

리니어 프로빙은 프로브 시퀀스가 $\textit{key}$ 의 해시 값부터 시작해 하나씩 커지게끔 만든 것입니다. 즉 키의 해시 값이 $h$ 라면, 프로브 시퀀스 $S$ 는 다음과 같이 $h$ 로 시작해 가장 큰 인덱스 $n-1$ 까지 도달한 뒤에, $0$ 에서 $h-1$ 까지 이어집니다.

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

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

E[T] = \Theta \left( \frac{1}{1-\alpha} \right)

여기서 시간 복잡도를 줄이기 위해 로드 팩터를 일정 수준 이하로 유지하는 방법을 생각해볼 수 있고, 앞서 만든 리사이징이 그 방법이 됩니다.

구현하기

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

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();
}

또한 이번에도 값에서 항상 키를 알아낼 수 있다고 가정합니다. 따라서 해시 테이블은 키를 구하는 함수를 받아 초기화합니다. 그리고 내부적으로 사용할 슬롯 배열을 만듭니다.

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()는 단순히 개수 필드를 리턴해서 만듭니다.

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

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;
  }

  // ...
}

이어서, 이터러블을 구현하기 위해 이터레이터 클래스를 내부에 만듭니다. 이 클래스는 다음 숫자를 간단한 계산식을 통해 구하고 리턴합니다.

  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);
  }
}

이제 테스트로 확인해봅시다. 이전 글에서와 마찬가지로, JUnit 5 프레임워크를 통해 테스트 코드로 출석부를 만들 수 있습니다. 출석한 학생은 해시 테이블에서 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의 해시 함수는 키가 이미 정수라면 그대로 리턴합니다. 즉 1의 해시 값은 그대로 1이고, 2 또한 2가 됩니다.

키가 스트링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$ 를 인덱스로 보내는 해시 함수가 됩니다.

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

여기서 $A$ 는 $0 < A < 1$ 중에 하나를 임의로 고른 것입니다. 그리고 $nA \bmod 1$ 라는 표현은 소수 부분을 구하는 것과 같고, 바닥 함수인 $\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$ 는 항상 새로운 숫자가 됩니다. 여기서는 황금비golden ratio $\phi = (1+\sqrt{5})/2$ 의 역수, 즉 $\phi^{-1}=0.618\dots$ 로 $A$ 를 선택해봅시다. 이 해시 함수는 피보나치 해싱Fibonacci hashing이라고도 부릅니다.

이렇게 만든 함수는 비슷한 키의 해시 값을 멀리 떨어뜨리면서, 반복 주기가 나타나지 않게 됩니다. 따라서 해시 값을 모듈로 해싱보다 좀 더 무작위처럼 보이게끔 만들게 됩니다.

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

리니어 프로빙에 적용하기

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

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

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

증명은 직접 해보는 것으로 남기고 넘어가겠습니다.

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

a = A2^{31} = \phi^{-1} 2^{31} = 1 \thinspace 327 \thinspace 217 \thinspace 884.749 \dots

이를 반올림한 값을 이용해, 피보나치 해싱을 다음과 같이 수도코드를 따라 만듭시다.

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^s$ 로부터 $s$ 를 구하는 함수를 이렇게 만듭니다.

  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 = 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$ 를 만들어볼 수 있습니다. 그렇다면 두 키 $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!$ 개일 때의 시간 복잡도를 계산해봅시다. 즉 프로브 시퀀스에 나타나는 인덱스가 모두 같은 확률로 나타날 때입니다. 이를 더블 해싱의 시간 복잡도를 근삿값으로서 구하는 데에 적용해봅시다.

해시 테이블이 $m$ 개의 슬롯과 $n$ 개의 값이 있다고 하고, get() 연산이 값을 못 찾는 경우를 보겠습니다. 여기서는 remove() 연산이 일어난 적이 없다고 합시다. get()이 거쳐가는 슬롯의 개수를 $X$ 라고 한다면, 반복문에서 각 슬롯을 확인할 때까지 드는 시간 $c$ 에 대해, 이 경우의 시간 복잡도 $T_u$ 는 $1 + cX$ 가 됩니다.

그런데 적어도 하나의 슬롯은 거치므로 $X$ 가 $1$ 이상일 확률은 $P(X \geq 1) = 1$ 입니다. 그리고 두 개 이상을 거치려면, 값이 들어있는 슬롯을 골라야 합니다. 앞서 가정한대로 다음 인덱스는 모두 같은 확률로 나타나므로, 그렇게 고를 확률은 $n/m$ 입니다. 따라서, $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} \end{align*}

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

\begin{align*} E[X] &= \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) \\ &\leq \sum_{k=1}^{n} \alpha^{k-1} \\ &\leq \sum_{k=1}^{\infty} \alpha^{k-1} \\ &= \frac{1}{1-\alpha} \end{align*}

따라서 시간 복잡도의 기댓값 $E[T_u]$ 는 $1+c/(1-\alpha)$ 이하이므로 다음과 같습니다.

E[T_u] = O\! \left( \frac{1}{1-\alpha} \right)

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

이제 get() 연산이 성공적으로 값을 찾는 경우의 시간 복잡도 $T_s$ 를 계산해봅시다. 슬롯에서 어떤 값을 찾았다면, 앞서 set() 연산으로 넣었던 것이고, 그 때 거쳤던 슬롯의 개수를 $X$ 라고 합시다. get() 연산 또한 set()과 같은 프로브 시퀀스를 이용하므로, 값을 찾을 때도 $X$ 개의 슬롯을 거칠 것입니다.

만약 당시의 로드 팩터가 $p/m$ 이었다면, 이 경우 $X$ 의 기댓값 $E_p[X]$ 는 앞서 구한 $E[X]$ 를 이용해 얻습니다.

E_p[X] \leq \frac{1}{1-(p/m)} = \frac{m}{m-p}

그리고 각 $p$ 가 같은 확률로 나타난다고 하면, $X$ 의 기댓값 $E[X]$ 를 얻습니다.

\begin{align*} E[X] &= \frac{1}{n} \sum_{p=0}^{n-1} E_p[X] \\ &= \frac{1}{\alpha} \sum_{p=0}^{n-1} \frac{1}{m-p} \\ &= \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*}

이로부터 $T_s = 1 + cX$ 를 이용해 다음과 같이 시간 복잡도의 기댓값 $E[T_s]$ 를 얻습니다.

E[T_s] = 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): 스트링에 대한 해시 함수.
Java Microbenchmark Harness (JMH): 자바 코드의 소요 시간 측정에 사용한 도구.