[자료구조] 05. 해쉬 테이블(Hash Table)

해쉬 테이블

해쉬 테이블은 해시 값을 index로 삼아 key와 value를 저장하는 자료구조이다.

빠른 검색이 필요한 경우에 많이 사용되는 자료구조인데 내부적으로 배열을 사용하여 값을 저장하기 때문이다. 해쉬 테이블은 각 Key 값에 해쉬함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 이때 실제 값이 저장되는 장소를 버킷이라고 한다.

 

자바에서 제공하는 Hashtable 클래스를 살펴보면 해당 자료구조에 값을 저장할 때 아래의 그림처럼 동작한다.

key를 자바에서 제공하는 해쉬함수인 hashCode()를 이용하여 해쉬 값으로 변경하고 그 변경한 값을 인덱스 값으로 또 계산하는 것을 볼 수 있다.

---

시간복잡도

추가, 삭제 : O(1)

검색 : O(1)

 

하지만 해쉬 충돌이 일어날 경우 O(n)이 발생할 수 있음.