해시 테이블❓

해시 테이블이란 '배열과 연결 리스트를 조합한 것' 이다.

쉬운 예로 위 그림처럼 각 사람의 이름이 해시 테이블에 저장되며, 해시함수는 '이름의 가장 첫 글자' 인 경우를 생각해보자.

이런 경우 알파벳 개수 (26개)에 해당하는 포인터가 필요하며, 각 포인터는 알파벳을 시작으로하는 연결 리스트를 가리키게된다.

해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값만 담기게된다.
따라서 최선의 경우 검색 시간은 O(1)이 된다.
하지만 그렇지 않은 경우, 최악의 상황에는 바구니 하나에 모든 값이 담겨서 O(n)이 될 수 있다.
일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하므로 거의 O(1)에 가깝다고 할 수 있다.