해싱 알고리즘

충돌(Collision) 두 개의 키가 동일한 버킷으로 해싱되는 경우 동의어(SYNONYMS) 같은 주소로 해싱되어 충돌을 일으킨 키 해싱의 탐색 시간은 O(1) 오버플로우(Overflow) 해시 충돌이 버킷(bucket)에 할당된 슬롯(Slot) 수보다 많이 발생해서 더이상 버킷에 값을 넣을 수 없는 현상 해싱 특징 검색 속도가 빠르며 삽입, 삭제의 빈도가 높음 해싱 기법에는 숫자분석법, 제산법, 제곱법, 접지법이 있다. 오버플로가 발생했을 때 해결기법으로 개방주소법(open addressing) 과 폐쇄주소법(close addressing)이 있다. 해싱 장점 레코드를 찾기 위해 키 값을 모두 비교할 필요 없다. 순차파일에서 데이터 탐색 시간 O(n) 키 값을 직접 주소로 사용하는 경우보다 기억장소 ..