자료구조-Hash

코딩연습을 하며 문제를 해결할때 알아야하는 자료구조나 알고리즘들이 있기에 여기에 정리를하며 공부할 예정이다.

해시 : 긴 데이터를 고정 길이의 데이터로 바꾼 값

해시테이블 : 키를 값에 매핑할 수 있는 자료구조로 Key, Value가 하나의 쌍을 이루며 데이터가 저장되고 검색되어지는 자료구조로 배열을 사용하여 구현 가능하다.

해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 간단하게 해시라고 한다.

충돌 : 해시함수로 서로 다른 key를 매핑했을때 동일한 해시값을 가지는 현상

충돌해결법으로는 개방주소법과 폐쇄주소법이 존재한다.

개방 주소법(open addressing) : 충돌이 발생하면 해당항목을 해시테이블 내의 다른 공간에 저장한다.

선형조사법 : 충돌이 발생한 해시테이블의 위치가 ht[a]일때 ht[a+1]이 비어있는지 확인한다. 비어있지않으면 ht[a+2]를 살펴보는 방식으로 비어있는 공간을 찾는 방법이다.
(h(t)+i) mod M (i=0,1,$\dots$,M-1)의 식으로 탐색위치를 나타낼 수 있으며 M은 해시테이블의 크기이고 h(t)는 해시값이다.

이차조사법 : (h(t)+i*i) mod M (i=0,1,$\dots$,M-1)의 식과 같은 식으로 탐색할 위치를 나타낼 수 있고 탐색할 위치는 h(t), h(t)+1, h(t)+4,$\dots$과 같은 방법으로 비어있는 공간을 찾는다.

이중 해싱법 : 저장할 다음위치를 기존의 해시함수와 다른 별개의 해시함수를 이용하는 방법이다
다른 해시함수가 h'(t)라고 할때 탐색위치는 h(t),h(t)+h'(t)+h(t)+2*h(t),$\dots$와 같은 방식으로 빈 공간을 찾는다

폐쇄 주소법(closed addressing) : 체이닝이라고도 하며 처음 계산한 주소를 이용하여 항목을 저장하는 방법으로 해시테이블의 리스트로 구현하여 해당 방법을 사용이 가능하다.

시뮬레이션

참고자료 : 위키백과, C언어로 쉽게 풀어쓴 자료구조