[Hash란] - 자료구조

본 포스팅은 다음 자료들을 참고하였습니다

: 한동대학교 한다성 교수님 강의 자료

https://siyoon210.tistory.com/85

https://mangkyu.tistory.com/102

 

해시는 검색과 저장에 특화된 자료구조로

python의 경우 dictionary가 내재적으로 해시로 저장되어 있다...!

 

빠르게 저장할 수 있는 기저에는

데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)로 수렴하게 된다.

 

 

예를 들어보자

 

(yscho, "1022") 를 담고 있는, 즉, 'yscho'를 key로 '1022'를 value로 가지고 있는 자료 구조라고 했을 때, 

이 데이터를 크기가 16인 해시 테이블에 저장한다고 하면

저 정보를 담고 있는 위치를 0~15 중 어디에 위치시키게 되는 걸까?

이 역할을 해주는 것이 바로 'hash_function'이다.

 

예를 들어 위의 경우 16 크기이므로

index = hash_function(yscho)%16

가 되고 arr[index] = "1022"가 담기는 식으로 동작을 하게 된다. 

 

그렇다면 저 해시 함수는 대체 뭘까?

 

보통은 데이터에 따라 핵심적인 해시 함수를 만들거나 알고리즘을 구현하는 부분은 구현의 방법에 따라 상이하다.

 

 

대표적인 해시 함수로는 다음과 같은 것들이 있다.

 

출처 : https://mangkyu.tistory.com/102

 

예를 들어 조금 더 구체적으로 살펴보자

만약 Hash function이 다음과 같이 주어졌다 가정해보자

" hash_function(key) = key % 10 "

그러면 1,3,5,7,9의 각각의 숫자가 담기는 index는 다음과 같이 labeling 될 수 있다. 

 

출처 : 한다성 교수님 강의자료

여기까지는 별다른 문제가 없는 것 같다. 하지만 만약 다음과 같은 수를 labeling하게 되면 어떻게 될까?

출처 : 한다성 교수님 강의자료

이 경우 '15', '10', '30'은 모두 0의 index로 labeling이 되 충돌이 발생하게 된다!

이것을 'Hash collision'이라고 부른다. 

 

이러한 Hash collision을 피하기 위해 다양한 방법들이 연구되고 있지만

현재 통상적으로 많이 사용되는 대표적인 2가지 방법은 바로

 

1) Open-address Hasing

 

2) Chained Hasing

 

다음 2가지가 있다.

 

구체적으로 살펴보자

 

1) Open-Address Hashing이란

 

한다성 교수님 강의자료

강의 자료를 참고해보면, 

쉽게 말해 다음 자리 비는 곳으로 labeling하라는 매우 단순한 접근 방법이다. 

이 방법을 다른 말로 'linear probing'이라고 한다.

 

다음 그림을 봐보자

 

한다성 교수님 강의자료

위의 경우 15는 5로 labeling이 되었고 10의 경우는 0으로 labeling이 되었다.

그 다음 30을 labeling할 때 30의 경우 0에 labeling이 되어 hash collision이 발생하므로

그 다음 자리인 1로 labeling하는 것이다. 

 

한다성 교수님 강의자료

하지만 이런식으로 계속해서 데이터가 쌓이게 되면, 즉 key에 mapping이 되는 정도가 커지면 cluster가 구축이 되는데 cluster가 커지게 되면 역시 마찬가지의 문제가 발생하게 된다. 

 

이런 경우에 Double Hashing이라는 방법을 통해 충돌을 예방할 수 있다. 

즉, 또 다른 hash function을 적용시키는 방법을 의미한다.

 

2) Chained Hashing이란

 

key가 충돌될 경우 entry를 하나 더 구축해서 또 다른 해싱의 기능을 연결하여 value를 매핑하는 방식이다.

 

연결 방식은 pointer를 기반으로 내재적으로 구현되어 있다.

한다성 교수님 강의자료

최종적으로 

Hashing의 경우 시간 복잡도는 어떻게 될까?

 

평균 시간 복잡도는 O(1)

최악 시간 복잡도는 O(n)이 된다.