1. 해시 함수 (Hash Function)
- 어떤 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수
- hashing : 해시 함수를 적용하는 암호화 과정
- key : 해시 함수 input
- hash : 해싱 결과
- 대표적 해시 함수의 종류?
2. 해시 테이블 (Hash Table)
- indexing에 해시를 이용하는 자료구조
- 해시값으로 index를 만들고 index의 slot에 넣고자 하는 value 저장
- 충돌이 없다는 가정 하에 삽입, 삭제, 검색 모두 O(1)
- 파이썬의 dictionary도 해시 테이블임 (collision 없는 해시 테이블?)
- 데이터 정렬하지 않은 상태로 저장하기 때문에 해시에 저장된 데이터를 정렬된 순서로 접근하는 것은 비용이 많이든다
3. 충돌
- 서로 다른 데이터의 해시값이 같은 경우, 테이블의 같은 인덱스에 여러개의 value가 저장되는 경우
- 해결 방법에는 seperate chaining, open addressing 등이 있음
3-1. 개별 체이닝 (seperate chaining)
- slot을 연결리스트로 만들어 해시값이 겹치는 데이터들을 함께 저장
- slot에 key, value를 함께 저장하여 연결리스트 내에서 검색할 수 있도록??
- 최악의 경우(모든 데이터가 하나의 해시값) 삭제, 검색이 O(n)
- 삽입의 경우에는 연결리스트 head에만 삽입하면 O(1) 유지 가능
3-2. open addressing
- 이미 존재하는 해시값일 경우 탐사(probing)을 통해 다른 해시값을 부여해주는 방식
- 탐사 방법에는 linear probing, quadratic probing, double hashing 등이 있음
- 최악의 경우(모든 해시를 탐사) 삽입, 삭제, 검색이 O(n)
3-3. 충돌 해결 방법 장단점 비교?
- TODO
3-4. 충돌 해결?
- 위의 방법들을 써서 충돌 해결을 한다고 해도 충돌로 인한 성능저하를 막을수는 없음
- 데이터가 많이 쌓일수록 성능도 저하
- 수용률이 일정 수준 이상 되면 저장공간을 늘리고 데이터를 재배치하던가 해야함
- 해시의 비트 수와 저장공간을 늘리는 consistent hashing 방법도 있음
이미지 출처
hi