[python] dictionary는 만능이다!
Dictionary!
Dictionary는 파이썬 생태계에서 매우매우 중요한 자료구조입니다.
유연하고, 빠르며, 사용하기 쉽습니다.
그야말로 만능에 가까운 자료구조입니다.
1년 주기로 발표되는 Minor 버전마다 계속해서 성능의 향상이 이루어지고 있을 정도로
Python core 개발진과 커뮤니티가 모두 많은 관심을 보이는 것입니다.
주요 특징은 다음과 같습니다.
해시 테이블을 활용합니다.
대부분의 동작에서 평균적으로 O(1)의 시간복잡도를 가집니다.
불변 객체라면 모두 Key로 넣을 수 있습니다.
입력 순서를 보장합니다.
Java에도 유사한 역할을 하는 HashMap이라는 자료구조가 있으나,
위의 3, 4번 특징은 갖지 못하기에, 유연한 사용은 조금 힘든 편입니다.
또한 해시 테이블이 아닌 체이닝 방식으로, 세부적인 구조는 조금 다릅니다.
1. Hash Table 방식
딕셔너리는 해시 테이블 방식으로 구현되어 있습니다.
키로 들어온 값을 고유한 해시 값을 생성하여 인덱스로 활용합니다.
일반적으로 list, tuple은 list[1]처럼 정수형 인덱스로 값에 접근합니다.
name이라는 string 값을 key로 넣는다고 하면,
해시 함수를 활용해 5라는 정수 값으로 변환하고 이를 인덱스로 넣는 것입니다.
내부적으로는 다른 시퀀스 자료형에 접근하는 것과 같이 정수형 인덱스로 접근한다는 것이죠.
그렇기 때문에 다른 시퀀스 자료형에 인덱스로 접근하는 것과 같이 평균적으로 O(1)이란 시간 복잡도를 가집니다.
다만, 해시 충돌이라는 문제를 고려해야 하기 때문에 평균적으로 O(1)이라 표현합니다.
해시 충돌?
두 개의 서로 다른 키 k1, k2가 해시 함수로 변환된 값이 서로 같을 때, 해시 충돌이 일어납니다.
충돌이 발생하면 해시 테이블의 시간 복잡도는 O(1)에서 O(n)으로 증가할 수 있습니다.
Python의 딕셔너리는 오픈 어드레싱(Open Addressing) 방식을 사용하여 충돌을 해결하며,
다음과 같은 방식으로 성능을 유지합니다.
충돌이 발생할 경우, 인접한 빈 슬롯을 찾아 이동(프로빙)하여 데이터를 저장합니다.
이는 충돌이 심하지 않다면 여전히 O(1)에 가까운 성능을 유지하도록 설계되었습니다.
또한 입력되는 값의 수에 따라 동적으로 테이블의 크기를 조정합니다.
따라서, 많은 값이 입력되어도 평균적으로 O(1)에 가까운 성능을 내는 것이죠.
2. 대부분의 동작에서 평균 O(1)의 시간 복잡도
| 메서드/연산 | 설명 | 평균 시간 복잡도 | 최악 시간 복잡도 |
|---|---|---|---|
d[key] (조회) | 키에 해당하는 값을 반환 | O(1) | O(n) |
d[key] = value (삽입) | 키-값 쌍을 삽입하거나 값을 업데이트 | O(1) | O(n) |
del d[key] (삭제) | 키-값 쌍을 삭제 | O(1) | O(n) |
key in d | 키가 딕셔너리에 있는지 확인 | O(1) | O(n) |
len(d) | 딕셔너리의 키-값 쌍 개수 반환 | O(1) | O(1) |
d.clear() | 모든 키-값 쌍 제거 | O(n) | O(n) |
d.keys() | 키 뷰 반환 | O(1) | O(n) |
d.values() | 값 뷰 반환 | O(1) | O(n) |
d.items() | 키-값 뷰 반환 | O(1) | O(n) |
d.pop(key) | 키-값 쌍을 삭제하고 값을 반환 | O(1) | O(n) |
d.popitem() | 마지막 키-값 쌍을 삭제하고 반환 (Python 3.7+) | O(1) | O(1) |
d.get(key) | 키에 해당하는 값을 반환 (없으면 기본값 반환) | O(1) | O(n) |
d.update([other]) | 다른 딕셔너리를 병합하거나 키-값 삽입 | O(k) (k는 삽입 개수) | O(k) |
다만, 위에서 말했던 해시 충돌에 대한 대책 덕분에
실제로 O(n)이 걸릴 일은 사실상 없다고 봐도 무방합니다.
3. 불변 객체라면 모두 Key로 넣을 수 있습니다.
파이썬은 사실상 모든 객체가 1급 객체 취급이기 때문에 가능한 것이죠.
Key로 넣을 수 있는 값은 다음과 같습니다.
int, str, float 등등, 수 많은 기본 자료형
tuple
함수(메서드)
클래스에 대한 참조
List와 Dict 타입은 가변 객체이므로 넣을 수 없습니다!
List와 Dict 모두 1 버전에서 해시하여 dict의 키로 넣었을 때,
만약 해당 객체가 변형되어 2 버전이 되어버리면,
해당 객체를 해싱했을 때 같은 해시 값이 나오지 않기 때문입니다.
- 입력 순서를 보장합니다.
입력 순서 보장은, Python 3.6 버전에서 구현이 되었으나,
공식적으로 확정된 것은 3.7 버전 부터입니다!
애초에 해시 테이블이라 순차적 인덱스로 접근하는 것도 아닌데 이게 왜 필요한가 싶지만,
순차적 접근이 필요한 때, 별도의 정렬이 필요없게 됩니다.
Json 형태로 파싱될 때, 입력순서가 보장된다면, 보다 가독성 높은 Json 파일로 변환할 수 있습니다.
Print를 통해 값을 출력했을 때 가독성이 보장됩니다.
이러한 발전 덕에 기존에 사용되던 OrderedDict 타입을 굳이 쓸 필요가 없게 되었습니다!
정리하자면, 정렬 용이, 데이터 포맷 변환 용이, 디버깅 용이, 코드 간소화 등의 장점이 생긴 것이죠!
요약
Python의 dictionary는 유연하고 빠르며, 사용하기 쉬운 만능 자료구조로, Python 생태계에서 매우 중요한 역할을 합니다.
- 해시 테이블 기반:
- 키를 해시하여 고유한 인덱스를 생성하고, 이를 통해 빠르게 값에 접근.
- 평균 O(1)의 시간 복잡도를 가지며, 충돌이 발생할 경우에도 최적화된 방식(Open Addressing)으로 성능 유지.
- 대부분의 동작에서 평균 O(1):
- 조회, 삽입, 삭제 등 대부분의 연산이 평균적으로 O(1)이며, 충돌이 거의 없으므로 O(n)은 사실상 발생하지 않음.
- 불변 객체만 키로 사용 가능:
int,str,float,tuple, 함수, 클래스 등 해시 가능한 객체를 키로 사용할 수 있음.list,dict와 같은 가변 객체는 키로 사용할 수 없음(변경 시 해시 값 불일치 문제).
- 입력 순서 보장:
- Python 3.7부터 입력 순서를 공식적으로 보장.
- 정렬, JSON 변환, 디버깅 등에서 데이터 가독성과 사용성을 향상.
장점
효율성: 평균 O(1)의 성능.
유연성: 다양한 객체를 키로 사용 가능.
가독성: 입력 순서 유지로 디버깅과 데이터 변환이 용이.
코드 간소화: 추가 데이터 구조 사용 없이 순차 접근 지원.
Python의 dict는 계속해서 최적화되고 있으며, JSON 변환, 데이터 정렬, 디버깅 등 다방면에서 활용도가 매우 높은 자료구조입니다.