🗒️ Hash Table (4)

1. 2021.05.28 [C++] 블룸 필터(Bloom Filter)

   블룸 필터(Bloom Filter) 해시 테이블에 비해 공간 효율이 매우 높은 방법 결정적(Deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있음. 거짓-부정(Fals Negative) 이 없다는 것은 보장하지만, 거짓-긍정(False Positive) 은 나올 수 있음. 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있음. 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실히 없음. 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용함. 보통 2개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 3개 이상을 사용해야 함. 블룸 필터는 실제 값을 저장하지는 않음. 대신 특정 값이 있는지 없는지..
2. 2021.05.28 [C++] STL로 해시 테이블(Hash Table) 만들기 (std::unordered_map, std::unordered_set)

   STL로 해시 테이블(Hash Table) 만들기 서론 C++의 STL을 이용하여 해시 테이블(Hash Table)을 구현할 수 있다. std::unordered_map과 std::unordered_set을 이용한다. 이 방법으로 해시 테이블을 구현할 경우 원소의 순서가 보장되지 않으며, 원소의 순서를 보장하도록 만들기 위해서는 std::unordered_multimap 또는 std::unordered_multiset을 이용하여 구현하면 된다. 코드 #include #include #include void print(const std::unordered_set& container) { for (const auto& element : container) { std::cout
3. 2021.05.22 [C++] 뻐꾸기 해싱(Cuckoo Hashing)

   뻐꾸기 해싱(Cuckoo Hashing) 크기가 같은 2개의 해시 테이블을 사용함. 각각의 해시 테이블은 서로 다른 해시 함수 를 가짐. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있음. 위치는 해당 해시 테이블의 해시 함수 에 의해 결정됨. 뻐꾸기 해싱이 다른 해싱 기법과 다른 점 원소가 두 해시 테이블 중 어디든 저장될 수 있음. 원소가 나중에 다른 위치로 이동할 수 있음. 다른 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없음. 그러나, 뻐꾸기 해싱 방법에서는 모든 원소가 2개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있음. 더 나은 성능을 얻고, 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가 시킬 수도 있음. 룩업 연..
4. 2021.05.20 [C++] 체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현

   체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현 체이닝(Chaining) 해시 테이블에 두 값을 모두 저장할 수 있는 여러 방법 중 하나 해시 테이블의 특정 위치에서 하나의 키 를 저장하는 것이 아니라 하나의 연결 리스트 를 저장함. 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가함. 따라서 다수의 원소를 원하는 만큼 저장할 수 있음. 벡터 대신 연결 리스트를 사용하는 이유? 특정 위치의 원소를 빠르게 삭제하기 위함. 코드 #include #include #include #include using uint = unsigned int; class hash_map { std::vector data; public: hash_map(size_t n) { dat..