HashTable이란?

Hash table 정의

 

hash table은 배열과 해시함수를 사용하여 map을 구현한 자료구조입니다. 

 

여기서 해시 함수란 무엇일까요? 해시 함수란 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로변환되는 함수를 뜻합니다

그림 1

다음과 같은 경우 'ABCED' 의 임의의 크기를 지닌 데이터를 해시 함수에 넣을 경우 정수 값인 350가 반환되는 것을알 수 있습니다. 이 떄 '350' 값을 hash라고 하고 이것이 HashTable에서의 함수가 됩니다.

 

---

Hash table의 동작 방식

 

그림 2

"ABCDE" 를 key로 "가나"를 value로 지니는 데이터를 HashTable에 넣는다고 가정해보겠습니다. 우선 key값을 해시 함수에 집어 넣어 특정 해시 값을 구합니다.  위와 같은 경우 350이 Hash값이 됩니다.

 

그리고 해당 해시값을 특정 값으로 나누어 나머지를 구하는데, 이 때 나누는 수를 Capacity라고 합니다.

Capacity는 데이터들이 저장되는 배열의 공간 크기를 뜻합니다. 위와 같은 경우 배열의 크기가 8이기 때문에

Capacity가 8이 됩니다. 또한 이러한 배열의 각 공간들을 버킷이라 부릅니다.

 

돌아와서, (ABCDE, 가나)를 오른쪽의 배열중에 한 공간에 저장해야 되기 때문에 해시값을 capacity로 나눈 6을인덱스로 가지는 공간에다 해당 데이터를 넣어주게 됩니다. 그리고 이렇게 해시값을 Capacity로 나누어 배열의 인덱스 값을 구하는 연산을 모듈러 연산이라 합니다.

 

---

Hash table의 문제점

 

해시 테이블의 대표적인 문제점 중에 하나가 해시 충돌입니다. 해시 충돌은 두가지가 있습니다.

 

1. key는 다른데 hash 값이 같을 때

2. key도 hash도 다른데, 모듈러 연산 후 나온 결과값이 같을 때

 

이러한 해시 충돌은 해시라는 자료구조가 가지는 특성상 불가피하게 발생하게 됩니다.

그림 3

 왜냐하면, 해시 자체가 임의의 크기를 지니는 데이터를 고정된 크기를 지니는 데이터로 줄이는 특성이 있기 때문입니다.

이러한 해시 충돌을 방지하기 위해 해시 함수를 조정하여 같은 해시값이 나오지 않게 하는 방법이 있습니다.

해당 해결방법은 위에서 제시한 해시 충돌 중 key 값이 다른데 hash값이 서로 같은 경우를 대비한 방법입니다.

 

또 다른 방법으로는 모듈려 연산 후 나온 결과값이 같을 때 할 수 있는 해결방법들이 있습니다. 크게 2가지로 나뉩니다.

 

1. Separate Chaining(분리 연결법)

그림 4

 

그림 2에서 (ABCDE, 가나) 데이터를 6번 인덱스를 가지는 버킷에다 저장했습니다.

그 후 key를 'CDEF',  value를 '다라' 를 지니는 데이터를 넣으려고 모듈러 연산 후 인덱스를 구했는데

이전과 같은 똑같은 6이라는 결과가 나왔습니다. 다시 말해 해시 충돌이 발생한 것입니다.

 

이 때 분리 연결법 방식에서는 똑같은 인덱스 6번을 가지는버킷에 해당 데이터를 넣는데,

이전에 넣었던 데이터와 리스트 형태로 연결하여 데이터를 넣게됩니다.

이러한 방식으로 해시 충돌을 다루는 방법이 분리 연결법 (Separate Chaining)이라고 합니다.

 

2. Open Addressing(개방 주소법)

그림 5

개방 주소법은 분리 연결법과 다르게 이미 해당 인덱스에 데이터가 존재하면 그 다음 비어있는 공간에 데이터를 넣는 방식을

뜻합니다. 이 떄 중요한 점은, 만약에 데이터를 삭제 할 경우에는 더미 노드를 삽입해줘야 한다는 것입니다.

 

만약 (ABCDE, 가나) 라는 데이터를 삭제한 후에 키를 CDEF로 가지는 VALUE 값을 찾게 된다면, 더미 노드가 없을 시, 6번 인덱스에는 아무런 데이터가 없기 때문에 아무런 값을 반환하지 않게 됩니다. 따라서 더미노드를 삽입하여 다음 버킷에 찾으려는 KEY에 해당하는 데이터가 있을 수 있음을 나타내줘야 합니다.

 

---

이상으로 hashtable의 정의와 특징 그리고 동작방식, 문제점에 대해 살펴보았습니다.

부족한 부분이나 수정 할 부분 있으면 댓글로 부탁드리겠습니다. 

 

긴글 일어주셔서 감사합니다.

 

 

---

참고 자료

 

https://www.youtube.com/watch?v=ZBu_slSH5Sk