자바스크립트 해시 테이블 충돌 해결하는 방법 2가지

 

> 자바스크립트 해시 테이블 구현하는 방법에서 이어진다.

 

class HashTable {
  table = new Array(3);
 
  /// ...
}

만약 위 같이 테이블의 길이가 너무 짧은 경우에는 해시 충돌이 일어난다.

 

myTable.setItem('firstName', 'eunjin');
myTable.setItem('lastName', 'lee');
myTable.setItem('age', 29);
myTable.setItem('birth', '2000-00-00');

console.log(myTable.getItem('firstName')); // 2000-00-00
console.log(myTable.getItem('lastName')); // 2000-00-00

 

당장 key-value 4개만 집어넣어도 해시 충돌이 일어나고 값 재정의가 일어난다. 이런 상황을 앞서 정리한 해시 함수 작성을 통해 최대한 방지할 수 있겠지만 아무리 복잡하게 짠 해시 함수라도 이와 같은 일이 발생할 수 있다. 이 해시 충돌이 일어났을 때 어떻게 해결하는지 정리했다.

 

1. 체이닝(chaining)

 

 

 

체이닝은 충돌이 발생하면 해당 인덱스에 해당하는 value를 배열 또는 연결 리스트로 값을 연결해나가는 식으로 충돌 문제를 해결하는 방법이다. 하나의 해시 값에 다수의 버킷들이 저장되기 때문에 탐색을 위해서는 동일한 해시 값으로 묶여 있는 모든 버킷들을 확인해야 한다는 단점이 생긴다. 하지만 해시 함수를 잘 정의하여 모든 데이터들이 골고루 분포되게 한다면 충돌 확률이 높지 않기 때문에, 탐색에 드는 비용은 크지 않을 것이다. 

 

  setItem = (key, value) => {
    const idx = hashStringToInt(key, this.table.length);
    if (this.table[idx]) {
      this.table[idx].push([key, value]);
    } else {
      this.table[idx] = [[key, value]];
    }
  };

데이터를 setItem으로 테이블에 저장할 때, 배열 형태로 저장하는 방법이다. 단순히 key를 변환한 인덱스에 value만 저장하는 게 아니라, key, value 쌍의 배열을 하나씩 push 하는 방식으로 저장을 한다. 만약 해시 충돌이 일어나지 않았다면 그냥 key, value 쌍을 배열에 넣어 주면 되고, 이미 해당 인덱스를 차지하는 값이 존재한다면 기존 배열에 새로운 key, value 쌍을 push 해 준다.

 

  getItem = (key) => {
    const idx = hashStringToInt(key, this.table.length);
    if (!this.table[idx]) return null;

    // O(n)
    return this.table[idx].find((el) => el[0] === key)[1];
  };

그러면 getItem에서 값을 가져오는 방식도 변경해야 한다. 단순히 찾고자 하는 key 인덱스에 해당하는 값을 리턴하는 것이 아니라, 인덱스에 해당하는 배열 값 중에서 key가 같은 key, value 쌍을 찾아서 [1]을 리턴한다. 만약 값이 없는 경우를 대비해 에러 캐칭도 신경 써 준다. 

 

기존에 단순히 전체 table의 인덱스로 접근을 하는 경우에는 시간 복잡도가 O(1)이지만, 이렇게 array.find 함수를 사용하게 되면 시간 복잡도가 O(n)으로 증가한다.

 

myTable.setItem('firstName', 'eunjin');
myTable.setItem('lastName', 'lee');
myTable.setItem('age', 29);
myTable.setItem('birth', '2000-00-00');

console.log(myTable.getItem('firstName')); // eunjin
console.log(myTable.getItem('lastName')); // lee
console.log(myTable.getItem('age')); // 29
console.log(myTable.getItem('birth')); // 2000-00-00

해시 충돌이 일어나도 체이닝을 통해 값 할당이 제대로 이루어지고 있고, 탐색도 올바르게 되고 있음을 확인할 수 있다. 

 

2. 해시 테이블 사이즈 늘리기

 

체이닝 방법만 사용하면 해시 테이블을 사용하는 주 목적인 '연산 시 시간 복잡도 최소화'에 부합하지 않는다. 테이블의 사이즈는 한정되어 있는 상태에서 수많은 데이터를 일일이 체이닝 해서 저장한다면 결국 탐색과 삽입, 삭제 등에 있어서 시간 복잡도 O(n)로 연산해야 하기 때문이다.

 

