해시테이블이란?
데이터를 (key, value) 쌍으로 저장하고, 키를 통해 빠르게 값에 접근할 수 있는 자료구조입니다. 배열과 달리 인덱스가 아닌 키를 사용하지만, 내부적으로는 배열과 해시함수를 사용합니다.
키를 입력 → 해시함수로 인덱스를 계산 → 해당 인덱스에 값을 저장
해시함수란?
키를 입력하면 해시함수로 인덱스를 계산해 해당 위치에 값을 저장한다고 위에서 말했는데요, 그렇다면 해시함수란 무엇일까요?
해시함수는 키를 입력받아 고정된 범위의 정수(인덱스)로 변환하는 함수입니다. 좋은 해시함수는 다음 조건들을 만족해야 합니다 :
•
동일한 키에 대해 항상 같은 인덱스를 반환할 것
•
키들이 균등하게 분포되도록 할 것(충돌 최소화)
•
계산 속도가 빠를 것
충돌(Collision)이란?
위에서 충돌을 최소화해야 좋은 해시함수라고 했는데, 그렇다면 충돌이란 무엇일까요?
해시함수는 동일한 키에 대해 항상 같은 인덱스를 반환하는게 좋은 해시함수라고 했습니다. 다만, 늘 동일 키에 대해 동일 인덱스를 반환하는 것만은 아닙니다. 다른 키인데도 같은 인덱스를 반환해 데이터 저장 위치가 동일하게 되는(= 동일 인덱스에 매핑되는) 현상을 충돌이라고 합니다.
충돌은 피할 수 없기 때문에, 이를 어떻게 처리하느냐가 해시테이블의 성능을 좌우한다고 합니다. 여러 방법으로 충돌을 해결할 수 있는데요, 이 중 대표적인 2가지를 말해보고자 합니다.
충돌해결방법 1 : 체이닝(Chaining)
동일 인덱스를 반환해 충돌이 발생한 경우, 체이닝은 해당 인덱스에 여러 데이터들을 연결리스트로 저장하는 방식입니다. 그냥 동일 인덱스에 리스트로 연결해주면 되니, 복잡할 것 없이 단순한 방법이죠. 그렇지만 해시테이블은 키를 통해 빠르게 값에 접근할 수 있는 자료구조임에도 불구하고 체이닝 방식으로 인해 연결 리스트에 5만 개의 데이터가 붙어있다고 생각하면, 최악의 경우 O(N)만큼 다시 순회해야하는 시간 낭비가 발생합니다(= 성능 저하).
충돌해결방법 2 : 개방주소법(Open Addressing)
개방주소법은 충돌이 발생하면 다른 빈 공간을 탐색해 빈 공간에 데이터를 저장하는 방식입니다. 체이닝에 비해 뭔가 한 번 더 처리함으로써 충돌을 해결하죠. 그만큼 구현도 간단하지 않다는 단점이 있습니다.
개방 주소법 방식에는 다시 여러 가지 방법이 있습니다. 우선 개방주소법의 대표적인 두 가지에 대해 간단히 얘기하겠습니다.
개방주소법 1 : 선형탐사
선형탐사는 충돌 발생 인덱스의 근처에 선형적으로 인덱스를 증가시켜 탐색하며 빈 공간에 데이터를 추가하는 방식입니다.
개방주소법 2 : 이차탐사
이차탐사는 충돌 발생 인덱스에서 제곱수만큼 인덱스를 증가시켜 탐색하며 빈 공간에 데이터를 추가하는 방식입니다.
시간복잡도
모든 데이터가 충돌이 발생하는 최악의 경우엔 O(N)입니다만, 잘 설계된 해시함수와 충분한 공간을 활용하면 대부분 O(1)의 시간을 보장합니다.