시카로의 공부방

어떠한 값을 순차탐색하면 확실히 데이터를 얻을 수 있지만, 모든 데이터를 살펴봐야하는 경우가 있으므로 효율적이지 않다. 그러므로 해시는 어떠한 기준(함수)로 변환한 값을 인덱스로 삼아서, 그 인덱스에 해당하는 배열에 키와 값을 저장해 빠른 데이터 탐색을 제공하는 자료구조다. 여기서 탐색에 특화되었다는 게 중요하다. 리스트 자료구조의 경우, 보통 검색에 O(n), 추가에 O(1)이자만, 여기서는 반대이다. 물론 리스트도 중간 추가면 O(n)이긴 하다. 그러나 차이점을 아는 게 중요하다. 해시의 시간복잡도 삽입(Insert): 평균 O(1), 최악의 경우 O(n) 검색(Search): 평균 O(1), 최악의 경우 O(n) 삭제(Delete): 평균 O(1), 최악의 경우 O(n) 해시의 특징 해시는 키를 통..