자바스크립트 해시 테이블에서 요소 검색하기 - get 메서드 완벽 이해

해시 테이블에서 특정 요소를 검색하는 기능은 사실 앞서 구현한 put 메서드 안에 이미 상당 부분 포함되어 있습니다. 이번에는 해당 로직을 분리하여 get 메서드로 독립적으로 살펴보겠습니다.

get 메서드 구현 예제

get(key) {
    let hashCode = hash(key);
    for(let i = 0; i < this.container[hashCode].length; i ++) {
        // 체인(연결 리스트)에서 해당 키를 가진 요소 탐색
        if(this.container[hashCode][i].key === key) {
            return this.container[hashCode][i];
        }
    }
    return undefined;
}

동작 원리

get 메서드는 다음과 같은 순서로 동작합니다.

1. 해시 계산: 전달받은 키를 hash 함수에 넣어 해시 코드(버킷 인덱스)를 구합니다.
2. 체인 탐색: 해당 버킷에는 여러 개의 요소가 충돌로 인해 연결되어 있을 수 있으므로, 반복문을 통해 각 요소의 키와 찾고자 하는 키를 비교합니다.
3. 결과 반환: 일치하는 키를 발견하면 해당 요소 전체(키와 값)를 반환하고, 끝까지 찾지 못하면 undefined를 반환합니다.

테스트 코드

아래 코드로 직접 동작을 확인할 수 있습니다.

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.get(21));
console.log(ht.get(55));
console.log(ht.get(32));

실행 결과

위 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

{ key: 20, value: 72 }
{ key: 21, value: 6 }
undefined
{ key: 32, value: 34 }

결과 분석

키 20, 21, 32는 해시 테이블에 존재하므로 키와 값이 함께 담긴 객체가 정상적으로 반환됩니다. 반면 키 55는 저장된 적이 없기 때문에 undefined가 출력되는 것을 확인할 수 있습니다. 이처럼 해시 테이블의 검색은 평균적으로 O(1)의 시간 복잡도로 매우 빠르게 수행됩니다.