캐럿보이넷 :: 해싱(Hashing)

해싱(Hashing)

  1 해싱의 개념

  • 파일을 구성하거나 특정 자료를 검색할 때 다른 검색 방법에서처럼 키 값들을 비교하면서 찾는 것이 아니라 해싱 함수로 계산된 키 값이 지적하는 주소로 직접 접근(key to  address transformation)

  • 키 값을 주소를 변환해 주는 것을 사상(mapping)이라 함

  • 이 때 해싱 함수로 계산된 값에 해당하는 위치에 각 레코드를 기억시킨  표를 해시표(hash table)라 함

  • 해시표는 해싱 함수에 의해 계산된 값(주소)에 레코드를 기억시키는 여러 개의 버킷(bucket)들로 구성된 기억 공간

  • 각 버킷은 하나 이상의 슬롯(slot)으로 구성되며, 각 레코드는 이 슬롯에 저장된다.

  • 해시표는 시작 주소에서 각 버킷들을 연속된 주소를 가짐

  • 해싱 함수는 여러 키들의 계산 결과 값들이 해시표의 정해진 범위에 고르게 분포하도록 해주는 함수이어야 한다

  • 해싱 함수의 조건

  ① 계산이 빠르고 쉬워야 한다.

  ② 서로 다른 값을 갖는 키들에 대한 결과 값들은 서로 중복되지 않아야 함

  • 만약 위의 두 번째 조건이 잘 맞지 않는 함수

        → 같은 주소를 생성해서 충돌(collision)을 일으킴

        → 충돌이 일어난 레코드들을 동의어(synonym)이라 한다 

  • 과잉 상태(overflower):해당 버킷에 더 이상 레코드를 저장할 수 없을 때

  • 만약 버킷 당 슬롯의 개수가 1개라면

        → 충돌과 과잉 상태가 동시에 발생한다.

그림 8.1 해싱

  2 해싱 함수의 종류

1) 나눗셈 법(division method)

  • 레코드의 키 값 k를 해시 테이블의 크기 m으로 나누어 그 나머지를 버킷 주소로 사용

                          h(k) = k mod m

  • 나눗셈법에서는 m의 선택이 중요함

      → 보통 버킷 크기에 가장 가까운 소수(prime number)로 정한다

  • 예) 키 값 : 12345

       버킷의 수 : 5,000 일 때 버킷 주소

            →  나머지 값 2347이 버킷 주소가 된다

                 12345 ÷ 4999 = 몫 2 -- 나머지 2347

  2) 중간 제곱법(mid-square)

  • 키 값을 제곱하여 제곱된 값의 중간 부분을 선택

               →  버킷 주소로 하는 방법

  • 예) 키 값 : 700478

        버킷수 : 5000일 때 버킷 주소

               →   4706이 버킷 주소

                    700478² = 4907 9412 1489

                       9412 * 0.5 = 4706

 

3) 접는 법(folding)

  • 키를 여러 부분으로 나누고 각 부분의 값을 더하여 버킷 주소를 계산

  • 이동 접지(shift folding) : 접는 법을 각 부분의 우측 끝을 맞추어 더한 값을 버킷 주소로 함

  • 경계 접지(bounding folding) : 인접되어있는 부분을 역으로 더하는 방법

4) 숫자 분석법

  • 비트 추출법(bit extraction method)이라고도 함

  • 키를 분석하여 중복이 많이 발생하는 자릿수를 제외하고

                   중복이 발생하지 않는 자릿수를 선택하여

               → 버킷 주소로 하는 방법

  • 예) 다음 레코드 키 값에 대해 버킷 크기가 1000일 때 숫자 분석법을 적용  → 버킷 주소 선택

5) 기수 변환법(radix exchange method)

  • 레코드의 키 값을 다른 진법으로 간주하고

        이 키 값을 10진수로 변환 후

           →  필요한 자릿수만 선택하면 된다

  • 예) 다음 레코드 키 값 576143에 대해 기수 변환법을 적용

           → 버킷 주소를 계산 ( 여기서 버킷 크기는 1000이다.)

(576153)₁₆ = (5726531)

5 * 16⁵ + 7 * 16⁴ + 6 * 16³ + 1 * 16² + 4 * 16¹ + 3 * 16⁰   =   5726531

     ⇒   버킷의 크기가 1000  하위 3자리만 선택

              →  531이 버킷 주소가 된다

6) 무작위법(pseudo random method)

  • 난수 발생 프로그램을 이용하여 난수(random number)를 발생

        →  이 난수를 버킷 주소로 사용

  • 만약 충돌이 발생하면 다음 난수를 사용

  3 과잉 상태의 처리

  • 충돌(collision)은 버킷에 레코드를 저장할 때

        →  서로 다른 레코드가 같은 버킷 주소에 대응될 때 발생

            이 주소에는 이미 다른 레코드가 저장되어 있으므로

                현재 계산된 버킷 주소에는 레코드를 저장할 수가 없다

         →  이 현상을 충돌이라 한다

  • 해결 방법 : 다른 버킷 주소를 할당해서 그 주소에 레코드를 저장하는 것

  • 과잉 상태(overflow) 처리 : 충돌을 유발한 레코드를 저장할 다른 기억 장소를 계산해 충돌을 해결하는 과정

  • 과잉 상태 처리 방법 : 다음과 같다

1) 선형 방법(linear method)

  •  충돌이 일어난 버킷 주소에서

        →  다음 주소를 차례로 탐색하여 처음으로 나오는 빈 버킷에 충돌이 일어난 레코드를 저장

  • 단순하며 간단

  • 그러나 다음 주소를 찾는 탐색 시간이 많이 소요

    버킷에 저장되어 있던 레코드를 삭제할 경우

       →  레코드가 충돌 레코드인 경우에 연결 정보가 사라지게 된다

  • 그러므로 특정 비트를 두어 레코드가 삭제되었음을 표시되게 하면 된다

2) 2차 검색 (quadratic probing method)

  • 충돌이 발생한 자리에서부터

       →   d²(d=1, 2, 3…) 즉, 1, 4, 9,… 만큼 떨어진 곳을 차례대로 탐색

               처음 나오는 빈 버킷에 충돌을 발생시킨 레코드를 저장

  • 매우 간단

  • 레코드들이 일정한 주소를 중심으로 뭉치는 것 → 어느 정도 방지 가능

  3) 난수 검색법(random probing method)

  • 난수를 발생 → 버킷 주소로 택하여 충돌을 해결

     4) 해시 연쇄 처리법(hash chaining)

  •  충돌이 발생한 레코드들을 연결 리스트로 연결하여

          → 같은 버킷에 할당되는 레코드들을 체인으로 연결한 것

  •  연결 리스트의 사용으로 삽입이나 삭제가 용이

  • 충돌이 발생한 레코드를 찾기 위해 버킷을 검색할 때

            → 그 시간을 줄일 수 있다

---

: http://blog.naver.com/post/postView.jsp?blogId=aram96&logNo=20010709841&from=search