코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 블룸 필터 뻐꾸기 해싱과 마찬가지로 여러 개의 해시 함수를 사용한다. 실제 값을 저장하지 않으며 키가 있는지 없는지 여부만 알 수 있다. 삽입 시 모든 해시 함수의 값에 해당하는 비트를 1로 설정한다. 확인한 모든 비트의 값이 1이면 키가 존재한다는 뜻이고, 모두 0이면 존재하지 않는다는 뜻이다. 해시 테이블에 비해 공간 효율이 매우 높지만 결정적(Deterministic) 결과 대신 부정확한 결과를 얻을 수 있다. 거짓-부정(False negative)이 없는 것은 보장하지만 거짓-긍정(False Positive)은 나올 수 있다. ※ 거짓-부정: 있는데 없다고 하는 경우 ※ 거짓-긍정: 없는데 있다고 하는 경우 블룸 필터를 사용하는 경우 데이터..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 뻐꾸기 해싱 크기가 같은 2개 이상의 해시 테이블을 사용한다. 각 테이블을 다른 해시 함수를 갖는다. 모든 원소는 테이블 어디든 저장될 수 있고 그 중 하나에 존재한다. 원소는 다른 테이블로 이동할 수 있다. 뻐꾸기 해싱에서의 삽입 해시 테이블1에서 공간이 비어 있으면 삽입한다. 비어 있지 않으면 기존 원소를 해시 테이블2로 이동한 후 삽입한다. 기존 원소를 옮길 공간이 비어 있지 않으면 원래 있던 원소를 해시 테이블 1로 이동한 후 삽입한다. 빈 공간이 발견되어 이동이 멈출 때까지 2부터 반복한다. 여기서 루프가 발생할 수 있고 이때는 재해싱을 수행해야 한다. 뻐꾸기 해싱의 성능 검색, 삭제는 원소의 개수와 상관 없이 테이블의 개수만큼만 확인하면..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 열린 주소 지정(Open Addressing) 하나의 테이블에 하나의 원소만을 저장한다. 중복이 발생할 경우 다른 비어 있는 위치를 탐색한다. 이차함수 탐색(Quadratic Probing) 충돌이 발생할 경우 선형 탐색을 진행한다. 1^2, 2^2, 3^2, 4^2, ... 순으로 다음 셀로 이동하여 비어 있는 셀인지 확인한다. 이차함수 탐색을 사용한 해시 테이블의 성능 선형 탐색에 비해 군집화(Clustering)가 발생활 확률은 상대적으로 줄어든다. 체이닝을 통한 해결에서 삽입 시간이 O(1)인데 비해 충돌한 해시 값의 수만큼 선형 시간이 소요된다. #include #include #include using namespace std; usin..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 열린 주소 지정(Open Addressing) 하나의 테이블에 하나의 원소만을 저장한다. 중복이 발생할 경우 다른 비어 있는 위치를 탐색한다. 선형 탐색(Linear Probing) 충돌이 발생할 경우 선형 탐색을 진행한다. 한 칸씩 다음 셀로 이동하여 비어 있는 셀인지 확인한다. 선형 탐색을 사용한 해시 테이블의 성능 특정 해시 값이 너무 자주 발생하면 원소가 몇 개의 그룹 형태로 뭉치는 군집화(Clustering)가 발생할 수 있다. 해시 충돌이 자주 발생할수록 검색 속도가 급격하게 느려진다. #include #include using namespace std; using uint = unsigned int; class hash_map { //..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 체이닝(Chaining) 해시 테이블의 특정 키에 값을 저장하는 것이 아니라 값의 리스트를 저장한다. 충돌이 발생할 경우 리스트의 마지막에 원소를 추가한다. 체이닝을 사용한 해시 테이블의 성능 삽입은 O(1) 복잡도를 갖는다. 원소 개수에 비해 테이블의 크기가 작으면 리스트가 평균적으로 길어지므로 검색 속도가 저하된다. 원소 개수에 비해 테이블이 너무 크면 공간이 낭비된다. 체이닝으로 충돌을 해결한 해시 맵 #include #include #include #include using namespace std; using uint = unsigned int; class hash_map { // 값의 리스트를 벡터로 관리한다. vector data; p..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 해시 테이블은 해싱을 통해 빠르게 값을 검색할 수 있지만 해시 값이 겹치는 경우에 주의해야 한다. 부하율(Load factor) 전체 원소 개수 / 해시 테이블의 크기 부하율이 1이면 원소 개수가 테이블의 크기와 같다는 뜻이고 가장 이상적인 상태이다. 모든 연산이 O(1)에 가깝게 작동하고 공간 이용도 효율적이다. 부하율이 1보다 낮아질수록 원소가 하나도 저장되지 않은 리스트가 많다는 뜻이고 공간이 낭비된다. 부하율이 1보다 커질수록 리스트의 크기가 1보다 크다는 것이고 검색 성능이 저하된다. 해시 테이블의 성능을 결정짓는 요소 부하율이 유일한 지표는 아니다. 몇몇 해시 테이블은 부하율이 1에서 너무 멀어지면 해시 함수를 변경하여 1에 가깝게 만드..