[C++ Algorithm] Ch3. 해시 테이블과 블룸 필터
3.1 들어가며
3.2 해시 테이블
해싱
해시 함수
- 어떤 데이터 값이든 원하는 범위의 정수로 매핑하는 함수
- 해시 값: 한수에 의해 반환되는 숫자
해시 함수의 문제점, 충돌
- 충돌: 해시 함수가 서로 다른 데이터에 대해 같은 해시 값 반환
- 다수의 키가 같은 값을 가지게 됨
- 해시 테이블에 키만 저장하는 것이 아닌 키와 값을 함께 저장해야 함
3.3 해시 테이블에서 충돌
체이닝
해시 테이블릐 특정 위치에서 하나의 키가 아닌 하나의 연결 리스트를 저장
- 충돌되는 값을 모두 저장할 수 있음(덮어쓰는 현상 X)
- 충돌이 발생한다면 리스트의 맨 뒤에 새로운 키를 추가
- 백터 대신 연결 리스트를 사용하는 이유 -> 특정 위치의 원소를 빠르게 삭제하기 위함
부하율(load factor)
부하율 = 전체 키 개수 / 해시 테이블 크기
- 부하율 = 1: 매우 이상적인 상태
- 부하율 < 1: 리스트당 키가 하나도 저장되지 않는 경우가 있음 -> 메모리 낭비 발생
- 부하율 > 1: 연결 리스트의 평균 길이가 1보다 큼 -> 검색, 삭제 등의 함수 느리게 작동
해시 함수는 서로 다른 키가 가급적이면 서로 겹치지 않고 골고루 분포되도록 해시 값을 만들어야 함
열린 주소 지정
모든 원소를 해시 테이블 내에 저장
- 특정 해시 값에 해당하는 위치가 이미 사용되고 있다면 테이블의 다른 비어있는 위치를 탐색
- 해시 테이블의 크기가 반드시 데이터 개수보다 커야 함
[테이블의 다른 비어있는 위치 탐색하는 방법]
- 선형 탐색
- 특정 해시 값에서 충돌이 발생하면 해당 위치에서 하나씩 다음 셀 위치로 이동하며 비어있는 셀을 확인(선형 방정식 이용) (예: x -> x + 1 -> x + 2)
- 데이터의 군집화 발생(특정 해시 값이 너무 자주 발생하여 데이터가 몇 개의 그룹으로 뭉치는 현상) -> 검색 속도 저하
- 이차함수 탐색
- 이동 폭을 이차함수 형태로 증가(이차 방정식을 이용) (예: x -> x + 1^2 -> x + 2^2)
- 선형 탐색의 문제점인 군집화 현상 감소
선형 탐색 및 이차함수 탐색은 모두 새로 삽입하려는 원소의 위치가 기존에 삽입되어 있는 다른 원소들에 의해 영향을 받음
뻐꾸기 해싱
크기가 같은 두 개의 해시 테이블 사용
- 구현만 제대로 한다면 시간 복잡도 O(1) 보장
- 각각의 해시 테이블은 서로 다른 해시 함수 사용
- 원소는 두 테이블 중 어디든 저장 가능
- 원소는 나중에 다른 위치로 이동할 수 있음(상황에 따라 이동)
- (문제점) 순환 발생 시 재해싱 수행해야 함
- 높은 성능을 보장하려면 부하율이 0.5보다 작게 설정
3.4 C++ 해시 테이블
C++에서 제공하는 해시 함수 알고리즘
- std::hash<std::string>(std::string): 문자열로부터 해시 값을 생성
- std::unordered_set
: 키를 저장 - std::unordered_map<Key, Value>: 키와 값을 함께 저장
3.5 블룸 필터
블룸 필터와 작동 과정
원소 삽입 시 모든 해시 함수 값을 계산하고 부울 타입 배열에서 해 해시값에 대응되는 위치의 비트 값을 1로 변경시킴
해시 테이블에 비해 공간 효율이 매우 놓은 방법
결정적 솔루션 대신 부정확한 결과를 얻을 수 있음
- 거짓-부정 이 없다는 것을 보장: 특정 원소 존재 x -> 확실히 없음
- 거짓-긍정 은 존재 가능: 특정 원소 존재 o -> 있을수도, 없을 수도 있음 필터 크기를 좀더 크게 설정하고 해시 함수를 보완하면 더 나은 성능을 얻을 수 있음