Hahing

03 Apr 2018 • 알고리즘

사진

이 포스팅의 알고리즘 강의는 이곳에서 보실 수 있습니다.

Hash table

  • 해쉬 테이블은 dynamic set(집합)을 구현하는 효과적인 방법의 하나이다.
    • 적절한 가정하에서 평균 탐색, 삽입, 삭제시간이 O(1) => 하지만 여러가지 조건이 만족된다는 가정이 붙는다.
    • 보통 최악의 경우 O(n)
    • RB트리: O(logN)
  • hash function을 사용하여 키 k를 T[h(k)]에 저장 (T는 테이블 h()는 해쉬함수)
    • h: U -> {0, 1, …, m-1} (여기서 U는 모든 가능한 키들의 집합, m은 테이블의 크기)
    • 키 k가 h(k)로 해슁되었다고 말한다. 사진
  • 모든 키들을 자연수로 가정할때 문자열 “CLRS”를 해쉬함수에 넣어보면
    • ASCII 코드: C=67, L=76, R=82, S=83.
    • (67 * 128의 3승) + (76 * 128의 2승) + (82 * 128의 1승) + (83 * 128의 0승) = 141,764,947
    • 어떤 데이터든지 자연수로 해석하는 것이 가능하다.
    • 해쉬 함수의 간단한 예로 h(k) = k % m이 있다.(모듈러를 사용) 이러면 값은 0~m-1이 나온다.

충돌(Collision)

  • 두 개 이상의 키가 동일한 위치로 해슁되는 경우를 말한다. (즉, k1, k2에 대해서 h(k1) = h(k2))
  • 일반적으로 전체집합 U가 해쉬테이블 m보다 크므로 충돌은 항상 발생할 수 있다.(즉 단사함수가 아니다.)
  • 또한 저장된 값들이 테이블의 크기 m보다 크면 당연히 발생한다. 사진

Chaining에 의한 충돌 해결

  • 동일한 장소로 해슁된 모든 키들을 하나의 연결리스트(Linked List)로 저장한다.
  • 이때 hash table은 연결리스트 시작주소만 가진다. 사진
  • 키의 삽입(insert)
    • 키 k를 리스트 T[h(k)]의 맨 앞에 삽입한다 했을때 시간복잡도는 O(1)이다.
    • 이때 중복된 키가 들어올 수 있고 중복 저장이 허용되지 않는다면 삽입 시 리스트를 검색해야 하므로 시간복잡도는 O(리스트의 길이)이다.
  • 키의 검색(Search)
    • 리스트를 순차검색해야하므로 정렬이 되든 안되는 시간복잡도는 O(리스트의 길이)
  • 키의 삭제(Delete)
    • 리스트로 부터 키를 검색 후에 삭제하므로 일단 키를 검색해서 찾은 후에는 시간복잡도 O(1)
  • 최악의 경우는 모든 키가 하나의 슬롯으로 해슁되는 경우 탐색시간은 O(n)+해쉬함수 계산시간
  • 따라서 평균 시간복잡도는 키들이 여러 슬롯에 얼마나 잘 분배되느냐에 의해서 결정된다.

Open Addressing에 의한 충돌 해결

  • 모든 키를 해쉬 테이블에 저장하며 테이블의 각 칸(slot)에는 1개의 키만 저장한다. (충돌이 생기면 다른곳에 저장한다.)
  • 충돌 해결 기법으로 Linear probing, Quadratic probing, Double hashing등이 있다. 사진
  • Linear probing의 단점은 primary cluster가 생길 수 있다는 것이다. (cluster란 데이터가 테이블의 한 부분에 뭉쳐있는 현상을 말함)
  • cluster가 생성되면 이 cluster가 점점 커지면서 검색시간이 cluster의 길이에 비례하게 될 수 있다.
  • 이 문제를 보완하기 위해 Quadratic probing, Double hashing을 사용한다.
  • Quadratic probing을 사용할때 해쉬함수 뒤에 추가되는 식은 바꿔도 된다. 사진 사진

OpenAddressing - 키의 삭제

사진

  • 위와 같은 상황이 되면 C2가 없다고 인식된다.
  • 삭제 한 후 삭제마크를 추가한다 해도 모든 칸들이 마크로 채워지면 검색을 할때 적당한 지점에서 검색을 멈추지 못한다.
  • 그래서 키를 삭제할때 뒤의 키값들을 위로 옮겨야한다.(성능에 영향을 끼친다.)

좋은 해쉬 함수란?

  • 현실에서는 키들이 랜덤하지않다. -> 랜덤 데이터에 대해서 성능이 좋은건 충분하지않다. 현실에서는 정렬된 데이터도 충분히 존재한다.
  • 요점은 hash의 성능은 key가 얼마나 테이블에 골고루 분포하느냐가 관건이다.
  • 키들이 어떤 특정한 패턴을 가지더라도 해쉬함수값이 불규칙 적으로 하는게 바람직하다.
  • Division 기법
    • h(k) = k % m (테이블 사이즈 m으로 나눈다.)
    • 보통 모든 과정의 마지막에 사용된다(이것만 사용하는건 좋은 해쉬함수가 아니다!!)
    • 이것만 사용할경우 m=2p일 경우 키의 하위 p비트가 해쉬함수값이 될 수 있다.
  • Multiplication 기법
    • 0과 1사이의 상수 A를 선택해서(0<A<1) kA의 수소부분만을 택한다.
    • 소수 부분에 m을 곱한 후 소수점 아래는 버린다. 사진
  • 해쉬함수값을 예측하기 어렵게 하기 위한 기법은 왜 그렇게 된다는지 생각하는건 무의미하다. 왜냐하면 해쉬함수의 값이 특정 부분에 의해서만 결정되게 하지 않기위해서 사용하기 때문에 방법은 다양해질 수 있다.

Comments

Related Posts