-
2021.05.28
[C++] 블룸 필터(Bloom Filter)
블룸 필터(Bloom Filter) 해시 테이블에 비해 공간 효율이 매우 높은 방법 결정적(Deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있음. 거짓-부정(Fals Negative) 이 없다는 것은 보장하지만, 거짓-긍정(False Positive) 은 나올 수 있음. 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있음. 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실히 없음. 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용함. 보통 2개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 3개 이상을 사용해야 함. 블룸 필터는 실제 값을 저장하지는 않음. 대신 특정 값이 있는지 없는지..
-
2021.05.22
[C++] 뻐꾸기 해싱(Cuckoo Hashing)
뻐꾸기 해싱(Cuckoo Hashing) 크기가 같은 2개의 해시 테이블을 사용함. 각각의 해시 테이블은 서로 다른 해시 함수 를 가짐. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있음. 위치는 해당 해시 테이블의 해시 함수 에 의해 결정됨. 뻐꾸기 해싱이 다른 해싱 기법과 다른 점 원소가 두 해시 테이블 중 어디든 저장될 수 있음. 원소가 나중에 다른 위치로 이동할 수 있음. 다른 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없음. 그러나, 뻐꾸기 해싱 방법에서는 모든 원소가 2개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있음. 더 나은 성능을 얻고, 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가 시킬 수도 있음. 룩업 연..
-
2017.06.20
[C] 해싱(Hashing)
해싱(Hashing) [해싱이란?] - 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근함. - 하지만 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근함. - 해시 테이블(hash table) : 키 값의 연산에 의해 직접 접근이 가능한 구조 - 해싱(hashing) : 해시 테이블을 이용한 탐색 - 해싱은 일상생활에서의 정리 정돈으로 비유할 수 있음. - 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있으면 O(n)이고 정렬되어 있으면 O(log₂n). - 이 정도의 시간 복잡도가 허용되는 경우도 있는 반면, 어떤 경우는 더 빠른 탐색 방법이 필요함. - 해싱은 이론적으로는 O(1)의 시간 안..
