Today I Learned - HashTable

Hash Table(해시 테이블) 이란?

 

Hash function(해시함수)을 사용하여 키를 Hash(해시) 값으로 매핑하고,

이 해시값을 index 혹은 주소 삼아 데이터의 value를 key와 함께 저장소(bucket, slot)에 저장하는

자료구조가 해시테이블(hash table)이다.

 

 

키(key) : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다.

이 상태로 최종 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야 하기 때문에

해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.

 

해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다.

다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를

효율적으로 운영할 수 있도록 도와준다.

다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데,

해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

 

해시(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭 되어 저장된다.

 

값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.