해시 테이블

사전(Dictionary)의 구현: 해시 테이블(Hash Table)

해시 테이블(Hash Table)은 문자열을 인수로 받아서 정수를 반환하는 '해시 함수'를 사용해서 문자열과 값의 대응 관계를 표현하는 방법이다. 값을 넣기 위해서 우선 큰 배열을 준비한다. 그리고 해쉬 함수를 사용해서 문자열을 '적당한 정수'로 변환한 후 해당 배열 어디에 넣을지를 결정한다.

→ 실제로 해쉬 테이블을 구현할 때 몇 가지 문제가 있다.

• 다른 키를 해쉬 함수에 넣었는데 가끔 같은 번지의 값을 참조하는 경우, 이를 해시 충돌(Hash Collision)이라 하며, 해결 방법으로 Chaining, Open Addressing이 있다.
• 공간 효율성이 떨어진다. 데이터가 저장되기 전에 미리 저장 공간을 확보해 놓아야 하기 때문에 공간이 부족할 수도, 공간이 남을 수도 있다.
• 해시 함수 의존도가 높다. 해시 함수의 복잡도에 따라 해시 테이블의 연산 속도가 영향을 받는다.

⁉️ 왜 해시 테이블을 사용하는 것일까? 그냥 순서대로 입력하면 되지 않나?

• Key로 Value를 저장, 탐색, 삭제할 때 배열의 처음부터 순회하는 것이 아니라, 해시 함수를 통해 배열의 인덱스로 변환된 값을 이용하기 때문에 평균 시간 복잡도가 O(1)로 빠르다. 하지만 해시 충돌이 일어날 수 있고, 최악의 경우 O(N)의 시간 복잡도로 느려진다.

참고 자료 및 출처

• 책 <코딩을 지탱하는 기술> 9장 컨테이너와 문자열
• [자료구조] 해시테이블(HashTable)이란?
• Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해