Python (2) Dict와 Set 차이

Dict과 Set은 특정 데이터를 unique하게 참조할 수 있는 별도 객체가 있는 자료구조입니다. 데이터를 참조하는 일명 참조 객체는 키(key), 데이터를 '값(value)'이라고 한다. (Set에서 key-value쌍이 없고 참조 객체 key만 있습니다.) 하나의  참조하는 객체 키는 일반적으로 문자열을 사용하지만 hashable하다면 어떤 타입이든 상관없습니다.

hashable 타입은 __hash__ 매직함수 그리고 __eq__또는 __cmp__ 매직함수를 구현한 타입입니다. 파이썬 내부 타입은 모두 매직함수가 구현되어져 있다.

Dict과 Set은 모두 유일한 키를 가지므로 주어진(찾고싶은) 색인(객체)을 O(1) 시간복잡도로 찾을 수 있습니다. (리스트는 선형탐색의 경우 O(n)이 걸리는데 말이죠)  그래서 주어진 색인을 빠르게 찾을 수 있다는 것인 Dict과 Set의 특징점이자 장점입니다. 하지만 Dict과 Set은 메모리를 많이 사용하고 hash함수에 의존적이므로 hash 함수가 느리다면 Dict과 Set연산도 느려질 수 있다는 단점을 가집니다.

 

1. Dict과 Set의 차이

Dict과 Set의 차이는 Set에서는 값(Value)이 없다는 점이다. 즉, Set은 유일한 키를 저장하는 자료구조이며 이는 집합 연산에 유용하다는 것을 의미합니다. 

프로그래밍적으로는 다음과 같은 선언 차이가 있습니다.

a = {1: 'a', 2: 'b'} #Dict
b = {1,2,'a','b'} #Set

위에서 알수 있듯이 Set과 Dict모두 중괄호({ })로 정의 되지만 key와 value쌍으로 정의되면 dict type을 가지고 key만 주어지면 set type을 가집니다. (마지막에 보이듯이 빈 중괄호(c={})는 dict type으로 정의됩니다.)

2. Dict과 Set의 동작 원리

파이썬 내부적으로 Dict과 Set의 동작원리에 알고싶다면 계속 읽으시면 좋을 것 같습니다!

위에서 말씀드렸듯이 Dict과 Set은 모두 hashtable을 사용한다고 말씀드렸습니다. 좀 더 구체적으로 hashtable이 어떻게 사용되는 지 알 아보죠.

• Dict의 hashtable은 key, value, hash 을 (메모리에) 저장합니다.
• Set의 hashtable은 key, hash을 (메모리에) 저장합니다.

hash값은 어떻게 계산되는지부터 알아보면 hash값은 key 데이터를 입력으로 hash function의 결괏값을 의미합니다. 여기서 중요한 점은 우리가 입력할 수 있는 수 만 가지(실제로 더 많죠 ㅎ) key값이 있을 텐데... 이 수만 가지의 key값을 입력으로 서로 다른 hash값을 내뱉을 수 있어야 합니다. (이를 만족하는 것을 최소 충돌이라 합니다.) key의 고유한 hash값이 존재해야 O(1) 시간 복잡도로 색인 탐색이 가능하니까요!

실제로 hash function을 거친 output값(hash 값)과 mask와의 연산을 해야 하는데 해당 부분 내용이 많아질 거 같아 생략합니다. 간단하게 말씀드리면 mask는 hash 값이 할당된 메모리 블록의 수보다 작아지도록 조정하는 데 사용됩니다.

그래서 해시 함수는 entropy(엔트로피)가 커지도록 설계해야합니다. entropy는 불확실성을 의미하니 불확실성이 클수록 고르고 균일한 분포의 hash값을 만들어 낼 것입니다. (entropy에 더 궁금하시면 구글링 해보세요 Machine Learning하시는 분이라면 다 이해하실거라 생각하며 저는 넘어갑니다) 그리고 엔트로피가 최대가 되는 hash fucntion은 최소 충돌을 보장하며 Complete hash function이라 합니다.

 

이제는 hash table이 데이터를 어떻게 저장하는지 알아보죠! 그러려면 옛날 버전 python의 hash table 구조부터 알아보죠. (Dict에 대한) 연속된 메모리 주소에 hash, key, value를 저장하는 것을 보실 수 있죠.

--+-------------------------------+
  |    hash       key     value
--+-------------------------------+
0 |    hash0      key0    value0
--+-------------------------------+
1 |    hash1      key1    value1
--+-------------------------------+
2 |    hash2      key2    value2
--+-------------------------------+
. |           ...
__+_______________________________+

그리고 다음과 같이 dictionary를 정의하였다면 

my_info = {'name': 'sinhan', 'birth': '1995-06-23', 'gender': 'male'}

hash table은 다음과 같이 데이터를 저장합니다.

entries = [
    ['--', '--', '--']
    [-230273521, 'birth', '1995-06-23'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [1231236123, 'name', 'sinhan'],
    ['--', '--', '--'],
    [9371539127, 'gender', 'male']
]

위에서 아시겠지만 index 0, 2, 3, 5번 index에는  ['--', '--', '--'] 와 같이 불필요한 데이터가 저장되고 있습니다. 이는 hash table의 데이터 저장이 비효율 적인 것을 알 수 있습니다.  (실제로는 index가 더 많을 것이니 해당 문제가 더 심각해지겟죠!)

 

그래서 현재 pyhton은 index와 (hash, key, value)을 분리시켜 메모리 효율성을 올렸습니다.

Indices
----------------------------------------------------
None | index | None | None | index | None | index ...
----------------------------------------------------

Entries
--------------------
hash0   key0  value0
---------------------
hash1   key1  value1
---------------------
hash2   key2  value2
---------------------
        ...
---------------------

그래서 위 예제의 hash, key, value값은 아래와 같이 효율적으로 저장됩니다.

indices = [None, 1, None, None, 0, None, 2]
entries = [
    [-230273521, 'birth', '1995-06-23'],
    [1231236123, 'name', 'sinhan'],
    [9371539127, 'gender', 'male']
]

  그래서 index 1, 4에 해당하는 [hash, key, value]는 각각 [1231236123, 'name', 'sinhan'], [-230273521, 'birth', '1995-06-23']이 되겠죠. 이를 통해 hash table의 데이터 저장 구조도 알아보았습니다.