Hashing

'

용어 정의 

해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 균일하게 매핑할수록 좋은 해시함수이다.

해시 : 해시 함수에 얻어지는 값

해시 테이블 : 해시 값을 인덱스로 하여 데이터를 저장하고 있는 자료구조

 

Hashing

• 정의 : 데이터를 담을 해시 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시함수에 의해 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 과정
• 장점 : 데이터 접근 속도가 빠르다.
• 단점 : 충돌(collision)발생 - 서로 다른 입격 값에 대해 동일한 해시 테이블 주소를 반환하는 경우
• 해결법
  • chaining : 충돌되는 데이터들을 해당 주소에 링크드 리스트로 연결
  • open addressing : 충돌 발생시 해당 주소에 고정 폭 만큼을 더한 주소 값에 데이터 저장
    • linear probing : 고정 폭의 값을 1로 설정하여 선형적으로 빈 주소를 탐색
    • double hashing : 제 2의 해시함수의 값을 고정 폭의 값으로 설정하여 해시테이블 내의 클러스터를 방지