0. 들어가며
- 룩업(조회) : 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업
- 해당 작업을 훨씬 빠르게 수행할 수 있는 해시 테이블과 블룸 필터 구현
1. 해시 테이블
- 선형 검색 O(N) / BST 검색 O(log N)
- 해시 테이블의 핵심은 해싱
1) 해싱
- 각각의 데이터를 가급적 고유한 숫자 값으로 표현, 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 원본 데이터를 추출하는 작업
- 가장 간단한 해시 함수는 나머지를 반환하는 모듈러함수(%)를 사용
- x를 입력 → (x%n) 연산 결과 반환 (해시 값 반환) → (x%n)위치에 x 값 삽입
- 모듈러 함수의 문제점은 서로 다른 데이터에 대해 같은 해시 값 반환 가능 (충돌 가능)
- 충돌 : 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환하여 다수의 키가 같은 해시 값을 갖게 된는 현상
2) 연습 문제 13: 정수 값을 저장하는 간단한 사전
#include<iostream>
#include<vector>
using uint=unsigned int;
class hash_map
{
std::vector<int> data;
public:
hash_map(size_t n)
{
data = std::vector<int>(n,-1);
}
void insert(uint value)
{
int n = data.size();
data[value%n] = value;
std::cout<<value<<"을 삽입했습니다."<<std::endl;
}
bool find(uint value)
{
int n = data.size();
return (data[value%n] == value);
}
void erase(uint value)
{
int n = data.size();
if(data[value%n]==value)
{
data[value%n]=-1;
std::cout<<value<<"을 삭제했습니다."<<std::endl;
}
}
};
int main()
{
hash_map map(7);
auto print = [&](int value){
if(map.find(value))
std::cout<<"해시 맵에서 "<<value<<"을 찾았습니다."<<std::endl;
else
std::cout<<"해시 맵에서 "<<value<<"을 찾지 못했습니다."<<std::endl;
std::cout<<std::endl;
};
map.insert(2);
map.insert(25);
map.insert(10);
print(25);
map.insert(100);
print(100);
print(2); // 2를 찾지 못함 -> 100에 의해 덮어 쓰워짐
map.erase(25);
}
2. 해시 테이블에서 충돌
1) 체이닝
- 해시테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라 하나의 연결 리스트를 저장
- 충돌 발생 시 리스트의 맨 뒤에 새로운 키를 추가
2) 연습 문제 14: 체이닝을 사용하는 해시 테이블
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using uint=unsigned int;
class hash_map
{
std::vector<std::list<int>> data;
public:
hash_map(size_t n)
{
data.resize(n);
}
void insert(uint value)
{
int n = data.size();
data[value%n].push_back(value);
std::cout<<value<<"을 삽입했습니다."<<std::endl;
}
bool find(uint value)
{
int n = data.size();
auto& entries = data[value%n];
return std::find(entries.begin(),entries.end(),value) != entries.end();
}
void erase(uint value)
{
int n = data.size();
auto& entries = data[value%n];
auto iter = std::find(entries.begin(),entries.end(),value);
if(iter != entries.end())
{
entries.erase(iter);
std::cout<<value<<"을 삭제했습니다."<<std::endl;
}
}
};
int main()
{
hash_map map(7);
auto print = [&](int value){
if(map.find(value))
std::cout<<"해시 맵에서 "<<value<<"을 찾았습니다."<<std::endl;
else
std::cout<<"해시 맵에서 "<<value<<"을 찾지 못했습니다."<<std::endl;
std::cout<<std::endl;
};
map.insert(2);
map.insert(25);
map.insert(10);
map.insert(100);
map.insert(55);
print(100);
print(2);
map.erase(2);
}
- 모든 키가 같은 해시 값을 가질 경우 룩업 연산 O(N)
- 부하율 = 전체 키 개수 / 해시 테이블의 크기
- 테이블 크기를 적절히 조절하여 사용
3) 열린 주소 지정
- 체이닝과 다르게 모든 원소를 해시 테이블 내부에 저장
- 특정 해시 값에 해당하는 위치가 이미 사용하고 있을 경우 테이블의 다른 비어있는 위치 탐색
(1) 선형 탐색
- 충돌이 발생하면 해당 위치에서 하나씩 다음 셀로 이동하며 비어있는 지 확인
- 특정 위치에 클러스터링(군집화)의 문제가 발생
(2) 이차 함수 탐색
- 선형 방정식이 아닌 이차 방정식을 사용하여 탐색 수행
- 이미 사용 중인 경우 hash(x+1^2) → hash(x+2^2) → hash(x+3^2)와 같이 수행
- 군집이 나타날 경우는 상대적으로 줄어듬
4) 뻐꾸기 해싱
- 해싱 기법과 다름 점
- 원소가 두 해시 테이블 중 어디든 저장 가능
- 원소가 나중에 다른 위치로 이동가능
- 룩업(조회)의 연산은 항상 O(1)
- 원소 삽입의 경우 충돌이 발생하면 원래 있던 원소가 다른 해시 테이블로 이동
- 뻐꾸기 해싱에서 순환이 발생가능
- 새로운 함수를 이용하여 재해싱
- 여러 번 재해싱도 가능
5) 연습 문제 15: 뻐꾸기 해싱
#include<iostream>
#include<vector>
class hash_map
{
std::vector<int> data1;
std::vector<int> data2;
int size;
int hash1(int key) const
{
return key%size;
}
int hash2(int key) const
{
return (key%size)%size;
}
public:
hash_map(int n) : size(n)
{
data1 = std::vector<int>(size,-1);
data2 = std::vector<int>(size,-1);
}
std::vector<int>::iterator lookup(int key)
{
auto hash_value1 = hash1(key);
if(data1[hash_value1]==key)
{
std::cout<<"1번 테이블에서 " << key <<"를 찾았습니다"<<std::endl;
return data1.begin() + hash_value1;
}
auto hash_value2 = hash2(key);
if(data2[hash_value2]==key)
{
std::cout<<"2번 테이블에서 " << key <<"를 찾았습니다"<<std::endl;
return data2.begin() + hash_value2;
}
return data2.end();
}
void erase(int key)
{
auto position = lookup(key);
if(position != data2.end())
{
*position = -1;
std::cout<<key<<"에 해당하는 원소를 삭제했습니다."<<std::endl;
}
else
std::cout<<key<<"키를 찾지 못했습니다."<<std::endl;
}
void insert(int key){
insert_impl(key,0,1);
}
void insert_impl(int key, int cnt, int table)
{
if(cnt>=size)
{
std::cout<<key<<" 삽입 시 순환 발생! 재해싱이 필요합니다!" <<std::endl;
return;
}
if(table == 1)
{
int hash = hash1(key);
if(data1[hash] == -1)
{
std::cout<<table<<" 번 테이블에 "<<key<<" 삽입"<< std::endl;
data1[hash]=key;
}
else
{
int old = data1[hash];
data1[hash]=key;
std::cout<<table<<"번 테이블에 "<<key<<" 삽입: 기존의 "<<old<<" 이동-> ";
insert_impl(old,cnt+1,2);
}
}
else
{
int hash = hash2(key);
if(data2[hash] == -1)
{
std::cout<<table<<" 번 테이블에 "<<key<<" 삽입"<< std::endl;
data2[hash]=key;
}
else
{
int old = data2[hash];
data2[hash]=key;
std::cout<<table<<"번 테이블에 "<<key<<" 삽입: 기존의 "<<old<<" 이동-> ";
insert_impl(old,cnt+1,1);
}
}
]
void print()
{
std::cout<<"INDEX : ";
for(int i =0;i<size;i++)
std::cout<<i<<'\\t';
std::cout<<std::endl;
std::cout<<"DATA1 : ";
for(auto i : data1)
std::cout<<i<<'\\t';
std::cout<<std::endl;
std::cout<<"DATA2 : ";
for(auto i:data2)
std::cout<<i<<'\\t';
std::cout<<std::endl;
}
};
int main()
{
hash_map map(7);
map.print();
std::cout<<std::endl;
map.insert(10);
map.insert(20);
map.insert(30);
std::cout<<std::endl;
map.insert(104);
map.insert(2);
map.insert(70);
map.insert(9);
map.insert(90);
map.insert(7);
std::cout<<std::endl;
map.print();
std::cout<<std::endl;
map.insert(14); // 순환 발생!
}
3. C++ 해시 테이블
1) 연습 문제 16: STL에서 제공하는 해시 테이블
#include <iostream>
#include <unordered_map>
#include <unordered_set>
void print(const std::unordered_set<int>& container)
{
for (const auto& element : container)
std::cout << element << " ";
std::cout << std::endl;
}
void print(const std::unordered_map<int, int>& container)
{
for (const auto& element : container)
std::cout << element.first << " -> " << element.second << ", ";
std::cout << std::endl;
}
void find(const std::unordered_set<int>& container, const int element)
{
if (container.find(element) == container.end())
std::cout << element << " 검색: 실패" << std::endl;
else
std::cout << element << " 검색: 성공" << std::endl;
}
void find(const std::unordered_map<int, int>& container, const int element)
{
auto it = container.find(element);
if (it == container.end())
std::cout << element << " 검색: 실패" << std::endl;
else
std::cout << element << " 검색: 성공, 값 = " << it->second << std::endl;
}
int main()
{
std::cout << "*** std::unordered_set 예제 ***" << std::endl;
std::unordered_set<int> set1 = {1, 2, 3, 4, 5};
std::cout << "set1 초깃값: "; print(set1);
set1.insert(2);
std::cout << "2 삽입: "; print(set1);
set1.insert(10);
set1.insert(300);
std::cout << "10, 300 삽입: "; print(set1);
find(set1, 4);
find(set1, 100);
set1.erase(2);
std::cout << "2 삭제:"; print(set1);
find(set1, 2);
std::cout << "*** std::unordered_map 예제 ***" << std::endl;
std::unordered_map<int, int> squareMap;
squareMap.insert({2, 4});
squareMap[3] = 9;
std::cout << "2, 3의 제곱 삽입: "; print(squareMap);
squareMap[20] = 400;
squareMap[30] = 900;
std::cout << "20, 30의 제곱 삽입: "; print(squareMap);
find(squareMap, 10);
find(squareMap, 20);
std::cout << "squareMap[3] = " << squareMap[3] << std::endl;
std::cout << "squareMap[100] = " << squareMap[100] << std::endl;
print(squareMap);
}
2) 실습 문제 6: 긴 url을 짧은 url로 매핑하기
#include
#include
#include
struct URLService
{
using ActualURL = std::string;
using TinyURL = std::string;
private:
std::unordered_map<tinyurl, actualurl=""> data;
public:
std::pair<bool, actualurl=""> lookup(const TinyURL& url) const
{
auto it = data.find(url);
if (it == data.end()) // 단축 URL이 등록되어 있지 않은 경우
{
return std::make_pair(false, std::string());
}
else
{
return std::make_pair(true, it->second);
}
}
bool registerURL(const ActualURL& actualURL, const TinyURL& tinyURL)
{
auto found = lookup(tinyURL).first;
if (found)
{
return false;
}
data[tinyURL] = actualURL;
return true;
}
bool deregisterURL(const TinyURL& tinyURL)
{
auto found = lookup(tinyURL).first;
if (found)
{
data.erase(tinyURL);
return true;
}
return false;
}
void printURLs() const
{
for (const auto& entry : data)
{
std::cout << entry.first << " -> " << entry.second << std::endl;
}
std::cout << std::endl;
}
};
int main()
{
URLService service;
if (service.registerURL("<https://www.gilbut.co.kr/book/view?bookcode=BN002245>", "https://py_dojang"))
{
std::cout << "https://py_dojang 등록" << std::endl;
}
else
{
std::cout << "https://py_dojang 등록 실패" << std::endl;
}
if (service.registerURL("<https://www.gilbut.co.kr/book/view?bookcode=BN001484>", "https://c_dojang"))
{
std::cout << "https://c_dojang 등록" << std::endl;
}
else
{
std::cout << "https://c_dojang 등록 실패" << std::endl;
}
if (service.registerURL("<https://www.gilbut.co.kr/book/view?bookcode=BN002402>", ""))
{
std::cout << " 등록" << std::endl;
}
else
{
std::cout << " 등록 실패" << std::endl;
}
auto pythonBook = service.lookup("https://py_dojang");
if (pythonBook.first)
{
std::cout << "https://py_dojang 원본 URL: " << pythonBook.second << std::endl;
}
else
{
std::cout << "https://py_dojang 원본 URL을 찾을 수 없습니다." << std::endl;
}
auto cppBook = service.lookup("https://cpp_dojang");
if (cppBook.first)
{
std::cout << "https://cpp_dojang 원본 URL: " << cppBook.second << std::endl;
}
else
{
std::cout << "https://cpp_dojang 원본 URL을 찾을 수 없습니다." << std::endl;
}
if (service.deregisterURL("https://c_dojang"))
{
std::cout << "c_dojang 책 URL 등록 해제" << std::endl;
}
else
{
std::cout << "c_dojang 책 URL 등록 해제 실패" << std::endl;
}
auto findQtBook = service.lookup("https://c_dojang");
if (findQtBook.first)
{
std::cout << "https://c_dojang 원본 URL: " << findQtBook.second << std::endl;
}
else
{
std::cout << "https://c_dojang 원본 URL을 찾을 수 없습니다." << std::endl;
}
std::cout << "등록된 URL 리스트:" << std::endl;
service.printURLs();
}
</bool,></tinyurl,>4. 블룸 필터
- 블룸 필터는 해시 테이블보다 공간 효율이 매우 높음 하지만 결정적인 솔루션 대신 부정확한 결과를 얻을 수 있음
- 여러 개의 해시 함수를 이용하여 정확도를 높임
- 특정 비트가 다수의 원소에 의해 1로 설정될 수 있어 결정적이지 않음 (거짓-긍정 발생 가능)
- 따라 거짓의 경우에는 해당 원소가 확실히 없음 (거짓-부정 발생 불가능)
1) 연습 문제 17: 블룸 필터 만들기
#include<iostream>
#include<vector>
class bloom_filter
{
std::vector<bool> data;
int nBits;
int hash(int num, int key)
{
switch(num)
{
case 0: return key%nBits;
case 1: return (key/7)%nBits;
case 2: return (key/11)%nBits;
}
return 0;
}
public:
bloom_filter(int n) : nBits(n)
{
data = std::vector<bool>(nBits, false);
}
void lookup(int key)
{
bool result = data[hash(0,,key)]&data[hash(1,key)]&data[hash(2,key)];
if(result)
{
std::cout<<key<<": 있을 수 있음" <<std::endl;
}
else
std::cout<<key<<": 절대 없음"<<std::endl;
}
void insert(int key)
{
data[hash(0,key)] = true;
data[hash(1,key)] = true;
data[hash(2,key)] = true;
std::cout<<key<<"를 삽입: ";
for(auto a:data)
std::cout<<a<<" ";
std::cout<<std::endl;
}
};
int main()
{
bloom_filter bf(7);
bf.insert(100);
bf.insert(54);
bf.insert(82);
bf.lookup(5);
bf.lookup(50);
bf.lookup(20);
bf.lookup(54);
}
2) 실습 문제 7: 이메일 주소 중복 검사
#include <iostream>
#include <vector>
#include <openssl/md5.h>
class BloomFilter
{
int nHashes;
std::vector<bool> bits;
static constexpr int hashSize = 128 / 8; // 128비트(16바이트)
unsigned char hashValue[hashSize];
public:
BloomFilter(int size, int hashes) : bits(size), nHashes(hashes)
{
if (nHashes > hashSize)
{
throw("해시 함수 개수가 너무 많습니다.");
}
if (size > 255)
{
throw("블룸 필터 크기가 255보다 클 수 없습니다.");
}
}
void hash(const std::string& key)
{
MD5(reinterpret_cast<const unsigned char*>(key.data()), key.length(), hashValue);
}
void add(const std::string& key)
{
hash(key);
for (auto it = &hashValue[0]; it < &hashValue[nHashes]; it++)
{
bits[*it % bits.size()] = true;
}
std::cout << "블룸 필터에 추가: " << key << std::endl;
}
bool mayContain(const std::string& key)
{
hash(key);
for (auto it = &hashValue[0]; it < &hashValue[nHashes]; it++)
{
if (!bits[*it % bits.size()])
{
std::cout << key << " : 사용할 수 있는 이메일입니다." << std::endl;
return false;
}
}
std::cout << key << " : 이미 사용 중입니다." << std::endl;
return true;
}
};
int main()
{
BloomFilter bloom(128, 5);
bloom.add("abc@gilbut.com");
bloom.add("xyz@gilbut.com");
bloom.mayContain("abc");
bloom.mayContain("xyz@gilbut.com");
bloom.mayContain("xyz");
bloom.add("abcd@gilbut.com");
bloom.add("ab@gilbut.com");
bloom.mayContain("abcd");
bloom.mayContain("ab@gilbut.com");
}
출처 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++
'Computer Science > Data Structure & Algorithm' 카테고리의 다른 글
| 그리디 알고리즘 (0) | 2023.07.02 |
|---|---|
| 분할 정복 (0) | 2023.07.01 |
| 트리/힙/그래프(2) - 힙&그래프 (0) | 2023.06.28 |
| 트리/힙/그래프(1) - 트리 (0) | 2023.06.27 |
| 리스트 / 스택 /큐 (0) | 2023.06.26 |