좋은 해쉬 함수의 조건, 체이닝

좋은 해시 함수 = 충돌이 적은 해시 함수

 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여

해쉬 값 만들기

 여덟 자리의 수로 이뤄진 키에서 네 자리의 수를 뽑아서 해쉬 값 생

성하는 방법 예

 자릿수 선택 방법 : 키의 특정 bit들을 선택하여 해쉬 값으로 사용.

 자릿수 폴딩 방법 : 일정 bit로 전체 키를 나누어 모두 더한 값을 사용

​

체이닝

 열링 어드레싱 모델 : 충돌이 발생하면 다른 자리에 저장.

 닫힌 어드레싱 모델 : 무슨 일이 있어도 자신의 자리에 저장. 한 자

리에 여러 slot이 들어갈 수 있어야 함.

 여러 자리를 마련하는 방법 : 배열과 리스트

 리스트 선호 : 메모리 낭비 적으므로.