해싱

이진 트리 탐색에서는 리스트의 값이 순서대로 정렬되어 있다는 점을 활용하여 로가디즘시간(리스트의 크기가 커지면 탐색 시간이 리스트 크기의 로그값만큼 증가하는)에서 탐색이 이루어지도록 탐색 성능을 개선시킬 수 있음을 보았다. 이 장에서는 보다 나아가 고정시간이 걸리는 탐색을 살펴보고자 한다. 이 컨셉은 “해싱”이라는 기법으로 불린다.
이를 사용하기 위해서는 리스트에서 원소가 어디쯤에 위치할 것인지에 대해 좀 더 많은 것을 알아야 한다. 만약 모든 원소가 있어야 할 위치에 있다면 단 한 번의 비교 만으로도 아이템을 찾을 수 있다. 더 보기 »Hash Map 이란 무엇인가