[바미] Hash tables - Open addressing알고리즘 구현하기

Open addressing?

Open addressing은 충돌이 발생하면 해시 테이블 내의 다른 빈 슬롯에 데이터를 저장하는 기법인데요.

Open Addressing 방식에서는 해시 충돌이 발생했을 때, 선형 탐사, 제곱 탐사, 이중 해싱 방법으로 충돌을 해결하는데요.

이것들에 대해 알아보자면

Linear Probing (선형 탐사)
해시 충돌이 발생하면, 다음 인덱스를 탐사하며 빈 공간을 찾아요. 탐사하는 인덱스는 hash(key) + i (i는 0, 1, 2, ...)와 같이 계산하죠.

Quadratic Probing (제곱 탐사)
선형 탐사의 단점을 보완하기 위해, 제곱 값을 이용해 탐사하는 방법인데 탐사하는 인덱스는 hash(key) + i^2 (i는 0, 1, 2, ...)와 같이 계산해요.

Double Hashing (이중 해싱)
해시 충돌이 발생하면, 두 번째 해시 함수를 이용해 다음 인덱스를 계산 하는데 hash(key) + i * hash2(key) (i는 0, 1, 2, ...)와 같이 계산하게 돼요.

이렇게 해서 Open Addressing 방식의 해시 테이블을 구현할 수 있는데 그 중에서 Open addressing 기법 중 선형 탐사 방법을 사용하여 구현한 해시 테이블 클래스로 구현해보겠습니다.

코드 구현(선형 탐사)

class OpenAddressingHashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size);
    this.count = 0; // 현재 저장된 데이터 개수
  }

  hashFunction(key) {
    // key의 문자열을 모두 더한 후, 해시 테이블 크기로 나눈 나머지 반환
    let sum = 0;
    for (let i = 0; i < key.length; i++) {
      sum += key.charCodeAt(i);
    }
    return sum % this.size;
  }

  put(key, value) {
    if (this.count >= this.size) {
      // 해시 테이블이 가득 찼을 경우 예외 발생
      throw new Error("Hash table is full");
    }

    let index = this.hashFunction(key);
    let i = 0;
    while (this.table[index]) {
      if (this.table[index].key === key) {
        // 이미 같은 키를 가진 데이터가 있을 경우 값 갱신 후 반환
        this.table[index].value = value;
        return;
      }

      // 선형 탐사 방법으로 다음 슬롯 탐색
      i++;
      index = (this.hashFunction(key) + i) % this.size;
    }

    // 빈 슬롯에 데이터 저장
    this.table[index] = { key, value };
    this.count++;
  }

  get(key) {
    let index = this.hashFunction(key);
    let i = 0;
    while (this.table[index]) {
      if (this.table[index].key === key) {
        // 키에 해당하는 데이터 반환
        return this.table[index].value;
      }

      // 선형 탐사 방법으로 다음 슬롯 탐색
      i++;
      index = (this.hashFunction(key) + i) % this.size;
    }

    // 데이터가 없는 경우 null 반환
    return null;
  }

  remove(key) {
    let index = this.hashFunction(key);
    let i = 0;
    while (this.table[index]) {
      if (this.table[index].key === key) {
        // 데이터 삭제
        delete this.table[index];
        this.count--;
        return true;
      }

      // 선형 탐사 방법으로 다음 슬롯 탐색
      i++;
      index = (this.hashFunction(key) + i) % this.size;
    }

    // 데이터가 없는 경우 false 반환
    return false;
  }
}

해시 함수는 문자열을 모두 더한 후, 해시 테이블 크기로 나눈 나머지를 반환하는 hashFunction 메서드로 구현하였어요.

해시 함수는 Open Addressing 방식에서도 사용돼요.

해시 함수의 동작은 Chaining과 동일한데, 주어진 키를 해시 코드로 변환하고, 그 해시 코드를 해시 테이블의 인덱스로 사용해요.

---

코드 구현(제곱 탐사)

class QuadraticHashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size);
    this.deleted = Symbol('deleted');
  }

  put(key, value) {
    const index = this.hashFunction(key);
    let i = 0;
    while (i < this.size) {
      const pos = this.probe(index, i);
      if (this.table[pos] === undefined || this.table[pos] === this.deleted) {
        this.table[pos] = { key, value };
        return true;
      } else if (this.table[pos].key === key) {
        this.table[pos].value = value;
        return true;
      }
      i++;
    }
    return false;
  }

  get(key) {
    const index = this.hashFunction(key);
    let i = 0;
    while (i < this.size) {
      const pos = this.probe(index, i);
      if (this.table[pos] === undefined) {
        return null;
      } else if (this.table[pos].key === key) {
        return this.table[pos].value;
      }
      i++;
    }
    return null;
  }

  remove(key) {
    const index = this.hashFunction(key);
    let i = 0;
    while (i < this.size) {
      const pos = this.probe(index, i);
      if (this.table[pos] === undefined) {
        return false;
      } else if (this.table[pos].key === key) {
        this.table[pos] = this.deleted;
        return true;
      }
      i++;
    }
    return false;
  }

  hashFunction(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.size;
  }

  probe(index, i) {
    return (index + i * i) % this.size;
  }
}

제곱 탐사(square probing)는 충돌이 일어난 경우, 해시 버킷의 위치로부터 제곱한 값만큼 떨어진 위치를 다음 탐색 위치로 지정하는 방법인데요. 즉, 충돌 발생 시 해시 버킷의 위치로부터 i 제곱만큼 떨어진 위치를 차례로 확인해보며 빈 공간이 나타날 때까지 검색하죠.

