해시 테이블
(Key, Value)로 데이터를 저장하는 자료구조
각각의 key 에 해시함수를 적용, 고유한 index를 생성하고 index에 종속되는 버킷(슬롯)에 값을 저장
- 장점
- 빠른 CRUD 가능
- 단점
- 해시 충돌이 발생할 경우 처리 속도가 느려짐
- 해시 함수의 로직이 복잡할수록 처리 속도가 느려짐
- 데이터가 순차적으로 저장되지 않아 빈 공간이 발생하기 때문에, 메모리 효율이 떨어지고 데이터 순서가 보장되지 않음.
평균 O(1)의 시간복잡도를 가지고 있지만
해시 충돌시, Chaining에 연결된 리스트들까지 검색하므로 O(n)
[ 활용 예시 ]
- Python의 Dictionary 자료형
- Mongo DB
- 캐시 메모리
해시 함수
임의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수
해시 함수는 서로 다른 두 값을 해싱했을 때, 중복이 발생할 수 있다 ( 해시 충돌 )
- 나눗셈 방법 (Division Method)
숫자로 된 Key 값 k 를 테이블의 크기 m 로 나누어 계산
h(k) = k mod m- 접기 방법 (Digit Folding)
각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 주소로 사용 ( ex: 이동 접기, 경계 접기 등 )- 곱하기 방법 (Multiplication Method)
숫자로 된 Key 값 k, 0 과 1 사이의 실수 A, 2의 제곱수인 m을 사용하여 변환한 값을 주소로 사용
h(k) = (k * A * mod1) * m- 범용 해싱 (Univeral Hashing)
다수의 해시함수를 만들고, 데이터를 입력시 무작위로 해시 함수를 선택하여 변환
해시 충돌 (Hash Collision)
# 분리 연결법 (Separate Chaining)
= 열린 해시법
각 버킷에 대응하는 연결 리스트를 생성, 해시 충돌시 리스트의 마지막 노드로 해당 데이터를 추가
# 개방 주소법 (Open Addressing)
= 닫힌 해시법
한 버킷에 하나의 데이터만 저장, 해시 충돌시 Key를 재해싱(rehashing) 하여 빈 버킷에 데이터를 저장
- 선형 탐사 (Linear Probing)
충돌이 발생한 hash 부터 고정폭만큼 이동하여 저장함
데이터가 밀집되는 현상인, Clustering 발생 가능- 제곱 탐사 (Quadratic Probing)
충돌이 발생한 hash 부터 n^2의 폭만큼 이동하여 저장함- 이중 해싱 (Double Hashing Probing)
충돌이 발생하면 또 다른 hash function 으로 처리
clustering 문제를 해결하기 위해 도입
기존 Hash는 최초 hash 변환 시 사용, 다른 Hash 는 충돌 발생 시 탐사의 폭을 얻기 위해 사용
출처 : 사진 클릭 시 이동
