해시

해시 테이블

특징

Key-Value 매핑 구조

해시 함수를 이용해서 키에 해당하는 값에 빠르게 접근 가능

해시 함수: 입력값을 고정된 길이의 출력값으로 변환 -> 주소값으로 사용

해시 알고리즘에 따라 성능이 달리진다.

 

시간복잡도

원소 접근, 삽입, 삭제: 평균 O(1) -> 최악의 경우 O(N)

 

*해시 충돌

서로 다른 키가 같은 해시값을 가질 수 있다.

충돌 문제에 대한 대응으로 체이닝 기법을 사용한다.

최악의 경우, 체이닝으로 연결된 데이터를 탐색하면서 시간복잡도가 O(N)이 될 수 있다.

체이닝을 선형구조가 아니라 레드 블랙 트리 등의 트리 구조로 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다.