JavaScript 해시 테이블에서 요소 제거하기 – splice()로 구현하는 remove 메서드

해시 테이블(hash table)에서 요소를 제거하는 작업은 의외로 간단합니다. 먼저 주어진 키(key)에 해당하는 요소를 찾은 뒤, 배열에서 요소를 제자리(in-place)로 삭제해 주는 splice() 함수를 호출하기만 하면 됩니다.

remove 메서드 구현

해시 테이블은 서로 다른 키가 같은 해시 코드를 가질 수 있기 때문에, 하나의 버킷(bucket)에 여러 요소가 체인(chain) 형태로 저장될 수 있습니다. 따라서 삭제 시에는 해당 체인 안에서 키가 일치하는 요소를 직접 찾아 제거해야 합니다.

remove(key) {
   let hashCode = this.hash(key);

   for (let i = 0; i < this.container[hashCode].length; i++) {
      // 체인에서 키가 일치하는 요소 찾기
      if (this.container[hashCode][i].key === key) {
         this.container[hashCode].splice(i, 1);
         return true;
      }
   }
   return false;
}

동작 과정을 단계별로 정리하면 다음과 같습니다.

• 해시 계산: hash() 메서드로 키의 해시 코드를 구해 저장 위치(버킷)를 찾습니다.
• 요소 탐색: 해당 버킷의 배열을 순회하며 키가 일치하는 요소를 찾습니다.
• 삭제 처리: 일치하는 요소를 발견하면 splice(i, 1)로 배열에서 제거하고 true를 반환합니다.
• 실패 처리: 끝까지 찾지 못했다면 false를 반환합니다.

테스트 예제

let ht = new HashTable();

ht.put(10, 94); ht.put(20, 72);
ht.put(30, 1);
ht.put(21, 6);
ht.put(15, 21);
ht.put(32, 34);

console.log(ht.get(20));
console.log(ht.remove(20));
console.log(ht.get(20));
console.log(ht.remove(20));

실행 결과

{ key: 20, value: 72 }
true
undefined
false

첫 번째 remove(20) 호출에서는 키 20이 해시 테이블에 존재하여 성공적으로 삭제되었기 때문에 true가 반환되었습니다. 이후 get(20)의 결과가 undefined로 출력되는 것에서 요소가 실제로 제거되었음을 확인할 수 있습니다. 반면 두 번째 remove(20) 호출에서는 이미 삭제되어 더 이상 존재하지 않는 키이므로 false가 반환됩니다.

참고로 이 구현은 최악의 경우 한 버킷 내의 모든 요소를 순회해야 하므로 시간 복잡도가 O(n)입니다. 다만 해시 함수가 키를 고르게 분포시켜 준다면 충돌이 드물게 발생하여 평균적으로 매우 빠른 속도로 동작합니다.