[바미] 해시 충돌 처리 방법

들어가기전에..

해시 테이블에서 해시 충돌이 발생하면, 두 개 이상의 서로 다른 키가 같은 해시 값을 가질 수 있습니다. 이를 해결하기 위해 충돌을 처리하는 다양한 방식들이 존재하는데 그 중에서 체이닝(Chaining), 개방 주소법(Open Addressing), 이중 해싱(Double Hashing)이 대표적인 방법입니다. 오늘은 이 세가지 방법에 대해 알아보겠습니다.

체이닝(Chaining)

해시 충돌을 처리하는 가장 보편적인 방법 중 하나인데 해시 테이블의 각 버킷(Bucket)을 연결 리스트나 배열과 같은 자료 구조로

만들어서 충돌이 발생한 여러 데이터를 그 안에 함께 저장하는 방식입니다.

동작 방식

• 각 버킷에는 하나의 데이터가 저장되는 것이 아니라, 여러 데이터가 연결 리스트로 연결됩니다.
• 같은 해시 값을 갖는 여러 키들이 발생하면, 해당 키들은 그 해시 값에 대응되는 버킷의 리스트에 차례대로 추가됩니다.
• 값을 검색할 때는 그 버킷에 저장된 리스트를 순차적으로 확인하여 원하는 값을 찾습니다.

장점

• 충돌이 발생할 때마다 별도의 리스트에 데이터를 저장하기 때문에, 테이블의 다른 버킷들을 건드리지 않고 데이터를 추가할 수 있습니다.
• 해시 테이블의 크기와 상관없이 데이터를 저장할 수 있기 때문에, 해시 테이블이 꽉 차는 문제는 발생하지 않습니다.

단점

• 충돌이 많이 발생하면, 각 버킷에 저장된 리스트의 길이가 길어지게 되고, 그로 인해 검색 성능이 저하될 수 있습니다.
• 최악의 경우에는 리스트의 길이가 테이블의 크기만큼 길어져 O(n) 시간이 소요될 수 있는데 이 때 해시 테이블의 이점이 사라지고 연결 리스트를 순차적으로 탐색해야 하므로 성능이 매우 저하되는 단점이 됩니다.

구현

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

  // 간단한 해시 함수 (키를 숫자로 변환)
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  // 데이터를 추가하는 함수 (체이닝 방식)
  set(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    // 충돌 발생 시 배열로 데이터를 저장
    this.table[index].push([key, value]);
  }

  // 데이터를 검색하는 함수
  get(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    if (bucket) {
      for (let i = 0; i < bucket.length; i++) {
        const [storedKey, storedValue] = bucket[i];
        if (storedKey === key) {
          return storedValue;
        }
      }
    }
    return undefined;
  }
}

const hashTableChaining = new HashTableChaining();
hashTableChaining.set('apple', 'fruit');
hashTableChaining.set('car', 'vehicle');
hashTableChaining.set('cat', 'animal');

console.log(hashTableChaining.get('apple')); // fruit
console.log(hashTableChaining.get('cat'));   // animal

결과

---

개방 주소법(Open Addressing)

체이닝과는 달리, 모든 데이터를 해시 테이블 내의 버킷에 직접 저장하여 충돌이 발생하면 다른 빈 버킷을 찾아서 데이터를 저장하는 방식입니다.

 

이 방식에서는 충돌이 발생할 때 빈 슬롯을 찾아 데이터를 저장하기 때문에, 모든 데이터가 테이블 내에 직접 저장됩니다.

대표적인 개방 주소법 방법

선형 탐사(Linear Probing)

충돌이 발생하면 다음 인덱스로 이동해 빈 버킷을 찾는 방법입니다. 만약 해시 값이 3이고, 버킷 3이 이미 차 있으면 버킷 4로, 4도 차 있으면 5로 계속 이동하며 빈 자리를 찾는 방식이죠.
선형 탐사는 구현이 간단하다는 장점이 있지만 데이터가 몰리면 클러스터링(Clustering) 현상이 발생해 빈 자리를 찾는 시간이 길어질 수 있는 단점이 존재합니다.

제곱 탐사(Quadratic Probing)

충돌 시 고정된 간격이 아닌, 제곱 형태로 간격을 증가시키며 빈 자리를 탐색하는 방식입니다. 만약 충돌이 발생하면 1, 4, 9, 16 등의 간격으로 인덱스를 이동해 빈 자리를 찾는 방식이죠.

 

이로 인해 선형 탐사보다 클러스터링 현상이 덜 발생하는 장점이 있지만 여전히 충돌이 많을 경우 성능 저하가 발생할 수 있다는 단점이 존재합니다.

이중 해싱(Double Hashing)

