공부/자료 구조 및 알고리즘
2019. 7. 15.
자료의 탐색 - 해싱(Hashing)
해싱(Hashing) 순차 탐색이나 이진 탐색의 비교 연산이 아닌 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾아가는 계산 탐색 방법. 해싱(Hashing) 탐색방법 ① 키값에 대해서 해싱 함수를 계산하여 주소를 구한다. ② 구한 주소에 해당하는 해시 테이블로 바로 이동한다. ③ 해당 주소에 찾는 키가 있으면 탐색을 성공한 것이며, 해당 주소에 찾는 키가 없으면, 찾는 원소가 없는 것으로 판단한다. 해싱(Hashing) 예제 문제: 10장으로 구성 수가 다음과 같다고 가정한다. 1)해싱 함수를 수 자체 해시값으로 정의한 경우 각 숫자가 저장된 위치는 다음과 같이 저장된다. 즉, 34의 경우는 34번째 공간에 저장되며 1은 첫 번째 공간에, 999는 999번째 공간에 저장되어 찾고자 하는 수가 3..