[알고리즘] Hash 해쉬

알고리즘이라기보다 검색하면 자료구조라고 더 많이 나온다.

 

 

Key -> Hash Function -> Hash -> Value -> Bucket(Slot) 으로 진행된다.

Key: 입력 값. 무한할 수 있다.

Hash Function: Key로 부터 Hash값을 반환하는 함수. 사용자 임의로 설정

Hash : 해쉬값을 통해서 value값과 매칭시켜 Bucket(Slot)에 저장한다. (유한)

Value: 저장 값

Bucket(Slot): Value 저장소. vector / map / list / queue등을 이용한다.

 

hash_map이라는 라이브러리가 있지만 표준은 아니기 때문에

C++ STL(자료구조) 공부할 때 목차에 없다.

 

 

예를 들면, Hash Function이 key%10 이라면 hash로 나올 수 있는 값은 0~10이다.

Key로 받는 값이 10보다 많은 경우 저장공간에 충돌이 일어날 수 있다. (Hash collision)

이런 경우 chaining으로 저장되어 있던 값에 충돌 되는 값을 이어서 붙여 줄 수 있고 (node->link .. 이에 저장소가 더 필요하다.)

충돌시 또 다른 연산을 적용하여 해결 할 수 있다. 예를 들면 이미 저장되어 해시충돌이 일어나는 경우 빈 공간을 찾는 연산을 해줄 수 있고,

아니면 조건식으로 저장되어있는 값과 저장할 값을 비교하여 하나만 고를 수도 있다.

 

해쉬 테이블은 순서가 정해져 있는 데이터들에는 적용하기 힘들고,

Bucket(Slot)의 크기를 정하고 시작하며 hash function의 의존도가 높다.