충돌이 발생하면, 두 번째 해시 함수를 이용하여 새로운 해시 값을 계산하고, 그 해시 값에 따라 다음 위치를 탐색하는 방식입니다.
만약 첫 번째 해시 함수로 계산한 해시 값이 충돌하면, 두 번째 해시 함수를 사용해 빈 자리를 찾는 형태죠.

충돌이 적게 발생하여 테이블의 공간을 더 효율적으로 사용할 수 있다는 장점이 있지만 해시 함수가 두 개 필요하기 때문에 복잡도가 증가할 수 있다는 단점이 존재합니다.

장점

• 체이닝과 달리 모든 데이터를 테이블 내에 저장하기 때문에, 추가적인 연결 리스트나 배열을 사용할 필요가 없습니다.
• 메모리 효율성이 체이닝보다 우수할 수 있습니다.

단점

• 테이블이 꽉 차게 되면 빈 슬롯을 찾는 과정에서 성능이 저하될 수 있습니다.
• 충돌이 빈번해지면, 특히 선형 탐사에서는 클러스터링 문제가 심각해질 수 있습니다.

구현

class HashTableLinearProbing {
  constructor(size = 10) {
    this.table = new Array(size);
    this.values = new Array(size);
  }

  // 간단한 해시 함수
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  // 선형 탐사를 사용해 데이터를 추가하는 함수
  set(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== undefined) {
      index = (index + 1) % this.table.length; // 충돌 시 다음 슬롯으로
    }
    this.table[index] = key;
    this.values[index] = value;
  }

  // 선형 탐사를 사용해 데이터를 검색하는 함수
  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== undefined) {
      if (this.table[index] === key) {
        return this.values[index];
      }
      index = (index + 1) % this.table.length;
    }
    return undefined;
  }
}

const hashTableLinear = new HashTableLinearProbing();
hashTableLinear.set('apple', 'fruit');
hashTableLinear.set('car', 'vehicle');
hashTableLinear.set('cat', 'animal');

console.log(hashTableLinear.get('apple')); // fruit
console.log(hashTableLinear.get('car'));   // vehicle

 

결과

---

이중 해싱(Double Hashing)

이중 해싱(Double Hashing)은 위에 언급했던 개방 주소법(Open Addressing)의 한 방식입니다. 

설명은 개방 주소법(Open Addressing)에서 했기 때문에 생략하도록 하겠습니다.

 

구현

class HashTableDoubleHashing {
  constructor(size = 10) {
    this.table = new Array(size);
    this.values = new Array(size);
  }

  // 첫 번째 해시 함수
  hash1(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  // 두 번째 해시 함수
  hash2(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    // 두 번째 해시는 1을 추가해 모듈러 연산을 피함
    return (hash % (this.table.length - 1)) + 1;
  }

  // 이중 해싱을 사용해 데이터를 추가하는 함수
  set(key, value) {
    let index = this.hash1(key);
    const stepSize = this.hash2(key);

    while (this.table[index] !== undefined) {
      index = (index + stepSize) % this.table.length; // 충돌 시 두 번째 해시 값으로 이동
    }

    this.table[index] = key;
    this.values[index] = value;
  }

  // 이중 해싱을 사용해 데이터를 검색하는 함수
  get(key) {
    let index = this.hash1(key);
    const stepSize = this.hash2(key);

    while (this.table[index] !== undefined) {
      if (this.table[index] === key) {
        return this.values[index];
      }
      index = (index + stepSize) % this.table.length;
    }

    return undefined;
  }
}

const hashTableDoubleHashing = new HashTableDoubleHashing();
hashTableDoubleHashing.set('apple', 'fruit');
hashTableDoubleHashing.set('car', 'vehicle');
hashTableDoubleHashing.set('cat', 'animal');

console.log(hashTableDoubleHashing.get('apple')); // fruit
console.log(hashTableDoubleHashing.get('cat'));   // animal

결과

---

마치며

해시 테이블에서 충돌 처리는 해시맵의 성능을 좌우하는 중요한 요소이고, 각 방법은 장단점이 있다는 것을 알았습니다.

먼저 체이닝은 구현이 간단하고 추가 메모리가 필요하지만, 충돌이 많아지면 성능이 저하될 수 있다는 점.

개방 주소법은 메모리를 효율적으로 사용할 수 있지만, 충돌 처리에 시간이 걸릴 수 있다는 점.

마지막으로 이중 해싱은 가장 강력한 충돌 처리 방법이지만 복잡도가 높은 편이라는 것이죠.

각 상황에 맞는 적절한 충돌 처리 방법을 선택하는 것이 해시 테이블의 성능을 극대화하는 핵심이기 때문에 적절한 처리 방법을 선택하여 해결하시길 바랍니다.