2024 자료구조개론 & 알고리즘개론 정리 - 2. Hash Table

 

 

 

2024 자료구조개론 & 알고리즘개론 정리 - 2. Hash Table 

 

 

• 1. 배열과 링크드리스트 
• 2. Hash Table
• 3. Queue & Stack 
• 4. Tree & Graph 
• 5. Sorting 
• 6. Recursion 
• 7. 최적화 기법 (DP, Greedy, Divide & Conquer)

 

 

---

 

 

• 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에 대한 아주 긴 주석을 볼 수 있게 되는데, 이를 읽어보면 파이썬 언어 개발에 참여한 개발자들이 얼마나 많이 고민을 했는지에 대해서 알 수 있다.

 

 

Reference

 

https://neos518.tistory.com/225

Python Dictionary 구조 CPython 소스 코드 레벨부터 파악하기