해쉬테이블

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

해쉬 테이블 해쉬 테이블은 해시 값을 index로 삼아 key와 value를 저장하는 자료구조이다. 빠른 검색이 필요한 경우에 많이 사용되는 자료구조인데 내부적으로 배열을 사용하여 값을 저장하기 때문이다. 해쉬 테이블은 각 Key 값에 해쉬함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 이때 실제 값이 저장되는 장소를 버킷이라고 한다. 자바에서 제공하는 Hashtable 클래스를 살펴보면 해당 자료구조에 값을 저장할 때 아래의 그림처럼 동작한다. key를 자바에서 제공하는 해쉬함수인 hashCode()를 이용하여 해쉬 값으로 변경하고 그 변경한 값을 인덱스 값으로 또 계산하는 것을 볼 수 있다. 시간복잡도 추가, 삭제 : O(1) 검색 : O(1) 하..