728x90
해싱(Hashing)
키를 고정된 크기의 해시값으로 변환하여 데이터를 저장하는 방법
이중 해싱(Double Hashing)
개방 주소법의 일종, 첫 번째 해시 함수에서 충돌이 발생하면 두 번째 해시 함수를 사용하여 새로운 위치 찾음
문제 풀이
이론은 잘 모르겠다;;;
첫번째 해시 함수가 테이블의 인덱스를 결정, 그러므로 현재 점유된 인덱스는 0,2,3,5,9
h(19) = 2, f(19)=7
이제 h_i 함수를 통해서 위치 계산, 만약에 충돌 발생하면 i를 늘려가면서 재해시 시도 횟수를 늘려간다.
h_i(19) = (2 + i*7) mod 17
h_0 = 2 → 점유된 인덱스
h_1 = 9 → 점유된 인덱스
h_2 = 16 → 빈칸이므로 여기에 저장!
출처
- https://naeunbi698.tistory.com/530