개발 공부 - [해슁] hashing - 2

 Open Addressing에 의한 충돌 해결

    - 모든 키를 해쉬 테이블 자체에 저장

    - 테이블의 각 칸(slot)에는 1개의 키만 저장

        ㄴ 충돌이 생기면 다른 slot에 저장해야 한다.

    - 충돌 해결 기법

        : linear probing (기본적인 해결책)

        : Quadratic probing

        : Double hashing

Linear Probing

- probing은 먼저 해싱을 해서 그 칸이 비어 있으면 저장하고,

이미 다른 키에 의해 차 있을때 순서대로 검사를 해서 빈 슬롯에 저장하는 기법이다.

h(k), h(k)+1, h(k)+2,... 순서로 검사하여 처음으로 빈 슬롯에 저장

테이블의 끝에 도달하면 다시 처음으로 circular 하게 돌아감

찾을 때도 자리 가서 보고 없으면 다시 순서대로 검사를 해야 한다.

이 Linear Probing의 단점은 clustering인데, 키들이 연속해서 뭉쳐져 있는 현상을 말한다.

그러면 cluster의 끝에 더덕더덕 붙을 확률이 커져서 cluster가 눈덩이처럼 길게 늘어나는 현상이 생길 수 있다.

그러면 cluster에 길이에 비례하여 속도가 저하되고,

원래 있어야 할 위치보다 멀리 저장되기 때문에 속도도 저하되고 cluster가 점점 커져서 더 느려지고 하는 현상이 발생한다.

primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미

Quadratic probing

    : 충돌 발생시 h(k), h(k)+1^2, h(k)+2^2 + h(k)+3^2 ... 순서로 시도한다.

    - 리니어와 비슷하나 probing 하는 순서를 바꿔본 것이다.

    : ai^2 + b^i + c 같이 검색 경향을 만들 수 있다고 한다... (잘 모름)

Double hashing

    : 서로 다른 두 해쉬 함수 h1과 h2를 이용하여

    h(k,i) = (h1(k)+i*h2(k)) mod m

    : 일단 이론상으로는 기본적으로 해쉬 함수에 의해 충돌이 발생하면 

    2차 해쉬 함수를 이용해 새로운 주소를 할당하는 방법이다. 

    캐쉬 효율은 3가지 방식 중 가장 좋지 않지만, 클러스터링에 거의 영향을 받지 않는다. 

    또한 가장 많은 연산량을 요구한다.

Open Addressing - 키의 삭제

    단순히 키를 삭제할 경우 문제가 발생한다.

    A2 B2 C2가 순서대로 모두 동일한 해쉬함수값을 가져서 linear probing으로 충돌 해결했을 경우, B2를 삭제한 뒤 C2를 검색해야 한다.

    고로면 B2가 삭제된 것을 확인 한 뒤 , DELETE 마크 같은 것으로 표기해서 삭제 했다고 알 수 있는데... 이러면 probing의 의미가 없으므로 B2를 삭제 한 뒤에 C2를 찾아서

    B2의 자리로 갖다 놔야 하는 것이다.

    

    그러므로 중간에 삭제를 했을 때는 다른 애를 찾아서 메꿔 놓고 땡겨 놔야 한다.

    안그러면 성능에 문제가 있음!

-------------------따르릉----------------------------

좋은 해쉬 함수는

    - 현실에서는 키들이 랜덤하지 않다.

    - 만약 키들의 통계적 분포에 대해 알고 있다면, 이를 이용하여 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어렵다.

    - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 것이 바람직하다

    : 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야 한다.