•   해싱(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(선형 조사법)

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

      • quadratic probing(제곱 조사법)

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

      • double hash

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

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

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

              • 일반적으로 최근의 정보가 검색될 확률이 높으므로
          • 탐색 성능:  n/m에 비례

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

 

Posted by 바게 BAGE