[javascript] 더블 해싱 (Double Hashing) 데이터 구조

08 Dec 2023

javascript

더블 해싱은 해시 충돌을 해결하기 위한 해싱 기법 중 하나입니다. 해시 충돌은 서로 다른 데이터가 동일한 해시 값으로 매핑되는 상황을 말합니다. 더블 해싱은 이러한 충돌을 효율적으로 해결하여 데이터를 빠르게 검색할 수 있도록 도와줍니다.

더블 해싱의 개념

더블 해싱은 두 개의 해시 함수를 사용하여 충돌을 해결합니다. 첫 번째 해시 함수로 계산된 값이 충돌이 발생하면 두 번째 해시 함수를 사용하여 새로운 주소를 찾습니다. 이러한 방식으로 충돌을 처리할 수 있고, 두 번째 해시 함수가 서로 독립적이라면 충돌을 빈번하게 일어나지 않게 할 수 있습니다.

더블 해싱은 일반적으로 hash1(key) = key % table_size와 hash2(key) = prime - (key % prime)과 같은 형태의 해시 함수를 사용합니다.

더블 해싱의 구현

아래는 자바스크립트를 사용하여 더블 해싱을 구현한 예제입니다.

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

  hash1(key) {
    return key % this.size;
  }

  hash2(key) {
    const prime = 7; // 임의의 소수
    return prime - (key % prime);
  }

  insert(key, value) {
    let index = this.hash1(key);

    if (this.table[index] === undefined) {
      this.table[index] = { key, value };
    } else {
      let hash2 = this.hash2(key);
      let i = 1;

      while (true) {
        let newIndex = (index + i * hash2) % this.size;

        if (this.table[newIndex] === undefined) {
          this.table[newIndex] = { key, value };
          break;
        }

        i++;
      }
    }
  }

  search(key) {
    let index = this.hash1(key);
    let hash2 = this.hash2(key);
    let i = 0;

    while (this.table[(index + i * hash2) % this.size].key !== key) {
      i++;

      if (i === this.size) {
        return "Not found";
      }
    }

    return this.table[(index + i * hash2) % this.size].value;
  }
}

결론

더블 해싱은 해시충돌을 피하기 위한 효과적인 방법 중 하나이며, 빠른 데이터 검색을 가능하게 합니다. 이를 통해 데이터 구조를 효율적으로 관리할 수 있습니다.

참고 문헌:

Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Wikipedia - Double Hashing