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