13강 Hash Table

• Hash Tables : 연관된 데이터에 심볼을 연결시키는 심볼 테이블이다.

  • symbol : 변수명, 절차명 등 / 연관된 데이터 : memory 위치, call graph 등
  • table은 표이므로, 사전과 비슷하기에 정렬순서를 신경쓸 필요가 없다!
  • 예시

  

  • hash 함수 h는 key를 해쉬테이블의 index로 변환한다. (mapping) U → {0,1,…,m-1}
  • 이러한 상황을 “k가 h(k)로 hash했다.” 라고 표현한다.

• 해쉬 테이블의 주요 함수?

  • Insert(T,x)
  • Delete(T,x)
  • Search(T,x)
  • 이 3개의 과정은 모두 평균적으로 O(1)

• Direct-address 테이블

  • key가 0~m-1 / key는 모두 다름
  • 설명 : x라는 value가 배열 T안에 있고 x에 대한 키가 i일때, T[i] = x / 나머지는 NULL

  

  • 앞서 말한 삽입, 삭제, 탐색 함수는 다음과 같이 구현

  

  • direct addressing 의 문제점

    • key의 범위 (m)에 따라 테이블의 크기가 결정되는데
      • key가 32bit 정수라면 → key값의 범위 : 2^32개의 엔트리가 되므로
        • 문제점 1 : 많은 메모리가 요구된다.
        • 문제점 2 : 메모리를 문제로 보지 않더라도, 초기화하는데 시간을 많이 사용한다.

  • Hash function의 문제점

    • Collision

      • key가 같은 인덱스를 가리키면 collision 발생!

      

      • collision의 해결방법

        • chaining : 데이터를 체인으로 연결

          • 같은 인덱스를 가리키면 linked list로 뒤에 연결시켜버림

          

          • 새로 연결되는 친구를 앞에다가 배치 (뒤에 연결되어있는 리스트가 먼저 연결된 친구들)
          • 삭제할 때도 체이닝된 곳을 찾아가 삭제하면 됨

          

          • 특정 슬롯에 매핑될 확률이 동일하다 가정할 때
            • load factor a = n(key수) / m(슬롯 수) → 슬롯당 연결된 평균 키의 갯수
              • key를 검색하는데 실패한 경우의 평균적인 비용은 O(1+a) (특정 리스트에 존재하는 키가 a개니까)
              • key를 검색하는데 성공한 경우의 평균적인 비용은 O(1+a/2) (키가 평균적으로 중간 위치에 존재하기에)
              • 검색에 대한 cost : O(1+a) → a가 상수라면(n이 m에 비례하면) ⇒ a = O(1)

        • Hash 함수 :

          • The division method 나머지를 이용 → 키가 특정 슬롯에 몰리지 않게 해야함(고르게 분포!)

            • h(k) = k mod m (나머지)

              • 장점 : 빠르다, 하나의 연산이 필요하다
              • 단점 : m의 특정 값이 구리다 → m = 2의 거듭 제곱(쉬프트 때문에 k의 하위 비트에 의존하게 되어 균일한 분포가 깨짐), 자연수
              • m이 어떤 값인 경우에 좋냐?
                • m = 소수, 2의 거듭제곱에 너무 가깝지 않은 수 ..

              

              • 701이면 소수이고, 2의 거듭제곱도 아니기에 적당한 load factor가 유지됌

          • The multiplication method 키와 상수를 곱한 후 결과의 소수 부분을 이용

            

          • key k * 상수 A (0 < A < 1)

          • kA mod 1 또는 kA - kA의 정수부분(floor함수로 표현) → 이 값을 m과 곱합

            • 그 값을 정수부분만 취해주고 테이블의 슬롯 인덱스로 사용하면 됨

          • h(k) = floor(m * (kA mod 1)) or floor(m * (kA - floor(k * A))

          • 장점 : m이 소수일 필요도 없고 2의 거듭제곱을 사용할 수 있다.

            • A를 0이나 1에 가깝게 설정하면 안된다. 좋은 A선택시 균일하게 만듦!

          • 단점 : 나눗셈 방법보다는 느리다.

            • A = 루트5 - 1 / 2(황금비율) 일때 최적의 상수가 된다.

          • Universal Hashing 악의적인 키(한쪽으로 몰리는 것) 선택에 대해 해시 테이블의 성능을 보장하는 방법이다. → 균일한 분포 보장

            • m = 소수, key x → {x0, x1, … , xr}로 분해, 랜덤 계수 {a0, … ,ar} ai는 0~n-1중 랜덤 선택

            

            • 해쉬 함수는 위와 같아진다.
            • 장점 : 랜덤화를 통한 고른 분포, 충돌 확률 제어, 악의적인 키 선택을 방지
            • 해쉬 함수가 어떤 것인지에 따라서 잘 하면 될 것 같다!

            

        • open addressing

          • 우리가 충분히 연속적인 메모리를 가졌다면(m > N) → key를 해시테이블 스스로에 저장 (즉, 링크드 리스트가 필요하지 않다.) ⇒ collision 해결!
          • 기본적인 아이디어 : 슬롯이 다 찼다면 다른 슬롯을 시도 → 비어있는 슬롯을 발견할때까지
          • 탐색 과정 : 만약 정확한 키에 대응하는 요소를 마주쳤다면, 바로 그값을 리턴 / NULL을 마주쳤다면, 테이블에 요소가 없는 것이다.
          • 예시 (key4가 해쉬 결과로 3이 나왔는데 3에는 key1이 존재 → index 5로 배정)

          

          

          • pseudocode

          

        • Linear Probing

          • Probing : 테이블에서 collision이 발생하면 다음 사용 가능한 위치를 확인함

          

          • Search : 값이 발견되거나 빈 위치가 발견될 때까지 상위 인덱스 탐색(테이블의 시작 부분까지)
          • Delete : initial(empty) vs 있었다가 지워짐(sentinel 값을 DELETED로 표시) ⇒다름 / 이 둘을 구분해야 됌 !

        • Double Hashing

          • 첫번째 해쉬 함수를 이용해 첫번째 슬롯 결정
          • 두번째 해쉬 함수를 이용해 probe 순서에 대한 증분을 결정
          • 장점 : 클러스터링(군집)을 방지할 수 있다.
          • 단점 : 요소를 삭제하기가 더 어려워졌다.

          

          • 실제 예시 (음.. 약간 구분을 더 잘 하게 되는듯? 매핑확률 더 공정하게)

          

          • 처음에 first 해시 함수만 적용 → 1 → 누가 있음 → second 해쉬 함수(i=1) 적용 → 5 → 누가 있음 → i를 늘림 → second 해쉬 함수(i=2) 적용 → 9
          • 주의할 점

    15, 16강 Binary Search Trees - AVL Tree

    • Tree 트리, Binary Tree 이진 트리

    

    • 일반적인 트리의 형태

    

    • Search trees support
    • 이진트리의 유형
    • 이진 탐색 트리 Binary Search Trees (BST)
    • Tree Traversal 트리 순회 : 특정 순서로 노드를 처리하는 기법 root(본인) → V
    • 중위 순회 시간 계산