[c++] 오픈 어드레싱 방식의 해시 테이블

08 Dec 2023

해시 테이블은 키-값 쌍을 저장하고 검색하는 데 사용되는 자료 구조입니다. 해시 테이블은 키의 해시 값을 사용하여 값을 저장하거나 검색하는 데 사용되는 인덱스를 계산합니다. 그러나 충돌이 발생할 수 있는데, 이를 해결하기 위해 여러 방식이 사용됩니다.

오픈 어드레싱은 해시 충돌이 발생한 경우 새로운 값을 저장하기 위해 해시 테이블 내부에서 다른 위치를 탐색하는 방식입니다. 이를 위해 일반적으로 다음 세 가지 방법이 사용됩니다.

선형 탐사 (Linear Probing)

선형 탐사는 충돌이 발생했을 때, 다음 가능한 위치를 탐색합니다. 만약 해당 위치가 이미 차있다면, 그 다음 위치를 검색합니다. 이 과정은 비어있는 슬롯을 찾을 때까지 반복됩니다.

int linearProbe(int key, int i, int size) {
    return (hash(key) + i) % size;
}

이차원 탐사는 충돌이 발생했을 때, i 제곱만큼을 더한 위치를 탐색합니다. 이를 통해 선형 탐사와는 다른 위치에 재해시할 수 있습니다.

int quadraticProbe(int key, int i, int size) {
    return (hash(key) + i * i) % size;
}

이중 해싱은 두 번째 해시 함수를 사용하여 충돌을 해결하는 방식입니다. 첫 번째 해시 함수의 결과가 충돌을 일으킨다면, 두 번째 해시 함수를 이용하여 다른 위치로 이동합니다.

int doubleHash(int key, int i, int size) {
    return (hash1(key) + i * hash2(key)) % size;
}

오픈 어드레싱 방식의 장점은 간단하고 쉽게 구현할 수 있다는 것입니다. 그러나 해당 슬롯이 삭제될 때, 검색 시 중단점을 찾기 어렵게 되는 일어납니다. 그래서 동일한 위치에 충돌이 지속되면 성능에 영향을 줄 수 있습니다.

오픈 어드레싱은 해시 테이블의 충돌을 해결하는 데 사용되는 세 가지 방식을 제공합니다. 각 방식은 장단점이 있으며, 구체적인 사용 사례에 따라 최적의 방식을 선택해야 합니다.

참고문헌: