Hash Table
매핑 전 원래 데이터의 값을 키(key), 매핑후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)
연관배열 구조를 이용하여 키(key)에 결과 값(value)를 저장하는 자료 구조이다.
연관배열 구조(associative array)란? 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출가능
Hash Table의 구조
-
keys | hash function | buckets(value)
<이미지 참조 - 위키백과>
-
키(key) : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
-
해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
-
해시(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
-
값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.
Hash Table에 자료를 저장하는 것을 보여주는 이미지
예를 들어 input 값을 7로 나눈 나머지로 변경해서 출력했을때, key는 '76', hash는 '6'이다. 그러면 input 값은 준비해놓은 저장소 중에 6에 해당하는 hash값을 찾아 해당 value를 저장한다.
< 이미지 참조 : https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/ >
Hash Table 이슈
예외적으로 같은 hash값을 가지는 경우가 생길 수 있다. -> Hash collision이라고 한다.
해결방법
- Separate Chaining
예외 충돌을 막기위해 linkedlist를 이용 -> 같은 index안에 겹치는 data를 넣는다.
- Open Addressing
같은 index / 해시 버킷에 data가 이미 존재하면, 주변 비어있는 index / 해시버킷을 찾아서 data를 넣는다.
data를 저장/조회할 해시 버킷을 찾을 때에는 Linear Probing, Quadratic probing 등의 방법
< 이미지 참조 : https://d2.naver.com/helloworld/831311 >
일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문이다. 반면, Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 조정할 수 있다면 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다. <참조 : https://d2.naver.com/helloworld/831311 >
Hash Table Code
// 예시
TIL record