[기타] 해시테이블

해시 테이블은 자료구조 중 하나로서, [key,value]로 데이터를 저장하여 빠르게 데이터를 검색할 수 있습니다.

해시의 경우 내부적으로 버킷을 사용합니다.

key 하나에 value 하나가 대응 됩니다.

key 값이 있으면 그 값의 index를 생성하고, 이 index를 사용하여 값을 저장, 검색하는데 사용합니다.

여기서 실제 값이 저장되는 곳을 버킷이라고 합니다.

해시 테이블의 구조는 아래와 같습니다.

 

 

출처 : ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

해시 테이블 - 위키백과, 우리 모두의 백과사전

해시 함수에서 사용되는 용어들에 대해 정리해보겠습니다.

1. key

key는 고유한 값이며, 데이터를 저장하는 입력값이 됩니다.

2. 해시함수

key를 해시값으로 바꿔주는 역할을 합니다.

key를 같은 길이의 해시로 변경하여 저장을 합니다.

보통은 key마다 다른 해시 값을 가지는데 대량의 key를 가지게 되면 해시값이 같이질 수 있으며, 이를 해시 충돌이라고 합니다.

이런 해시 충돌을 방지하기 위한 해결책도 여러 가지로 존재합니다.

3. 해시

키를 해시 함수에 넣었을 때 나오는 결과 값입니다.

버킷에서 value와 매칭됩니다.

4. value

버킷에 최종적으로 저장되는 값입니다.

해쉬의 경우 시간복잡도는 O(1)이 됩니다.

알고리즘 성능으로 봤을 때, 매우 우수합니다.

그러나 이렇게 좋은 자료구조도 문제점은 존재합니다.

위에서 언급한 해시 충돌 현상입니다.

이것이 발생하는 이유는 key는 무한한값이 될 수 있지만, 해시 테이블의 value는 유한합니다.

위의 해시 테이블 구조에서 해시 테이블의 크기가 16이므로, 16개보다 더 많은 key값에 대해 value를 저장하기 위해서는 해시 테이블에 2개 이상의 값이 저장되어야 합니다.

해결 방법은 여러가지가 있습니다.

1. 체이닝

해시 충돌이 발생할 경우, 해시 테이블에 들어가는 데이터들을 연결하는 방식입니다.

연결리스트로 데이터를 연결하거나, Tree를 사용합니다.

2. 개방 주소법

해시 충돌이 발생하면, 다른 버킷에 데이터를 저장하는 방식입니다.

해시 충돌이 발생할 경우, 다음 버킷에 저장을 할 수도 있고, 제곱만큽 건너 뛰어서 버킷에 데이터를 저장하기도 합니다.

또한, 해시를 한번더 사용하여 데이터를 저장할 수도 있습니다.

이상입니다.