chaining
-
Open Hashing - ChainingC 자료구조/Hash 2020. 11. 7. 22:26
참고 문헌 뇌를 자극하는 알고리즘, 쉽게 풀어쓴 자료구조 개념 구현할 방식은 Chaining방식이다. 해시 주소가 같은 탐색 키들을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것이다. 이러한 리스트는 그 크기를 예측할 수 없으므로, 연결 리스트로 구현하는 것이 가장 바람직하다. 각 버킷에 고정된 슬롯을 할당하는 것이 아니라, 각 버킷에 삽입과 삭제가 용이한 연결리스트를 할당한다. 당연히 버킷 내에서 원하는 항목을 찾을 때는 연결리스트를 순차 탐색한다. 예를 들어, 크기가 7인 해시 테이블에 h(k) = k mod 7 의 해시 함수를 이용하여 8,1,9,6,13을 삽입할 때에의 체이닝에 의한 충돌 처리를 보자. 1. h(8) = 8 mod 7 = 1 (저장) 2. h(1) = 1 mod 7..