해시 테이블(Hash Table)은 데이터를 연관(associative) 방식으로 저장하는 자료구조입니다. 해시 테이블에서 데이터는 배열 형태로 저장되며, 각 데이터 값은 고유한 인덱스 값을 가집니다. 따라서 원하는 데이터의 인덱스만 알고 있다면 데이터에 매우 빠르게 접근할 수 있습니다.
이러한 특성 덕분에 해시 테이블은 데이터 크기와 무관하게 삽입과 검색 연산이 매우 빠른 자료구조가 됩니다. 해시 테이블은 배열을 저장 매체로 사용하고, 해시 기법을 활용해 요소를 삽입하거나 찾아야 할 위치의 인덱스를 생성합니다.
해싱(Hashing)이란?
해싱은 키(key) 값의 범위를 배열 인덱스의 범위로 변환하는 기술입니다. 일반적으로 나머지 연산자(%)를 사용해 키 값을 인덱스 범위로 매핑합니다. 크기가 20인 해시 테이블에 다음 항목들을 저장한다고 가정해 보겠습니다. 각 항목은 (키, 값) 형태로 구성됩니다.
여기서 해시 함수는 키를 입력받아 테이블의 인덱스를 생성합니다. 이 인덱스를 통해 해당 값이 어디에 저장되어 있는지 알 수 있습니다. 이후 특정 키와 연관된 값을 검색할 때는 키에 대해 해시 함수를 다시 실행하기만 하면 되므로, 거의 일정한 시간(O(1)) 안에 값을 얻을 수 있습니다.
하지만 해시 함수를 설계하는 것은 생각보다 까다롭습니다. 간단한 예제를 살펴보겠습니다.
예제
function modBy11(key) {
return key % 11;
}이 함수를 저장하려는 키-값 쌍에 적용하면 다음과 같은 결과가 나옵니다.
- (15, 20) → 해시 코드: 4
- (25, 39) → 해시 코드: 3
- (8, 55) → 해시 코드: 8
- (26, 84) → 해시 코드: 4
결과를 보면 충돌(collision)이 발생했음을 알 수 있습니다. 즉, 먼저 키 15를 저장한 상태에서 같은 해시 함수로 키 26을 처리하면 두 항목이 동일한 인덱스(4번 슬롯)에 저장되려고 합니다. 이런 상황을 충돌이라고 부르며, 이를 처리하기 위해서는 별도의 충돌 해결(collision resolution) 메커니즘이 필요합니다. 대표적인 충돌 해결 알고리즘은 다음과 같습니다.
- 선형 탐사(Linear Probing): 충돌이 발생하면 배열에서 비어 있는 다음 셀을 순차적으로 찾아 그곳에 데이터를 저장합니다. 위 예제에서 4번 슬롯이 이미 차 있으므로, 바로 다음인 5번 슬롯에 저장하게 됩니다.
- 분리 연결(Separate Chaining): 해시 테이블의 각 슬롯을 리스트(연결 리스트 등)와 연결합니다. 충돌이 발생하면 해당 리스트의 끝에 키-값 쌍을 추가합니다. 구현이 간단하지만, 체인이 계속 길어지면 검색 시간이 크게 늘어날 수 있습니다.
지금까지 해시 테이블의 동작 원리와 충돌 해결 방법을 살펴봤습니다. 이제 이를 바탕으로 실제 HashTable 클래스를 구현해 보겠습니다.
구현할 메서드
우리가 구현할 HashTable 클래스에는 다음 메서드들이 포함됩니다.
put(key, value): 해시 테이블에 새로운 키-값 쌍을 추가합니다.get(key): 특정 키와 연관된 값을 조회합니다.remove(key): 테이블에서 해당 키-값 쌍을 삭제합니다.forEach(): 모든 키-값 쌍을 순회(iterate)할 수 있게 해줍니다.static join(): 두 개의 해시 테이블을 하나로 합쳐 새로운 해시 테이블을 반환하는 정적(static) 메서드입니다.