'해시'에 해당되는 글 1건

최근 알고리즘 공부가 필요할 것 같아서 고민하다

프로그래머스 라는 코딩 테스트 사이트에 도전하기로 마음먹게 되었다

프로그래머스에는 코딩테스트 고득점 Kit라는 섹션이 있는데

여기 있는 Kit의 유형들을 하나씩 공부할 예정

(참고로 유형에 있는 문제 해답은 공유 안할거임)

그래서 오늘 주제는 '해싱'이다

해싱은 키 값을 가지고 자료를 저장하는 방식을 말한다

보통 자료를 저장하는 곳은 배열로 되어있고 해시 테이블이라고 불리고

키 값을 이용해서 배열의 주소를 구하는 방식으로 되어있다

이때 키 값을 주소로 바꾸기 위해 해시 함수를 사용한다

해시 함수를 사용하면 자료가 있는 곳까지 바로 안내하기 때문에

이상적으로는 시간 복잡도가  O(1) 이 된다.

대강 그림을 그리자면 다음과 같다

> 해시 함수

해시 함수는 키 값을 해시 테이블의 주소로 변환하는 역할을 한다

해시 함수를 만들때 가장 중요하게 봐야할 것중 하나는 충돌 이다

해시 테이블의 크기는 한정되어있기 때문에 한 주소에 여러개의 키가 들어갈 수 있는데

이것을 충돌이라고 한다

충돌이 많이 일어나면 자료를 다른 곳에 저장해야하고

그 다른 곳을 찾는 연산을 추가로 해야하기 때문에 탐색 속도가 느려지게 된다

따라서 좋은 해시 함수는 

1. 충돌이 적어야하며

2. 해시 함수 값이 해시 테이블의 주소 영역 내에 골구로 분포되어야하고

3. 계산이 빠를 수록 좋다

>해시 테이블

지금까지 나온 해시 함수중 충돌이 없는 함수가 없다고 한다

따라서 테이블도 충돌에 대비한 설계가 필요한데

2가지 정도의 해결책이 있겠다

1. 조사 (probing)

조사법은 특정 버킷(테이블의 구성요소를 버킷이라고 부른다)에서 충돌이 일어나면

해시 테이블에서 비어있는 다른 버켓을 찾는 방법이다

>선형 조사법 (linear probing)

만약 해시 테이블의 [n]번 버킷에서 충돌이 일어나면 [n+1]번 버킷이 비어있는지 확인하고

만약 거기도 차있으면 [n+2]를 살펴보는 식으로 차례차례 빈 공간을 찾는 것을 선형 조사법이라고 한다

>이차(제곱) 조사법 (quadratic probing)

선형조사법이 차례대로 조사하는 것이라면 이번에는 제곱수만큼 움직이는 것이다

만약 [n]번 버킷에서 충돌이 일어나면 [n+1²] 번으로 그 다음은 [n+2²], [n+3²], [n+4²] ...

이런식으로 찾아가는 것이다

>이중 해싱 (재해싱)  (double hashing)

이중 해싱은 해시 함수를 2개 만들어두고

만약 충돌이 일어나면 2번째 해시함수로 다시 해싱을 하는 방식이다

2. 체이닝 (chaining)

위와 같은 경우에는 버킷 하나당 고정된 양의 자료만 저장할 수 있어서

버킷이 꽉 차면 모든 테이블을 돌아다니며 자리를 찾아야 했고

해시 주소가 다른 탐색키와도 비교를 해야하기 때문에 시간이 많이 걸릴 수 있었다

만약 버킷에 슬롯을 만들어서 한번에 같은 해시 주소를 가진 여러개의 자료를 저장할 수 있게 한다면 어떨까?

체이닝은 연결리스트를 사용해 슬롯을 만든다

연결리스트를 사용하기 때문에

충돌이 일어나도 오버플로(버킷이 꽉 차는 경우)가 발생할일이 없고

삽입과 삭제가 수월해진다

하지만 실제로 프로젝트를 진행하면서 (심지어 프로그래머스 코딩테스트에서도)

별 특이한 경우가 아니고서야 실제로 사전 구조를 처음부터 만드는 일은 없을 것이다

그래서

C++에서는

<map>의 map

을 사용하고

C#에서는
System.Collections.Generic 의 Dictionary

를 사용할 수 있겠다

근데 프로그래머스 고득점 Kit 해시 문제 중에 절반은 해시 안 쓰는 게 더 간단하던데... 뭐지?