7) 해시 테이블

해시 테이블이란

해시 테이블은 ‘연결 리스트의 배열’입니다. 연결 리스트가 담긴 노드가 여러 개 이어져 있는 것이 ‘연결 리스트의 배열’, 즉 ‘해시 테이블’이 됩니다.

해시테이블

사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우를 생각해 보겠습니다.

그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 됩니다.

만약 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담기게 될 것입니다.

따라서 검색 시간은 O(1)이 됩니다.

하지만 그렇지 않은 경우, 최악의 상황에는 단 하나의 바구니에 모든 값들이 담겨서 O(n)이 될 수도 있습니다.

일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다고 볼 수 있습니다.

해시 함수는 어떻게 만들 수 있을까요?

여러 방법이 있을 수 있다. 조금 다르지만 json으로 만들 수도 있겠고, 배열을 선언하는 방법도 있을 수 있다. 아니면 정공법으로 해시 테이블의 첫 노드를 모두 만들어 연결 리스트로 연결하는 방법을 사용할 수도 있을 것이다.

written by CaesiumY