Hash table
테이블 (table) :
데이터를 구조화해 저장하는 자료구조로 key-value 쌍으로 데이터를 입력 받아 키를 입력해 해당 쌍의 데이터를 찾아온다.
해시 테이블:
- 큰 테이블 하나를 키로 생각해서 key-value 쌍으로 데이터를 입력받는다.
- 해시 함수를 이용해 데이터를 고유한 해시값으로 인덱싱해서 전체 데이터 보다 작은 크기의 배열을 형성한다.
→ 충돌이 없다면 데이터를 한 번에 찾을 수 있어 효율적인 탐색( 빠른 탐색 ) 을 위한 자료구조이다.
시간복잡도:
- 해시 테이블의 평균 시간 복잡도는 O(1) 이다. 즉, 해시 테이블에서 데이터를 검색하거나 삽입하는 데 걸리는 평균 시간은 상수 시간에 해당한다.
해시 테이블은 빠른 검색 속도를 제공하며, 삽입과 삭제 연산도 상수 시간에 가깝게 수행될 수 있어 많은 데이터를 효율적으로 처리할 때 유용하다. 그러나 해시 함수의 선택과 충돌 해결 방법의 올바른 구현이 중요하며, 최악의 경우 충돌이 많이 발생할 경우 성능이 저하될 수 있다.
Direct-address Table
직접 주소화 테이블
배열을 사용해 각 키에 대한 인덱스를 사용하여 키-값 쌍을 저장하는 자료구조, key 값으로 k를 갖는 원소는 인덱스 k에 저장
키의 범위가 작고 연속적인 경우에 유용하며, 키를 직접 인덱스로 사용하여 배열에 접근하여 값을 저장하거나 검색할 수 있다.
공간 복잡도:
직접 주소화 테이블은 저장할 수 있는 키의 범위가 제한되어 있어 공간 복잡도가 상대적으로 높을 수 있다. 예를 들어, 키의 범위가 0부터 m까지이면 배열의 크기는 m+1이 된다.
→ 즉 불필요한 공간의 낭비가 발생
시간 복잡도:
직접 주소화 테이블은 키를 배열의 인덱스로 사용하여 바로 해당 위치에 접근하여 값을 저장하거나 검색할 수 있다. 따라서 데이터를 검색하거나 삽입하는 데 걸리는 시간 복잡도는 O(1) 즉, 상수 시간에 해당한다.
문제:
- 불필요한 공간 낭비
- key에 다양한 자료형을 담을 수 없다.(key가 즉 index니까)
- 서로 다른 키들이 같은 인덱스를 가리키는 경우 충돌 발생
Hash Table
해시 함수 h를 이용해 (key, value) 를 index : h(k) 에 저장
키 k 값을 가지는 원소가 위치
h(k)에 해시된다.
h(k)는 키 k의 해시값이다.
- 키는 무조건 존재하며 중복된 키가 있어서는 안된다.
- 해시 테이블을 구성하는 key, value 데이터 각각의 저장 공간을 slot 또는 bucket 이라 한다.
Collision
collision ( 충돌 ):
서로 다른 키의 해시값이 같은 상황, 중복되는 key는 없지만 해시 값이 중복되어 같은 데이터를 가리키는 상황
해결
- 개방주소법(open addressing)
- 개별 체이닝(seperate chaining)
개방 주소법
인덱스 위치가 충돌한다면 정한 규칙에 따라 빈 슬롯을 찾을 때까지 검사
추가적인 메모리 공간이 필요 없고 테이블이 가득 차면 삽입이 어렵다.
- 선형 탐사 (linear prob)
인덱스 위치가 충돌한다면 빈 slot을 찾을 때까지 내려간다. 배열의 끝에 도달하면 다시 처음으로 돌아가서 빈 slot을 탐색 (wrapping around : 배열을 원형으로 생각해 탐색)
- 이차 탐사(Quadratic Probing):
충돌이 발생했을 때 현재 위치에서부터 일정한 간격을 이용하여 다음 위치를 찾는 방법
- 일반적으로는 이차식의 형태로 간격을 결정한다. 예를 들어, 다음 위치를 찾을 때는 현재 위치에서 1, 4, 9, 16, ... 만큼 이동하는 방식
- 이차 탐사는 선형 탐사와 달리 일정한 간격이 아니라 제곱 수의 간격을 이용하기 때문에 클러스터링(Clustering) 현상을 줄일 수 있다. 하지만 이차 탐사 역시 일정한 패턴을 가지고 이동하기 때문에 빈 슬롯을 찾는 데 어려움이 있을 수 있다.
- 이중 해싱(Double Hashing):
두 개의 해시 함수를 사용하여 충돌을 해결하는 방법
충돌이 발생했을 때 두 번째 해시 함수를 사용하여 다음 위치를 결정한다. 이때 두 번째 해시 함수는 키와 상관없이 일정한 범위 내에서 값을 반환해야 한다.
-
이중 해싱은 충돌된 위치에서부터 일정한 간격이 아닌 다른 위치로 이동하기 때문에 클러스터링 문제를 해결할 수 있다.
-
또한, 두 번째 해시 함수가 독립적으로 정의되기 때문에 일정한 패턴이 나타나지 않아 빈 슬롯을 더 쉽게 찾을 수 있다.
→ 하나의 해시함수는 최초의 해시값을 얻을 때 사용, 또 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용
개별 체이닝
해시 테이블에서 충돌 발생 시 각 해시에 해당하는 slot에 linked list를 추가해 데이터를 저장, 추가적인 메모리 공간 사용
해시 테이블의 크기가 고정되어 있을 때에도 효율적으로 동작하며, 연결 리스트의 구현 방법에 따라 메모리 소비를 최적화할 수 있다.
충돌된 데이터들은 연결 리스트의 형태로 슬롯에 저장되고, 이를 통해 동일한 해시 값에 대한 다수의 데이터를 하나의 슬롯에 저장할 수 있다.
- 검색 : 데이터를 검색할 때는 해당 키의 해시 값을 계산하여 해당 슬롯의 연결 리스트를 탐색한다. 기본 시간복잡도는 O(1)이지만 최악의 경우 O(n)의 시간 복잡도를 갖는다.
- 삽입: 데이터를 삽입할 때도 마찬가지로 해당 슬롯의 연결 리스트에 노드를 추가해 (key, value) 데이터 쌍을 저장한다. 시간복잡도는 O(1)이다.
- 삭제: 삭제를 위해선 검색이 필요하기 때문에 검색과 같은 시간복잡도를 갖는다.
장점
- 공간 활용: 개별 체이닝은 해시 테이블의 슬롯에 연결 리스트를 저장하기 때문에 슬롯이 가득 차도 추가적인 데이터를 저장할 수 있다.
- 평균적으로 개별 체이닝은 충돌을 효율적으로 해결할 수 있다. 검색 및 삽입 연산의 시간 복잡도는 O(1 + α)입니다. 여기서 α는 충돌된 데이터의 평균 개수를 의미
🎯 개별 체이닝은 기본적으로 linked list를 이용해 데이터를 저장하지만 충돌이 많이 발생해 연결 리스트의 길이가 길어지면 BST 자료구조로 데이터를 저장하기도 한다.
→ BST를 사용해 worst case의 시간복잡도를 O(n) → O(logn)으로 낮출 수 있다.
🧀 worst case의 시간 복잡도 O(n)
n개의 모든 키가 동일한 해시값을 가져 길이 n의 연결리스트가 생성되는 경우
특정 키를 찾기 위해서는 길이 n의 연결리스트를 검색하는 O(n)의 시간복잡도와 동일하게 된다.
