Dictionary in Python 3.7

5 min readApr 2, 2020

Python의 Dictionary는 Hash Table로 구현되어 있습니다. 하지만 일반적인 Hash Table의 동작과는 달리 Python 3.7부터는 삽입한 순서대로 Key를 보존합니다.

# Python 3.6
>>> {'a': 1, 'b': 2, 'c': 3}
{'a': 1, 'c': 3, 'b': 2}# Python 3.7+
>>> {'a': 1, 'b': 2, 'c': 3}
{'a': 1, 'b': 2, 'c': 3}

Dictionary before Python 3.7

Python Hash Table은 C코드로 구현되어 있으며 Python 3.7 이전에는 삽입한 데이터는 hash/key/value로 구성된 PyDictEntry 구조체로 정의되었습니다. Python Hash Table은 메모리 상에서 실제로는 PyDictEntry 의 연속된 메모리 블록으로 저장되며, 각 Entry가 저장되는 공간을 Slot이라고 부릅니다.

새로운 key/value가 Dictionary에 삽입되면 아래와 같은 동작이 일어납니다.

Hash Table을 위한 공간을 메모리에 할당합니다. 기본 Slot의 개수는 PyDict_MINSIZE 에 8로 정해져 있습니다.
새로운 Entry가 저장될 Slot을 찾습니다. Slot Index는 hash(key) & mask 의 값으로 정해지는데, 여기서 mask는 Slot 개수보다 1 작은 값입니다.
만약 hash collision이 발생해서 이미 Slot에 Entry가 들어가 있다면 다른 Slot을 찾아야 하는데, Python에서는 Open Addressing이라는 방법으로 해결합니다.
만약 사용된 Slot이 할당된 크기의 2/3에 도달하면 Resizing이 발생하고, 새로운 Slot의 크기는 2의 배수로 증가합니다(만약 초기값인 8이었다면 다음에는 16이 됩니다). Open Addressing과 Resizing에 대한 내용은 다른 글에 기술하겠습니다.
참고로 Table에서 Key를 삭제한다고 해도 크기를 줄이지는 않습니다. 따라서 매우 큰 Dictionary를 만들고 여기서 2/3 이상의 Key를 삭제한다고 해도 메모리 사용량은 큰 변화가 없습니다.

이와 같은 Hash Table의 장점은 두말할 것 없이 hash function을 통해 Index를 찾아서 바로 Slot의 위치를 알 수 있기 때문에 O(1)의 비용으로 빠른 Lookup이 가능하다는 점입니다. 다만 데이터가 입력 순서와 관계없이 Slot Index에 할당되고, 이 과정에서 낭비되는 메모리 공간이 발생하게 되며 이는 Table의 크기가 커질수록 더욱 심해집니다.

Dictionary in Python 3.7+

Python 3.7 이상에서 Dictionary는 데이터의 삽입된 순서를 보장하게 되었습니다.

Changed in version 3.7: Dictionary order is guaranteed to be insertion order. This behavior was an implementation detail of CPython from 3.6.

순서 보장이 가능하게 된 이유는 Dictionary의 구현이 일부 변경되었기 때문입니다.

데이터 구조가 단일 Entry에서 Index를 관리하는 Array(dk_indices)와 Entry를 저장하는 Array(dk_entries)로 나뉘었습니다.
Entry를 저장하는 구조체는 PyDictKeyEntry이며, hash/key/value를 가지고 있습니다.
dk_indices는 char array로 정의되며, 단순히 각 Entry의 Index 값만을 가지고 있습니다. Entry의 Index는 이전 버전과 동일하게 hash function과 mask로 지정됩니다.
dk_entries는 PyDictKeyEntry의 Array로 정의됩니다. Key의 hash값과 관계 없이 입력 순서대로 저장됩니다.
이런 구조를 통해 dk_indices로 빠른 Lookup이 가능하면서 동시에 dk_entries로 입력 순서를 보장 받을 수 있습니다.
다만 dk_entries의 크기는 dk_indices의 크기에 맞춰 증가하기 때문에 생각보다 메모리를 적게 쓰게 되지는 않습니다.

Dictionary의 상세 구현은 CPython 코드의 주석에 잘 설명되어 있으니 참고해 주세요!

Dictionary in Python 3.7

Dictionary before Python 3.7

Dictionary in Python 3.7+

References

Written by Lenny Lee

No responses yet