Python Dict Set 설명

이전 list tuple 포스트에 이어 python의 사전 dict와 집합 set 에 대해 설명해 보겠습니다.

dictset은 내재적 순서가 존재하지 않지만 특정 데이터를 고유하게 참조할 때 유용하게 쓰이는 자료구조입니다.
dict와 set의 차이점은 dict에는 key:value쌍이 존재한다는 점이고, set은 value가 없이 key로만 접근한다는 점입니다.
또한, 앞서 소개한 list tuple은 탐색알고리즘이 O(log n)이 걸리는 데 비해 dict와 set은 hash table에 의존하여 O(1)시간복잡도로 찾을 수 있습니다.



작동원리

dict와 set은 둘 다 해시 테이블을 사용합니다.


삽입

데이터를 삽입하면 먼저 키를 해시한 후 배열의 색인으로 쓸 수 있는 형태로 만듭니다.
해시의 예시를 들면, 8개의 메모리 블록이 있으면 111(2)를 마스킹 처리하는 것입니다.
7이라는 값을 해시하면 7이고 8을 해시하면 0으로 해시되는 것입니다!
이렇게 블록으로 할당하고 나면 8, 0은 같이 0으로 해시되어 중복되는 일이 생길 것입니다.

해시 테이블에 이 블록들을 가능한 균등하게 분포되어 있어야 합니다. (=로드 팩터 load factor)
새로운 색인 찾는 과정을 프로빙(probing)이라고 하는데 python 에서는 선형 프로빙(linear probing)을 사용합니다.
자세한 설명은 생략하고, 선형 프로빙은 마지막 몇비트만 사용하고 나머지는 무시하고, 중복될 경우 추가 비트를 사용해서 해시를 진행한 다는 점입니다!

탐색도 똑같습니다

해시함수(__hash__)는 파이썬 기본내장되어 있어 따로 해시함수를 만들 필요는 없을 것입니다.


삭제

삭제같은 경우는 해당 블록이 비어있음을 특수한 값으로 기억해두고 나중에 비어있음으로 생각하고 사용한다.


해시테이블 크기

해시테이블은 테이블의 2/3정도 채워지면 충돌 횟수와 공간 활용 측면에서 적절한 비율이라고 생각한다고 합니다.
최소 크기는 8에서 50,000까지는 4배씩 증가하고 그뒤로는 2배씩 증가합니다. (삽입연산에서만)


해시함수와 엔트로피

앞서 말한 해시를 균일하게 분포되도록 신경써야 하는 것이 해시 함수의 엔트로피 라고 합니다.
image
P(i)는 해시함수가 i를 출력할 확률로, P(i)가 전부 동일할 때 엔트로피가 최대로서 최소충돌하는 완전 해쉬 함수 이다.

또 크기가 N인 사전의 최소크기는 (N x 5) / 3이다.
정리하면, 1000인 사전의 최소크기는 1,699고 앞서 말한 해시테이블 크기 증가(8, 32, 128, 512, 2048 …)에 따라 가장 가까운 2048을 사용합니다. 따라서 마스크로 (2048-1)을 이진수로 바꿔 사용합니다.


고찰

python에서 유용하게 쓰는 dictset을 알아보았습니다.
탐색이 O(1)으로 제가 가장 많이 쓰는 자료구조이기도 합니다.
기본적으로 python으로 내장되어있는 자동으로 해시테이블을 잘 이용하면 될 것 같습니다.
핵심은 해시테이블로 적절한 엔트로피를 만족하기위해 파이썬 내부에서 어떻게 작동하는지를 알아 보았습니다.
가장 큰 해시테이블을 사용할려면 정수전체로 사용하면 충돌날 일이 적겠지만, 적절한 해시테이블의 크기도 있기 때문에 현실적으로는 불가능합니다.
알고 쓰니까 뭔가 느낌이 다른 것 같습니다. 물론 좋은 해시함수를 짜면 좋겠지만, 더욱 수고로움이 들기 때문에 알아두기만 하겠습니다.




출처
  • 고성능 파이썬 책
  • https://github.com/scari/high_performance_python/
  • https://github.com/dsindex/blog/wiki/%5Bstatistics%5D–Entropy,-Relative-Entropy-and-Mutual-Information