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