해시 테이블

해시 테이블(hash table)은 키를 해시 함수(hash function)로 숫자로 바꾸고, 그 숫자로 배열(array)의 칸 위치를 정해 값을 두는 자료구조(data structure)다. 칸 위치를 계산 한 번으로 알아내므로 원소가 아무리 많아도 평균적으로 원소 수와 상관없는 일정한 시간(O(1))에 찾고 넣지만, 서로 다른 키가 같은 칸으로 몰리면 최악에는 원소 수에 비례하는 시간(O(n))까지 느려진다. 이 문서는 해시 함수가 칸을 정하는 방식과, 이 충돌을 처리하는 두 가지 방법을 다룬다.

해시 함수가 칸을 정한다

해시 테이블의 배열 칸 하나하나를 버킷(bucket)이라 부른다. 키를 넣을 버킷 번호는 보통 해시 함수가 내놓은 숫자인 해시 값을 배열 길이로 나눈 나머지(hash(key) % 배열 길이)로 정한다. 찾을 때도 같은 계산을 다시 하면 같은 버킷이 나오므로, 배열 전체를 훑지 않고 그 칸만 보면 된다.

다이어그램 로딩…

위 해시 값은 설명을 위한 예다. 좋은 해시 함수는 세 가지 조건을 갖춘다.

• 같은 키는 늘 같은 값: 넣을 때와 찾을 때 값이 다르면 다른 버킷을 보게 되어 넣은 값을 잃는다.
• 고르게 퍼뜨림: 키들이 버킷에 고르게 흩어져야 한 칸에 몰리지 않는다.
• 빠른 계산: 해시 계산 자체가 느리면 O(1)이라는 장점이 줄어든다.

해시 충돌은 피할 수 없다

해시 충돌(hash collision)은 서로 다른 키가 같은 버킷으로 가는 것이다. 키가 될 수 있는 값(예: 모든 문자열)은 사실상 무한한데 버킷 수는 유한하다. 비둘기집 원리(pigeonhole principle)는 "비둘기가 집보다 많으면 어떤 집에는 두 마리 이상이 들어간다"는 단순한 사실인데, 이 원리 때문에 충돌은 반드시 생긴다. 그래서 해시 테이블 설계의 핵심은 충돌을 없애는 것이 아니라 충돌이 났을 때 어디에 저장할지 정하는 것이다.

체이닝

체이닝(chaining)은 버킷마다 연결 리스트(linked list)를 매달고, 같은 버킷에 온 원소를 그 리스트에 이어 붙이는 방식이다. 찾을 때는 버킷을 계산한 뒤 그 리스트를 앞에서부터 훑으며 키를 비교한다. 구현이 단순하고 배열 칸 수보다 원소가 많아져도 계속 넣을 수 있다. 대신 리스트의 노드(node)가 메모리 곳곳에 흩어져 있어, 리스트를 따라갈 때마다 캐시 메모리(cache memory)에 없는 주소를 읽게 되어 느려지기 쉽다. 또 노드마다 다음 노드의 주소를 담는 포인터(pointer)를 따로 들고 있어야 해서 메모리를 더 쓴다.

다이어그램 로딩…

개방 주소법

개방 주소법(open addressing)은 모든 원소를 배열 칸 안에 직접 넣고, 충돌이 나면 정해진 규칙으로 다른 빈칸을 찾아간다. 빈칸을 찾아 차례로 칸을 들여다보는 것을 탐사(probing)라 한다.

• 선형 탐사(linear probing)는 바로 다음 칸, 그다음 칸 순서로 본다. 이웃 칸은 메모리에 붙어 있어 한 번 캐시 메모리로 가져오면 다음 칸도 함께 들어오므로 빠르지만, 찬 칸이 한 덩어리로 뭉치는 군집화(clustering)가 생겨 그 근처에 오는 키마다 탐사가 길어진다. 예를 들어 버킷이 8개이고 A·B·C 세 키의 해시 결과가 모두 3번이면, A는 3번, B는 3번이 차 있으니 4번, C는 3·4번이 차 있으니 5번에 들어간다. 이제 해시 결과가 4번인 D는 원래 자리가 아닌 6번까지 밀린다. 이렇게 한 덩어리가 커질수록 그 근처로 오는 모든 키가 덩어리 끝까지 탐사해야 한다.
• 이차 탐사(quadratic probing)는 1², 2², 3²칸씩 점점 멀리 뛰어 본다. 덩어리는 줄지만, 같은 버킷에서 출발한 키들은 여전히 같은 순서로 칸을 보므로 그 키들끼리는 계속 서로 부딪치며 탐사가 길어진다.
• 이중 해싱(double hashing)은 두 번째 해시 함수로 뛰는 간격을 키마다 다르게 정한다. 뭉침이 가장 적은 대신 해시를 두 번 계산한다.

개방 주소법에서는 원소를 지울 때 칸을 그냥 비우면 안 된다. 찾기는 빈칸을 만나면 "이 키는 없다"고 멈추는데, 중간 칸이 비어 버리면 그 뒤로 밀려 들어간 키를 못 찾게 된다. 그래서 칸에 "지워졌음" 표시(tombstone)를 남긴다. 찾기는 이 표시를 지나쳐 계속 탐사하고, 넣기는 이 칸을 다시 쓴다.

이어지는 내용은 해시 테이블 2에서 다룬다.

면접 포인트

• "해시 테이블이 왜 O(1)인가요?" → 해시 값으로 버킷 위치를 계산해 바로 접근. 단 평균이고 최악은 O(n).
• "좋은 해시 함수의 조건은?" → 같은 키는 늘 같은 값, 고르게 퍼뜨림, 빠른 계산.
• "충돌은 어떻게 해결하나요?" → 체이닝(버킷에 리스트) vs 개방 주소법(선형·이차 탐사, 이중 해싱). 개방 주소법 삭제는 표시(tombstone)로.