14.1 해싱이란?

지금까지 배운 선형 탐색이나 이진 탐색은 모두 키와 값을 반복적으로 비교함으로써 항목에 접근한다.

→ 이런 방법들은 최대 가능한 시간 복잡도가 O(log n)에 그치는데, 더 빠른 탐색 알고리즘이 필요하다.

해싱

• 키(key)에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.

해시 테이블

• 키에 대한 연산에 의해 직접 접근이 가능한 테이블 구조.
  • 이를 이용한 탐색이 해싱이다.

14. 2 추상 자료형 사전

사전의 개념

• 사전은 (키, 값)쌍의 집합으로, 키와 관련된 값을 동시에 저장하는 자료구조이다.
• 이로 인해 맵(map)이나 테이블(table)로 불리기도 한다.

키의 중요성