해쉬(Hash)

해쉬 테이블은 key-value system을 이용하여 자료를 정리하는 구조이다. 이 구조는 사전과 같은 의미라고 볼 수 있다.

만약 사전에서 단어를 찾는다면 해당 단어를 찾고 그 단어의 해석을 확인할 것이다. 이 때 해당 단어가 key이고, 단어의 해설이 value이다.

 

해쉬 테이블을 사용하는 이유는 무엇일까? 바로 효율성 때문이다. 아래는 배열과 해쉬에서 하나의 데이터를 찾는 과정이다.

---

배열

위에서 보이는 배열에서 원하는 메뉴를 찾는다고 가정하자. 만약 pizza의 가격을 찾는다면 위에서부터 선형 탐색(Linear Search)을 진행한다. 이렇게 선형 탐색을 하게되면 매우 시간이 오래 걸리게 된다.

 

배열의 선형 탐색(Linear Search)의 시간 복잡도

---

해쉬 테이블

 위 해쉬 테이블에서 같은 pizza의 가격을 찾는다면 간단하게 pizza를 호출하면 된다. 그렇기 때문에 배열의 선형 탐색보다 빠른 시간으로 탐색이 가능하다.

 

위 예시와 같이 배열은 선형 탐색을 해야하기 때문에 데이터가 많을수록 많은 시간을 사용하게 되는 것과 달리 해쉬 테이블에서의 탐색은 하나의 key를 검색하는 것으로 1번으로 탐색이 가능하다. 이러한 이유로 해쉬 테이블을 사용하는 것이 효율성에 좋다.

 

해쉬 테이블 시간 복잡도

---

 

> 해쉬 관련 문제 보기