[Data Structure/python] Hash Table (DAT, Collision, Open Addressing, Seperate Chaining)

 

 

 

[Data Structure/python] Hash Table
(DAT, Collision, Open Addressing, Seperate Chaining)

 

 

 

 

 

• Direct Address Table (DAT)
  • key:value 쌍에서 key값 그 자체를 index로 넣는 방법 
  • 문제점 
    • Key값에 다양한 자료형 넣을 수 없음 (string, ... )
    • 메모리 낭비 -> key가 1, 20000001, 300001일 때 최소 20000001까지 사용됨 

 

 

 

• 이 문제를 해결하기 위한 Hash Table 
  • Hash Function을 이용하여 각 Key값에 index번호 부여 
  • 이 Hash Function을 어떻게 정의하느냐에 따라 효율성 달라짐
  • 좋은 Hash Function의 기준 
    • 연산 속도가 빨라야 하며, 
    • 충돌(Collision)이 일어나지 않게 해야 함 == 해시값이 최대한 겹치지 않게 한다 

 

 

 

• 그럼에도 불구하고 Collision이 발생한다 이를 해결할 방안은?  
  • 크게 두 가지 해결 방안 : 1) Open Addressing / 2) Seperate Chaining 
  • 1) Open Addressing 
    • collision 발생 시, 미리 정한 규칙에 따라 hash table에 비어있는 slot을 찾는다 
    • 추가적인 메모리 사용하지 않아 Seperate Chaining방식보다 메모리를 적게 사용한다 
    • 종류
      • Linear Probing (선형 조사법)
        • 충돌한 해시값으로부터 일정한 값만큼 건너뛰어가며, 비어있는 슬롯에 값 할당
      • Quadratic Probing (이차 조사법)
        • 제곱수 만큼 뛰어넘음 
        • 단, Linear/Quadratic Probing은 충돌횟수가 많아지면 특정 영역에 그 값이 몰리게 되는 클러스터링 현상이 발생하게 됨 (탐사 이동 폭이 같기 때문에) -> 평균 탐색 시간 늘어나게 되는 한계 있음 
      • Double Hasing (중복해시)
        •  위의 Clustering 문제가 발생하지 않도록 하기 위해, 2개의 해시 함수를 사용하는 방법
        • 하나는 최초의 해시값을 얻을 때 사용하고, 또 다른 하나는 해시 충돌이 일어날 때 탐사 이동폭을 얻기 위해 사용함 
  • 2) Seperate Chaining 
    • 충돌이 발생하면 linked list에 노드를 추가하여 데이터를 저장
    • worst case의 경우, N개의 모든 key가 동일한 해시값을 갖게 되어 길이 n의 linked list가 생성되면 탐색의 시간 복잡도 O(N)됨 

 

 

 

•  파이썬에서는 Dictionary 라는 자료구조를 통해 해시를 제공한다

 

 

 

 

궁금한 것 

 

 

 

• 그렇다면 파이썬의 dictionary에서는 어떻게 Collision에 대처하나? 
  • Open Addressing 방식을 사용하나, 파이썬 고유의 'Perturbation Shift Probing' 알고리즘을 사용한다고 함 
  • https://svn.python.org/projects/python/trunk/Objects/dictobject.c를 보면, 이 Probing에 대한 아주 긴 주석을 볼 수 있게 되는데, 이를 읽어보면 파이썬 언어 개발에 참여한 개발자들이 얼마나 많이 고민을 했는지에 대해서 알 수 있다.
  • 참고 
    • https://neos518.tistory.com/225

 

 

 

 

 

 

이전 기록

 

 

 

자료구조의 선택

• 이름대신 번호가 주어졌다면?
  • 배열을 이용
• 문자열로 접근할 수 있는 좋은 자료구조는 해시(Hash)

 

 

 

해쉬 문제 해결 방안 

•  hash는 딕셔너리로 푼다 ! → 파이썬에서는 Dictionary 라는 자료구조를 통해 해시를 제공합니다. 그리고 Dictionary는 dict클래스에 구현되어있습니다!
• 딕셔너리는 리스트보다 연산 속도가 훨씬 빠르다
  • https://yunaaaas.tistory.com/46
• Counter 함수는 개수 세서 딕셔너리 반환 !
  • DAT (Direct Addressing Table)

 

 

개념 정리 

 

Direct Addressing Table이란? 

 

 

 

 

 

 

 

 

https://github.com/AAISSJ/AlgorithmStudy/blob/main/README.md

GitHub - AAISSJ/AlgorithmStudy: [2022.11 ~] Problem Sloving with algorithms ✍️