해쉬 테이블 (Hash tables)

해쉬 테이블의 장점 ( 배열과 비교)

해쉬 테이블의 장점을 알기 위해 배열과 비교해보자.

피자의 가격을 검색한다고 하자. 배열에서는 일단 피자를 찾아야 한다. 그러므로 선형 검색을 통해 찾는다.

해쉬 테이블로 찾는다면 pizza를 찾고 바로 price를 찾을 수 있다. 그 어떤 음식의 가격을 찾는다 하더라도 1만큼의 시간이 걸린다. 참고로 해쉬 테이블은 key값, value값이 있다.

시간 복잡도는 배열은 O(n), 해쉬 테이블은 O(1)이다.

 

 

 

배열은 인덱스의 번호를 알아야 아이템에 접근할 수 있다.

해쉬 테이블은 내부에 배열같은 구조가 있음에도 시간복잡도가 O(1)인 이유는 무엇일까?

그 이유는 해쉬 함수가 있기 때문이다. 해쉬 함수는 key값을 숫자로 바꾸어 주는 역할을 한다.

그 숫자가 인덱스가 되고 해당 숫자값에 value가 저장된다.

예를 들면, 식당에 메뉴가 있다. pizza는 5글자로 5라는 인덱스에 값이 저장되고, cake는 4글자로 4라는 인덱스에 값이 저장된다.

 

충돌발생 가능! (collision)

 문제는 taco를 저장하면 taco도 인덱스 4에 값이 저장된다. 그럼 인덱스 4에 cake value와 taco value가 모두 있는 것이다.

만약 우리가 taco를 찾는다면 해쉬 함수는 taco를 4로 바꿀 것이고 우린 4로 가서 바로 taco를 찾을 수 없다.

taco를 찾기 위해서는 4로 가서 4에서 taco를 찾기위 '선형검색'을 해야하는 것이다.

그러므로 해쉬 테이블의 시간복잡도는 항상 상수인 것은 아니다.