해쉬 테이블, 문자열 탐색(라빈 카프 알고리즘)

1point·2023년 5월 28일

테이블 자료구조는
탐색에있어서 O(1) 의 탐색 속도를 보인다.

학번	이름
2020000001	무식
2020000002	무찬

key값(학번) 을 알면 value(이름) 을 바로 찾을수 있기 때문에 테이블은 탐색에서 O(1)의 시간복잡도를 보인다.

"그냥 배열의 idx 2020000001 에 "무식" 을 저장하면 되는거아니야?"
라고 생각 할 수있는데 그만큼의 학생을 받을 수 없기 때문에, 메모리 낭비가 너무 심하다.
-> 나머지 연산을 활용해서 겹치지 않게 메모리를 활용해보자.
학생이 100명미만으로 있다고하면, f(x)=x%100 라는 함수로, key 값의 범위를 줄여보자.

여기서 f(x)를 해쉬함수 라고한다.
역할 : 넓은키의 범위를 좁은 키의 범위로 변경해준다.
위의 예 만 보더라도 10자리의 key 값을 -> 2자리의 key값 으로 줄여준다.

근데 범위를 줄이면, 겹치는 idx가 많지않을까? 라는 생각을 하게되는데,
이를 "충돌" 이라고한다.
만약 "충돌" 이 일어난다면?

길이를 올린다? -> 뭐 해결 될 수도있지만, 충돌 될때마다 메모리르 늘리는것은 문제를 해결했다고 할 수는없다.
해쉬 함수를 잘 만들어서 충돌을 줄여야한다!

즉 "좋은 해쉬" 를 만들어야한다.

"충돌" 의 해결책 :

먼저 좋은 해쉬란?

데이터가 한쪽에 몰리지않고, 고르게 분포하도록 만드는 해쉬함수를 "좋은 해쉬함수" 라고 할 수 있다.

자 본문으로 돌아와서
충돌의 해결책을 살펴 보도록 하자.

선형조사법 :

f(key)=key%10 라고하자.
key=11 과, key=1 의 f(key) 는 1로 같다. 즉 idx=1 에서 충돌을 보인다. 그럴때 한 칸 더 이동해서 빈 자리를 살피는 방법이다.

이렇게 한칸씩 넘어가면서 자리가 있는 지 확인하고, 자리가 비었다면 값을 넣어주는 방식이다.
즉 f(k)+1 -> f(k)+2 ..... 이다.

근데 선형조사법으로 충돌문제를 해결하려고 한다면, 충돌의 횟수가 증가함에따라 클러스터현상 즉 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다는 단점이 생긴다.

이차조사법 :

이차 조사법은 충돌 발생시, f(k)+1^2 -> f(k)+2^2 ..... 로,
좀더 멀리서 빈공간을 찾으며 전개된다.
이렇게하면 클러스터 현상을 덜 증가 시킬 수 있을것이다.
그래도 여전히 클러스터 현상의 발생률은 높다.

선형 조사법과, 이차조사법의 불편한점

선형, 이차 조사법을 적용했다면, 탐색의 과정에서도 이를 근거로 충돌을 의심하는 탐색의 과정을 포함시켜야한다.

이중해쉬

해쉬를 두개를 만든다.
ex)
1차 해쉬함수 : h1(k) = k % 15
2차 해쉬함수 : h2(k) = 1 + (k % c)

1차 해쉬함수를 %15 라고 결정한 것으로보면, 배열의 길이가 15라고 예상할 수있다.
이때 c는 15보다 작으면서 소수중 하나로 결정해야한다.
why? :
15보다 작은 값인이유 : 가급적 2차 해쉬의 값이 1차 해쉬 값을 넘어서지 않게 하기위함이다. (인덱스를 벗어 날 수도 있기때문.)
소수로 결정하는 이유: 소수를 선택했을때 클러스터 현상의 발생 확률을 현저히 낮춘다는 통계를 근거로 한 것.

실제로 이중해쉬는 이상적인 충돌해결책으로 알려져있다.