참고 자료 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - 존캐리, 파야스라잔, 셰리안도시 저
# 3장 해시 테이블과 블룸 필터
3.1 들어가며
- 룩업(lookup, 조회)은 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업을 의미한다.
3.2 해시 테이블
- 선형 검색은 O(N)의 시간이 필요로 한다.
- 더 나은 방법은 BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것이다. 이는 시간 복잡도가 O(log N)이 되기 때문에 선형 검색보다 훨씬 바르다.
- 이보다 더 효율적인 방법에는 해시 테이블이라는 방법이 있다.
3.2.1 해싱
- 해시 테이블의 핵심은 해싱이다.
- 해싱은 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 또는 해당 숫자에 대응하는 원본 데이터를 추출하는 작업이다.
- 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수를 해시 함수라고 한다.
- 해시 함수는 데이터 원소를 인자로 받고 정해진 범위의 정수를 반환한다.
- 해시 함수에 의해 반환되는 숫자 값을 해시 값이라고 한다.
- 모듈로 함수의 문제점은 이 함수가 서로 다른 데이터에 대해 같은 해시 값을 반환할 수 있다는 점이다. 이러한 문제를 충돌이라고 한다. 충돌이란 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써, 다수의 키가 같은 값을 갖게 되는 현상을 말한다.
3.2.2 연습 문제 13: 정수 값을 저장하는 간단한 사전
- 해시 테이블을 사용할 때 단순히 해당 키가 있는지를 확인하는 것이 아니라 해당 키에 대응하는 값이 있는지를 확인해야 한다. 이를 위해 해시 테이블에 키만 저장하는 것이 아니라 키와 값을 함께 저장하는 방식을 사용해야 한다. 그러므로 삽입, 삭제, 룩업 함수에서 키를 기반으로 해시 값을 계산하여 배열에서의 위치를 알아낸 후 함쎄 저장된 값을 이용할 수 있어야 한다.
3.3 해시 테이블에서 충돌
- 해시 테이블에 모든 키를 저장할 수 있는 몇 가지 방법.
3.3.1 체이닝
- 체이닝은 두 값은 모두 저장할 수 있는 여러 방법 중 하나이다. 이 방법은 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라 하나의 연결 리스트를 저장한다. 그러므로 새로 삽입된 키에의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가한다. 따라서 다수의 원소를 원하는 만큼 저장할 수 있다.
- 벡터 대신 연결 리스트를 사용하는 이유는 특정 위치의 원소를 빠르게 삭제하기 위함이다.
3.3.2 연습 문제 14: 체이닝을 사용하는 해시 테이블
- 특정 해시 값 위치에 하나의 원소만 저장되는 것이 아니라 여러 개의 원소가 리스트 형태로 저장된다.
- 삽입 함수의 시간 복잡도는 O(1)이다.
- 룩업과 삭제는 데이터 크기와 해시 테이블 크기에 따라 상당히 느릴 수 있다. 예를들어 모든 키가 같은 해시 값을 가질 경우, 룩업 연산은 연결 리스트에서 선형 검색을 수행하는 것과 같으므로 O(N)의 시간 복잡도를 갖게 된다.
- 부하율은 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 나타내며, 다음 수식을 이용해 구할 수 있다.
- 부하율 = 전체 키 개수/ 해시 테이블 크기
- 키 개수가 해시 테이블 크기와 같다면 부하율은 1이다. 이는 매우 이상적인 상태로 모든 연산이 O(1)에 가깝게 작동하고 모든 메모리 공간을 적절하게 활용한다.
- 부하율이 1보다 작으면 리스트당 키가 하나도 저장되지 않은 경우가 있다는 것이고, 이는 메모리 낭비가 될 수 있다.
- 부하율이 1보다 크면 이는 리스트의 평균 길이가 1보다 크다는 의미이고, 이경우 검색, 삭제 등의 함수가 약간 느리게 동작할 수 있다.
- 부하율은 항상 O(1) 시간 복잡도로 계산할 수 있다. 몇몇 해시 테이블은 부하율이 1 근방의 특정 값보다 너무 크거나 작아지면 해시 함수를 변경하도록 구현되어 있으며, 이를 재해싱이라고 한다.
- 즉 해시 함수를 수정하여 부하율이 1에 가까운 값이 되도록 만드는 것이다. 변경된 해시 함수에 의한 값의 분포와 부하율을 고려하여 해시 테이블의 크기도 변경할 수 있다.
- 해시 함수는 서로 다른 키가 가급적이면 서로 겹치지 않고 골고루 분포되도록 해시 값을 만들어야 한다. 기본적으로 버킷의 최대 크기와 최소 크기의 차이가 너무 크면 좋지 않다.
- 해시 테이블은 해시 함수 구현에 종속적이지 않기 때문에 해시 함수 자체에서 잘 고려해야 한다.
3.3.3 열린 주소 지정
- 충돌을 해결하는 다른 방법으로 열린 주소 지정이 있다. 이는 모든 원소를 해시테이블 내부에 저장하는 방식이다. 그러므로 해시 테이블의 크기가 반드시 데이터 개수보다 커야 한다.
- 열린 주소 지정 방법의 핵심은 특정 해시 값에 해당하는 위치가 이미 사용되고 있다면 테이블의 다른 비어 있는 위치를 탐색하는 것이다. 이때 다른 비어있는 위치를 찾는 방법은 여러가지가 있을 수 있다.
[선형 탐색]
- 선형 탐색은 특정 해시 값에서 충돌이 발생하면 해당 위치에서 하나씩 다음 셀 위치로 이동하면서 셀이 비어 있는지를 확인하고, 비어 있는 셀을 찾으면 원소를 삽입한다.
- 데이터가 특정 위치에 군집화되는 경우에 문제가 발생하게 된다. 데이터가 군집화된다는 것은 특정 해시 값이 너무 자주 발생해서 데이터가 몇 개의 그룹으로 뭉치는 형태로 저장된다는 의미이다.
[이차함수 탐색]
- 선형 탐색의 가장 큰 문제점은 군집화이다. 충돌이 발생하면 군집을 차례대로 검사해야 하기 때문이다. 이를 해결하기 위해 선형 방정식이 아닌 이차 방정식이 아닌 이차 방정식을 사용하여 탐색을 수행할 수 있다. 이러한 방식의 탐색을 이차함수 탐색이라고 한다. 이처럼 이동 폭을 이차함수 형태로 증가시키면 데이터 군집이 나타날 확률은 상대적으로 줄어든다.
- 선형 탐색 및 이차함수 탐색은 모두 원소 위치가 기존에 삽입되어 있는 다른 원소들에 의해 영향을 받는다. 이때 기존에 저장되어 있던 원소는 새로 삽입하는 원소와 서로 다른 해시 값을 가질 수도 있다. 즉 특정 해시 값을 갖는 키가 오직 하나만 존재한다 하더라도 충돌이 발생할 수 있다.
3.3.4 뻐꾸기 해싱
- 뻐꾸기 해싱은 완벽한 해싱 기법 중의 하나이다. 앞에서 언급했던 방법들은 최악의 상황에서는 O(1)의 시간 복잡도를 보장하지 않지만 뻐꾸기 해싱은 구현만 제대로 한다면 O(1)이다.
- 뻐꾸기 해싱은 크기가 같은 두 개의 해시 테이블을 사용하고, 각각의 해시 테이블은 서로 다른 해시 함수를 가진다. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있으며, 그 위치는 해당 해시테이블의 해시 함수에 의해 결정된다.
- 뻐꾸기 해싱이 이전에 설명한 해싱 기법과 다른 점은 다음과 같다.
- 원소가 두 해시 테이블 중 어디든 저장될 수 있다.
- 원소가 나중에 다른 위치로 이동할 수 있다.
- 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없다. 그러나 뻐꾸기 해싱 방법에서는 모든 원소가 두 개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있다. 더 나은 성능을 얻고 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가시킬 수도 있다.
- 룩업의 경우, 특정 원소가 존재하는지를 알기 위해 저장 가능한 위치 두 군데만 확인해보면 된다. 룩업 연산의 시간 복잡도는 항상 O(1)이다.
- 삽입 함수는 먼저 첫 번째 해시 테이블에서 A를 삽입할 위치를 찾아 현재 비어 있는지를 검사 후에 비어있다면 그대로 삽입한다. 그러나 이미 B가 저장되어 있다면 해당 위치에 A를 저장하고 B를 두 번째 해시 테이블로 옮긴다. 이러한 작업을 완전히 비어 있는 셀이 나타날 때까지 재귀적으로 반복한다.
- 이러한 과정에서 만약 순환이 발생한다면 무한 루프에 빠질 수 있다.
- 순환이 발생했다면 새로운 해시 함수를 이용하여 재해싱을 수행해야 한다.
- 적절한 해시 함수를 사용하면 높은 확률로 O(1)의 성능을 갖는 해시 테이블을 구성할 수 있다. 열린 주소 지정 방법과 마찬가지로 뻐꾸기 해싱도 전체 해시 테이블 크기 이상의 원소를 저장할 수는 없다. 높은 성능을 보장하려면 부하율이 0.5보다 작게끔 설정해야 한다. 즉 전체 원소 개수가 해시 테이블 크기의 절반보다 작아야 한다.
3.5.5 연습 문제 15: 뻐꾸기 해싱
- 룩업 함수는 양쪽 해시 테이블에서 키를 검색하고, 해당 위치를 나타내는 반복자를 반환한다. 반복자가 항상 필요한 것은 아니지만, 여기서는 삭제 함수에서 이 반복자를 사용할 것이다. 만약 원소를 찾지 못하면 마지막을 가리키는 반복자가 반환된다. 해당 룩업 함수는 O(1)의 시간 복잡도를 가지며, 매우 빠르게 동작한다.
3.4 C++ 해시 테이블
- C++는 문자열로부터 해시 값을 생성하는 용도로 std::hash<std::string>(std::string) 함수 객체를 제공한다.
- 이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다. C++는 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다.
- 체이닝을 사용하는 해시 테이블에서 구현했던 해시 테이블 코드를 템플릿 형태로 바꾸면 모든 데이터 타입에 대해 사용할 수 있는 형태로 만들 수 있다. STL은 이러한 기능을 std::unordered_set<Key>와 std::unordered_map<Key, Value> 형태로 미리 구현하여 제공한다.
- unordered_set 은 키만 저장할 수 있고, unordered_map은 키와 값을 함께 저장할 수 있다.
- 두 컨테이너 모두 체이닝을 사용하는 해시 테이블 형태로 구현되어 있다. 해시 테이블의 각행은 키 또는 키와 값의 쌍을 저장하는 벡터이다. 여기서 각 행을 버킷이라고 부른다.
- 키로부터 해시 값을 구하면 이에 해당하는 버킷에 접근할 수 있다. 각 버킷은 하나의 리스트를 가진다.
- std::unordered_set과 std::unordered_map 컨테이너는 검색, 삽입, 삭제 등의 보편적인 기능을 제공한다. 모든 원소에 차례대로 접근할 수 있도록 반복자 기능도 제공하고, 벡터나 배열 같은 다른 컨테이너로부터 곧바로 std::unordered_set또는 std::unordered_map을 구성할 수 있는 생성자도 제공한다. std::unordered_map은 [] 연산자를 이용하여 주어진 키에 해당하는 값을 받을 수도 있다.
- 이들 컨테이너는 최대 1의 부하율을 가진다. 해시 테이블 크기보다 원소 개수가 많아지게 되면 곧바로 해시 테이블 크기를 키우고, 해시 함수를 변경하는 재해싱이 일어난다. 그 결과 부하율은 1보다 작아지게 된다.
- 사용자가 강제로 rehash() 함수를 호출하여 재해싱을 할 수도 있다.
- max_load_factor(float) 함수를 사용하여 기본값이 1로 되어 있는 부하율 최대 한계치를 변경할 수 있다. 부하율이 지정된 최대 한계치를 넘어가면 재해싱이 발생한다.
3.4.1 연습 문제 16: STL에서 제공하는 해시 테이블
- std::unordered_set과 std::unordered_map을 사용하여 데이터 삽입, 삭제, 검색 등의 작업을 수행해보자.
- std:: unordered_map 예제에서 키와 값의 쌍을 저장한 후, [] 연산자와 키를 이용하여 값을 받아올 수 있었다. 이 []연산자는 값에 대한 참조를 반환하므로 이를 이용하여 저장된 값을 변경할 수도 있다.
의 [] 연산자는 참조를 반환하며, 만약 해당 키가 없다면 해당 위치에 기본값을 추가하여 반환한다.
- bucket_count() 함수는 현재 버킷의 개수를 알 수 있다. 이 외에도 load_factor(), max_bucket_count() 등의 함수를 이용하여 컨테이너 내부에서 사용되는 설정 값을 알 수 있다. 또한 rehash() 함수를 이용하여 수동으로 재해싱을 수행할 수 있다.
- 이들 컨테이너는 체이닝 기법을 사용하여 구현되었으므로 키와 값의 쌍을 서로 다른 버킷에 저장한다. 그러므로 버킷에서 특정 키를 찾을 때 키가 같은지를 비교해야 한다. 그러므로 키 타입에 대해 등호 연산이 정의되어 있어야 한다. 또는 템플릿 매개변수로 비교자를 지정할 수 있다.
- std::unordered_set과 std::unordered_map은 중복된 키를 허용하지 않는다. 만약 중복된 값을 저장하고 싶다면 std::unordered_multiset과 std::unordered_ multimap을 사용해야 한다. 이 두 컨테이너의 삽입 함수는 주어진 키가 이미 존재하는지를 검사하지 않는다.
- 또한 이들 컨테이너는 특정 키에 해당하는 모든 값을 얻을 수 있는 기능도 지원한다.
- STL은 C++에서 지원하는 모든 기본 데이터 타입에 대한 해시 함수를 제공한다. 따라서 앞서 언급했던 컨테이너에서 사용자 정의 클래스 또는 구조체를 키 타입으로 사용하려면 std 네임스페이스 안에서 해시 함수를 구현해야 한다. 또는 컨테이너의 템플릿 매개변수로 해시 함수 객체를 지정할 수도 있다. 그러나 해시 함수를 직접 만드는 것은 그다지 좋은 생각이 아니다. 해시 함수를 어떻게 만드느냐가 성능에 큰 영향을 주기 때문이다.
- Boost 라이브러리에서 제공하는 hash_combine() 함수를 사용하여 원하는 해시 함수를 구성할 수 있다.
- 암호화 함수를 사용할 경우, 해시 값으로부터 원본 데이터를 알아내는 역해싱이 매우 어렵기 때문에 보안 시스템에서 사용되기도 한다.
3.4.2 실습 문제 6: 긴 URL을 짧은 URL로 매핑하기
+ 기타 문제
# 해시 테이블 개념
해시테이블이란? 키(Key)와 값(Value)을 저장하고 빠르게 검색할 수 있는 자료구조입니다.
std::unordered_map과 std::unordered_set을 사용해서 구현할 수 있습니다.
- 키(Key)를 해시 함수(Hash Function)를 사용해 해시값으로 변환한 후, 특정 버킷(Bucket)에 저장한다.
- 같은 해시값을 가지는 키가 여러 개 존재할 경우 충돌(Collision)이 발생할 수 있다.
- 충돌 해결 방식으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 존재한다.
# C++에서 해시 테이블
C++ 표준 라이브러리에서는 std::unordered_map과 std::unordered_set을 제공한다.
- std::unordered_map : 키와 값을 쌍으로 저장하는 해시 테이블이다.
같은 키가 들어오면 값을 덮어쓴다.
- std::unordered_set : 키만 저장하는 해시 테이블이다.
같은 키가 들어오면 그냥 무시한다.
# 해시 테이블 성능
- 평균 시간 복잡도: 삽입, 삭제, 검색 모두 O(1)
- 최악의 경우: 해시 충돌이 많으면 O(N)까지 갈 수도 있다.
# 해시 충돌 해결 방법
- 체이닝(Chaining) → 동일한 해시값을 가진 원소를 연결 리스트로 저장.
- 개방 주소법(Open Addressing) → 빈 공간을 찾아 원소를 저장.
# std::map과의 차이점
| 내부 구조 | 해시 테이블 | 레드-블랙 트리 |
| 정렬 여부 | X (순서 없음) | O (자동 정렬됨) |
| 평균 검색 속도 | O(1) | O(log N) |
| 최악의 검색 속도 | O(N) | O(log N) |
3.5 블룸 필터
- 블룸 필터(Bloom Filter)란?
블룸 필터는 공간 효율적인 확률적 데이터 구조로, 어떤 요소가 집합에 포함되지 않았는지는 확실히 판별할 수 있지만, 포함되었는지는 확률적으로 판별하는 구조입니다. 즉, "없다"는 정확하지만, "있다"는 오탐(false positive)이 발생할 수 있는 필터이다.
- 빠르고 메모리 효율적 : O(1)의 시간 복잡도로 작동하며, 일반적인 집합(set)보다 훨씬 적은 메모리를 사용함.
- 오탐(false positive) 가능 : 특정 데이터가 존재한다고 판별될 수 있지만, 실제로 존재하지 않을 수도 있음.
- 삭제 불가 : 원칙적으로 기존 블룸 필터에서는 개별 요소를 제거할 수 없음(Counting Bloom Filter를 사용하면 가능).
- 해시 함수 활용 : 여러 개의 해시 함수를 사용하여 데이터가 존재하는지를 판별.
- 블룸 필터는 해시 테이블에 비해 공간 효율이 매우 높은 방법이지만, 결정적 솔루션 대신 부정확한 결과를 얻을 수
있다.
- 블룸 필터는 거짓-부정이 없다는 것은 보장하지만, 거짓-긍정은 나올 수 있다.
즉 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있다. 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면 이 원소는 확실히 없다.
- 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용한다. 보통 두 개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 세 개 이상을 사용해야 한다.
- 블룸 필터는 실제 값을 저장하지는 않으며, 대신 특정 값이 있는지 없는지를 나타내는 부울 타입 배열을 사용한다.
- 원소를 삽입할 경우, 모든 해시 함수 값을 계산하고 부울 타입 배열에서 이 해시 값에 대응되는 위치의 비트 값을 1로 설정한다. 록업의 경우, 모든 해시 함수 값을 계산하고 이에 대응되는 위치의 비트 값을 1로 설정되어 있는지를 검사한다. 만약 검사한 모든 비트가 1이면 true를 반환한다. 1이 아닌 비트가 하나라도 있다면 false를 반환하고, 이는 해당 원소가 없음을 의미한다.
- 블룸 필터가 왜 결정적이지 않은 것일까요? 그 이유는 특정 비트가 다수의 원소에 의해 1로 설정될 수 있기 때문이다.
- 즉 특정 값 x와 연관된 모든 비트가 이전에 삽입된 다른 원소 값들에 의해 모두 1로 설정되어 있을 가능성이 있다는 뜻이다. 이러한 경우 x에 대한 룩업 함수는 true를 반환할 것이다. 이처럼 특정 원소가 있다고 잘못 판단하는 것을 거짓-긍정이라고 한다. 원소 개수가 많아질수록 거짓-긍정이 발생할 가능성이 증가한다.
- 그러나 x와 연관된 비트 중 하나라도 1로 설정되어 있지 않다면 x가 확실하게 없다고 말할 수 있다. 그러므로 거짓-부정은 발생할 수 없다.
- 부울 배열의 모든 원소가 true 또는 1로 설정될 경우, 이 배열은 포화 상태가 된다. 이 상태에서 룩업 함수는 항상 true를 반환하고, 삽입 함수는 블룸 필터 상태에 아무런 영향을 주지 못한다.
3.5.1 연습 문제17: 블룸 필터 만들기
- 거짓-긍정이 발견되지만, 거짓-부정은 나타나지 않는 것을 확인할 수 있다.
- 블룸 필터는 컨테이너에 실제 데이터를 저장하지 않기 때문에 다양한 타입의 데이터에 대해서도 사용할 수 있다. 해시 함수를 충분히 잘 만들었다면 하나의 블룸 필터에 정수, 문자열, 실수 등의 데이터를 섞어서 삽입할 수도 있다.
- 블룸 필터를 사용하기에 적합한 실제 상황을 꽤 많이 찾을 수 있다. 즉 데이터양이 너무 많아서 해시 테이블조차도 사용하기가 버겁고, 거짓-양성이 있어도 괜찮은 경우가 있다.
3.5.2 실습 문제7: 이메일
3.6 나가며
'Programming II > 자료구조 (STL)' 카테고리의 다른 글
| [코딩 테스트를 위한 자료 구조와 알고리즘 with C++] 5장 그리디 알고리즘 (0) | 2025.05.07 |
|---|---|
| [코딩 테스트를 위한 자료 구조와 알고리즘 with C++] 4장 분할 정복 (0) | 2025.05.07 |
| [코딩 테스트를 위한 자료 구조와 알고리즘 with C++] 2장 트리, 힙, 그래프 (0) | 2025.03.24 |
| [코딩 테스트를 위한 자료 구조와 알고리즘 with C++] 1장 리스트, 스택, 큐 (0) | 2025.01.23 |
| [자료구조] hashTable/ hashMap (0) | 2023.04.02 |