class HashTable {
  table = new Array(3);
  numItems = 0;
 
   setItem = (key, value) => {
    this.numItems++;
    
    const idx = hashStringToInt(key, this.table.length);
    if (this.table[idx]) {
      this.table[idx].push([key, value]);
    } else {
      this.table[idx] = [[key, value]];
    }
  };
  
  // ...
}

해결하기 위해서는 동적으로 해시 테이블의 사이즈를 늘리는 방법이 있다. 해시 테이블의 사이즈에 바로 접근할 수 있도록 numItems 변수를 만든다. setItem을 할 때마다 numItem++ 연산을 해 주면 table에 들어 있는 값의 개수를 그때그때 반영할 수 있다. 이 값을 활용하여, table의 길이 대비 현재 들어있는 값의 개수를 연산해 특정 수준 이상으로 값이 할당이 되면 table의 길이를 늘리도록 하면 된다.

 

  setItem = (key, value) => {
    this.numItems++;
    
    const loadFactor = this.numItems / this.table.length;
    if (loadFactor >= 0.8) {
      this.resize();
    }

    const idx = hashStringToInt(key, this.table.length);
    if (this.table[idx]) {
      this.table[idx].push([key, value]);
    } else {
      this.table[idx] = [[key, value]];
    }
  };

위와 같이, setItem을 실행할 때 table에 들어 있는 원소의 개수를 판단하여 80% 이상 차 있는 경우 테이블 사이즈를 조정하게 할 수 있다. 꼭 80퍼센트일 필요는 없고 70퍼센트도 되고 60퍼센트도 되고 본인이 판단해서 적당한 수준으로 최대 비율을 설정하면 된다.

 

  resize = () => {
    const newTable = new Array(this.table.length * 2);
    this.table = newTable;
  };

리사이즈 함수를 만든다. table의 원소의 개수가 table의 길이의 80% 이상 차지하는 경우 등에서 table 사이즈를 2배 늘리는 것이다. 이 또한 꼭 2배일 필요는 없고 1.5배일 수도 있고 또는 다른 큰 소수로 table의 길이를 새로 설정해줄 수도 있다. 예를 들어 배열의 크기를 3에서 6으로 두 배를 했다면, 그보다 큰 소수인 7을 새로운 table의 크기로 설정해주는 것이다. 여기서는 간단히 2배를 한다.

 

function hashStringToInt(s, tableSize) {
  let hash = 17;

  for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize;
  }
  return hash;
}

다시 해싱 함수를 들여다보면, 이 함수는 table 길이를 파라미터로 받고 있다. 즉, table의 길이가 달라지는 즉시 해시 함수 로직도 달라지는 것이다. 따라서 해시 테이블 리사이즈가 일어나면 table 내에 있는 모든 원소에 대하여 해시 연산을 새로 해 주어야 한다.

 

  resize = () => {
    const newTable = new Array(this.table.length * 2);
    this.table.forEach((item) => {
      if (item) {
        item.forEach(([key, value]) => {
          const idx = hashStringToInt(key, newTable.length);
          if (newTable[idx]) {
            newTable[idx].push([key, value]);
          } else {
            newTable[idx] = [[key, value]];
          }
        });
      }
    });
    this.table = newTable;
  };

기존 테이블의 사이즈가 아니라, 새로 생성되는 테이블의 사이즈를 넣고 해시 함수를 실행한다. 이중 for문으로 모든 원소를 탐색하여 다시 key, value 쌍을 만들어 새로운 테이블에 넣어준다. 

 

---

 

const myTable = new HashTable();
myTable.setItem('firstName', 'eunjin');
console.log(myTable.table.length) // 3
myTable.setItem('lastName', 'lee');
console.log(myTable.table.length) // 3
myTable.setItem('age', 29);
console.log(myTable.table.length) // 6
myTable.setItem('birth', '2000-00-00');
console.log(myTable.table.length) // 6

console.log(myTable.getItem('firstName')); // eunjin
console.log(myTable.getItem('lastName')); // lee
console.log(myTable.getItem('age')); // 29
console.log(myTable.getItem('birth')); // 2000-00-00

초기 해시 테이블 table의 길이가 3으로 설정되었을 때, 길이가 3 이상이 되려고 하는 순간 먼저 table의 길이를 2배로 리사이즈하고 있고 이로써 해시 충돌을 최소화하고 있음을 알 수 있다.