waca's field

# 해싱이란? 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다. 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있다면 $O(n)$이고 정렬이 되어 있다면 $O(log_2n)$이다. 정렬되어 있는 경우의 시간 복잡도가 $O(log_2n)$인 건 이진 탐색 알고리즘 혹은 이진 탐색 트리의 탐색 알고리즘의 시간복잡도를 생각하면 된다. 잘 모르겠다면 이진 탐색 또는 이진 탐색 트리 ..