[박혜웅] 해싱(hashing)

•   해싱(hashing)의 특징

  • 평균적으로 탐색속도 빠름

  • 임의적인 순서

    • 순차탐색 불가능
  • 해시함수(알고리즘)와 해시테이블(데이타저장소)로 구성됨

  • 해시를 사용하기 위한 필요 지식

    • 영역(저장할 데이타)에 대한 지식
    • 저장할 키의 수
    • 데이타 안정성(?)
  • 
     

 

• 성능

  • 탐색: O(1) ~ O(n)

    • 해쉬함수나 입력되는 데이타에 따라 다름
  • 삽입/삭제: O(1) ~ O(n)

  • 성능 결정 요인

    • 적당한 비사용 공간과 충돌의 수가 되도록 하는 것이 최적화 방법

    • 충돌의 수

      • 충돌이 많을 수록 탐색속도 저하
      • 충돌을 적게할 수록 비사용 저장공간 크기 증가

 

• 해쉬 함수(hash function)

  • 키를 입력받아서 해시주소(hash address)를 생성하는 함수

    • 예: h(key)= key mod 9 일 때, key=13, hash address=4

  • 해쉬함수의 기본형태

    • h(k) = f(k) mod m (단, 버킷의 수=m)

  • 이상적인 해쉬함수의 조건

    • 충돌이 발생하지 않도록 모든 요소를 완전히 분산시키는 함수

  • 좋은 해쉬함수의 예

    • h(k) = f(k) mod m 에서 f(k)의 예(key=문자열 일때)

      • f(k)= 모든 k의 바이트를 모두 곱하거나 합한 값
      • f(k)= 중간 또는 마지막의 바이트 값들
      • f(k)= 일부 중간바이트의 자승 값

  • 잘못된 해쉬함수의 예

    • key= 2의 제곱수, hash(k) = k mod 5

      • 2의 제곱수는 모두 짝수 이므로 버킷 0은 항상 비어 있다.

    • key= 이름중 성의 첫문자, hash(k) = k의 첫글자

      • 성의 첫문자의 분포가 고르지 않다.

  • 충돌(collision)

    • 다른 키가 동일한 버킷(해쉬값)으로 사상될 때 발생

    • 해결방법

      • 개방주소법(open address):

        • 이중해싱: 충돌된 키에 대해 새로운 색인값을 계산

      • 오버플로우주소법

        • 연쇄법(chaining): 충돌되는 원소들을 연결리스트로 연결
        • 탐색효율이 선형탐색처럼 낮아질 수 있는 위험존재.

  • overflow

    • 새로운 데이타를 입력하려고 할 때, 버킷이 가득차서 더 이상 삽입할 수 없는 경우

  • rehashing(재해싱)

    • 해쉬테이블을 재구축함
    • 일반적으로 해쉬테이블이 75~80% 찼을 때, 재해싱 적용

 

 

• 해시테이블(hash table)의 기본 구조

  • 버킷(bucket)

    • 1개 이상의 슬롯(slot)이으로 구성
    • 배열 또는 연결리스트로 연결됨.

  • 슬롯

    • 1개의 데이타가 들어감
    • 버킷이 배열일 경우, 슬롯은 데이타만 저장됨.
    • 버킷이 연결리스트일 경우, 슬롯은 (데이타+다음노드 위치포인터)가 저장됨

 

 

• 충돌(오버플로우) 해결 방법

• • open addressing(공개 주소방식): 1개의 버킷에 1개의 키(데이타)입력, 충돌시 다른 버킷으로 키(데이타) 입력

    • linear probing(선형 조사법)

      • h₂(b) = (b+i) mod m (단, i=1,2,3....)
      • 충돌이 일어나면 한 칸씩 다음 버킷을 검사(조사)하여 빈곳에 데이타 삽입
      • 끝까지 조사해도 빈 곳이 없으면 버킷 0부터 다시 조사
      • 버킷이 가득 찰 수록 조사회수가 버킷의 개수 m에 가까워짐
      • 선형탐사의 경우 데이타가 특정 버킷을 중심으로 모이는 cluster(클러스터) 현상이 발생하기 쉬움

      • 예

        • h(k) = k mod 31 이고, 65, 34, 127 순으로 데이타 삽입
        • 
          
          

    • quadratic probing(제곱 조사법)

      • h₂(b) = (b+i²) mod m  (단, i=1,2,3....)
      • 충돌이 일어나면 버킷의 간격을 1,4,9.... 순으로 이동하여 검사함
      • 
        
        

    • double hash

      • 충돌시 다른 해쉬함수를 이용하여 빈 버킷을 검사
  • closed addressing(비공개 주소방식): 1개의 버킷에 여러 개의 키(데이타)입력
  • • chaining(체인법 )
    • • 체인형 해쉬(chained hash)

      •  

        

        • 버킷이 연결리스트로 구성됨

          • 새로운 데이타(item)가 추가될 경우 연결리스트의 맨 앞에 삽입

            • 일반적으로 최근의 정보가 검색될 확률이 높으므로

        • 탐색 성능:  n/m에 비례

          • n=키의 수, m=버킷의 수이고, 모든 체인의 길이가 동일한 경우