소개
키, 값 쌍으로 데이터를 저장하는 자료구조. 데이터 삽입, 검색, 삭제가 빠르다. (스위프트에서 사용하는 딕셔너리도 해시 테이블이다.)
해시 테이블은 키를 배열의 인덱스로 직접 사용하는 대신, 해시 함수를 통해 키를 일정한 범위의 해시 값으로 변환한다. 이 덕분에 배열 전체를 순회하지 않고도 데이터가 저장된 위치에 빠르게 접근할 수 있다.
구조
해시 테이블은 배열과 해시 함수로 구성된다.
- 배열: 데이터를 저장할 배열, 배열의 인덱스는 해시 값을 뜻함
- 해시 함수: 키를 해시 값으로 변환하는 함수
키를 해시 함수에 넣어서 계산된 해시 값을 기반으로, 배열의 인덱스에 값을 저장한다.
예를 들어 문자열 키를 해시 함수에 넣은 결과가 3이라면, 해당 데이터는 배열의 세 번째 인덱스에 저장된다. 이후 같은 키를 검색할 때도 동일한 해시 함수를 사용하므로 데이터가 저장된 위치에 바로 접근할 수 있다.
동작 원리
해시 테이블은 일반적으로 다음 순서로 동작한다.
- 키를 해시 함수에 전달한다.
- 해시 함수가 키를 해시 값으로 변환한다.
- 해시 값을 배열의 인덱스로 사용한다.
- 해당 인덱스에 값을 저장하거나, 저장된 값을 조회한다.
서로 다른 키가 같은 해시 값으로 변환되어 충돌하는 경우도 있다. 이런 경우엔 따로 처리를 해줘야 한다.
특징
장점
- 빠른 삽입, 삭제, 검색
- 키를 이용해 데이터에 직접 접근할 수 있음
- 적절한 해시 함수와 충분한 공간이 있다면 평균적으로 O(1)의 성능을 기대할 수 있음
단점
- 해시 충돌을 처리할 방법이 필요함
- 해시 테이블을 너무 크게 만든 경우에는, 메모리가 낭비될 가능성이 있음
- 해시 함수의 품질이나 충돌 처리 방식에 따라 성능이 크게 달라질 수 있음
- 데이터가 정렬된 순서로 저장된다는 보장이 없음
해시 충돌 처리
- 체이닝
- 각 배열 슬롯을 링크드 리스트로 만들어서 충돌이 일어난 새로운 값을 노드 형태로 추가하여 저장함
- 링크드 리스트가 너무 커진 경우에 성능 저하가 발생함
- 충돌이 발생해도 데이터를 연결하여 저장하므로 오픈 어드레싱보다 리사이징의 필요성이 상대적으로 낮다.
- 오픈 어드레싱
- 다른 빈 슬롯을 찾아서 데이터를 저장하는 방식
- 선형 탐사(다음 빈 슬롯에 저장), 제곱 탐사(인덱스를 제곱하여 빈 슬롯을 찾으면 저장), 더블 해싱(2차 해시 함수를 만들어서 저장)이 있음
- 탐사 방식에 따라 구현이 복잡해질 가능성이 있음
- 해시 테이블을 리사이징 해야할 필요가 있음
리사이징과 Load Factor
해시 테이블에 데이터가 지나치게 많이 저장되면 빈 슬롯이 줄어들고 충돌 가능성이 높아진다. 이를 판단하기 위해 현재 저장된 데이터 수를 배열 크기로 나눈 Load Factor를 사용한다.
Load Factor가 일정 기준을 넘으면 더 큰 배열을 만들고 기존 데이터를 다시 배치한다. 이 과정에서는 배열의 크기가 달라지기 때문에 기존 키의 해시 인덱스도 다시 계산해야 한다.
시간/공간 복잡도
해시 충돌이 적고 데이터가 고르게 분산된 경우 삽입, 삭제, 검색은 평균적으로 O(1)에 수행되지만, 모든 키가 같은 인덱스에 몰리는 최악의 경우에는 O(n)까지 느려질 수도 있다.
- 삽입: 평균 O(1), 최악 O(n)
- 삭제: 평균 O(1), 최악 O(n)
- 검색: 평균 O(1), 최악 O(n)
- 공간 복잡도: O(n)