---

코드 구현(이중 해싱)

class DoubleHashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size);
  }

  put(key, value) {
    const hash1 = hashFunction1(key, this.size);
    const hash2 = hashFunction2(key, this.size);
    let index = hash1;
    let step = 1;
    while (this.table[index] != null && this.table[index].key !== key) {
      index = (hash1 + step * hash2) % this.size;
      step++;
      if (step > this.size) {
        return false;
      }
    }
    this.table[index] = { key, value };
    return true;
  }

  get(key) {
    const hash1 = hashFunction1(key, this.size);
    const hash2 = hashFunction2(key, this.size);
    let index = hash1;
    let step = 1;
    while (this.table[index] != null) {
      if (this.table[index].key === key) {
        return this.table[index].value;
      }
      index = (hash1 + step * hash2) % this.size;
      step++;
      if (step > this.size) {
        return null;
      }
    }
    return null;
  }

  remove(key) {
    const hash1 = hashFunction1(key, this.size);
    const hash2 = hashFunction2(key, this.size);
    let index = hash1;
    let step = 1;
    while (this.table[index] != null) {
      if (this.table[index].key === key) {
        this.table[index] = null;
        let nextIndex = (index + hash2) % this.size;
        while (this.table[nextIndex] != null) {
          const nextHash1 = hashFunction1(this.table[nextIndex].key, this.size);
          const nextHash2 = hashFunction2(this.table[nextIndex].key, this.size);
          if ((nextHash1 === nextIndex || nextHash2 === nextIndex) && nextIndex !== index) {
            this.table[index] = this.table[nextIndex];
            this.table[nextIndex] = null;
            index = nextIndex;
          }
          nextIndex = (nextIndex + hash2) % this.size;
        }
        return true;
      }
      index = (hash1 + step * hash2) % this.size;
      step++;
      if (step > this.size) {
        return false;
      }
    }
    return false;
  }
}

DoubleHashTable 클래스는 put, get, remove 메소드를 구현하고 있어요.

put(key, value) 메소드는 먼저 hashFunction1을 사용하여 key의 해시값을 계산하고, 그 다음 hashFunction2를 사용하여 충돌 시에 사용할 이동 거리를 계산하게 되는데 계산된 해시값과 이동 거리를 사용하여 비어있는 위치를 찾을 때까지 해시 테이블을 순회하며 탐색하게 돼요. 그리고 찾은 위치에 { key, value } 형태의 객체를 저장하고, 성공적으로 저장했으면 true를 반환하죠.

만약 해시 테이블이 가득 차있거나, 이미 같은 key값이 해시 테이블에 존재한다면 false를 반환하게 돼요.

get(key) 메소드는 key의 해시값을 계산하고, 이동 거리를 계산한 후, 해당 위치부터 이동 거리만큼 해시 테이블을 순회하며 key값이 일치하는 객체를 찾는데 객체를 찾으면 해당 객체의 value를 반환하고, 찾지 못했을 경우에는 null을 반환하게 돼죠.

remove(key) 메소드는 key의 해시값을 계산하고, 이동 거리를 계산한 후, 해당 위치부터 이동 거리만큼 해시 테이블을 순회하며 

key값이 일치하는 객체를 찾고, 객체를 찾으면 해당 객체를 삭제하고, true를 반환하게 돼요. 그러다 만약 찾지 못했을 경우에는 false

를 반환하게 돼요

 

어떻게 사용하면 좋은가?

글 초반에 해시 함수의 충돌이 발생했을 때, 다음으로 저장할 위치를 정하기 위한 방법으로 선형 탐사, 제곱 탐사, 이중 해싱 방법들이 있다고 말씀드렸었죠? 이 중 어떤 방법을 선택해야 하는지는 사용하는 데이터에 따라 달라질 수 있어요.

선형 탐사 방법은 해시 충돌이 발생했을 때 다음 위치를 일정한 간격(보통 1)씩 이동하면서 찾는 방법인데 선형 탐사 방법은 구현이 간단하고, 해시 테이블의 공간 효율성이 높은 장점이 있지만, 클러스터링 문제가 발생할 가능성이 높아져 탐색 시간이 늘어나는 단점이 있어요.

제곱 탐사 방법은 선형 탐사 방법의 클러스터링 문제를 해결하기 위한 방법이에요. 충돌이 발생하면 1, 4, 9, 16, ... 과 같이 제곱수를 이용하여 다음 위치를 계산하여 제곱 탐사 방법은 선형 탐사 방법의 단점을 보완할 수 있지만, 해시 테이블의 크기가 소수(prime number)이어야만 충분히 좋은 성능을 보장할 수 있다는 단점이 있어요.

이중 해싱 방법은 해시 충돌이 발생했을 때, 두 개의 해시 함수를 사용하여 다음 위치를 계산하는 방법이에요.

즉, 먼저 hashFunction1을 사용하여 다음 위치를 계산하고, 충돌이 발생했을 경우 hashFunction2를 사용하여 다음 위치를 계산하죠. 이중 해싱 방법은 선형 탐사나 제곱 탐사 방법보다 클러스터링 문제가 덜 발생하며, 해시 테이블의 크기에 상관없이 좋은 성능을 보장할 수 있지만 구현이 다소 복잡하며, 두 개의 해시 함수를 선택해야 하는 단점이 있어요.

따라서 데이터의 크기, 저장 가능한 데이터 타입, 해시 함수의 성능 등 다양한 요인들을 고려하여 적절한 방법을 선택해야 해요.