뭐?python dict 사전 이 질서 가 있 습 니까?!

결론 이 너무 길 어서 시 리 즈 를 안 봐 요.
어떤 사람 이 나 에 게 왜 내 가 먼저 결론 을 내 렸 느 냐 고 물 었 다. 왜냐하면 아래 내용 이 너무 많아 서 보고 싶 지 않 고 결론 을 찾 고 싶 은 친구 들 이 너희들 을 도와 시간 을 절약 하 는 것 을 도와 주 었 다.
python 3.6 부터 dict 의 삽입 은 질서 가 있 습 니 다. 즉, 사전 전체 가 질서 가 있 습 니 다.이전 버 전, 예 를 들 어 python 2.7 은 사전 의 삽입 이 어 지 러 웠 습 니 다. 즉, a, b, c 를 삽입 하고 결 과 를 되 돌려 주 는 순 서 는 a, c, b 일 수 있 습 니 다.
글 목록

결론 ~ ~ 너무 길 어서 시 리 즈 를 안 봐 요 ~

배경

기초 지식

사전 이 무엇 입 니까?

사전 의 조회, 추가, 삭제 시간 복잡 도?

사전 의 키 를 반복 할 수 있 습 니까?

소스 코드 비밀 탐지

python 3.6 이전

python 3.6 이후

참고 자료

배경
오늘 은 하나의 항목 을 만 들 때 사전 을 사용 해 야 하지만 데 이 터 를 사전 key 가 삽입 한 순서에 따라 정렬 하려 고 합 니 다. python 2.7 의 경험 에 따라 사전 은 무질서 합 니 다. 그래서 자 료 를 찾 는 과정 에서 보물 package OderedDict 를 발 견 했 습 니 다. 말 그대로 질서 있 는 사전, 즉 삽입 순서에 따라 정렬 하 는 사전 입 니 다.이 걸 로 개 발 했 지.
그런데 우연 한 기회 에 이 걸 안 써 도 되 냐 고 물 어 봤 어 요. OderedDict import 라 는 물건 이 있어 서 너무 귀찮아 요.나 는 네가 귀 찮 으 면 python 을 쓰 지 않 는 것 이 좋 겠 다 고 생각 했다. 이렇게 간단 한 조작 은 너 에 게 적합 하지 않 지만 그래도 마음 을 가 라 앉 히 고 방 귀 를 참 으 며 그 를 도와 방법 을 생각해 봐 야 한다.그리고 나 서 나 는 python 의 dict 를 찾 아 보 았 다. 놀랍게도 python 3 의 사전 이 질서 가 있 는 것 을 발견 했다?!
이것 은 나 를 매우 의아 하 게 하여 다음 과 같은 소스 코드 의 비밀 을 탐지 하 게 하 였 다.
기초 지식
초보 자 들 에 게 기초 지식 을 보급 시 켜 라. 그러면 소스 코드 의 비밀 탐지 과정 에서 쉽게 이해 할 수 있 을 것 이다.
사전 이란 무엇 입 니까?
컴퓨터 과학 에서 관련 배열 (영어: Associative Array) 은 맵 (Map), 사전 (Dictionary) 과 같은 추상 적 인 데이터 구조 로 (키 키 키, 값 value) 와 유사 한 질서 있 는 쌍 을 포함한다.사전 은 가 변 용기 로 임의의 유형의 대상 을 저장 할 수 있다.사전 의 실현 은 해시 알고리즘 과 밀접 한 관 계 를 가진다. key 와 value 의 매 핑 은 바로 해시 (hash) 를 통 해 이 루어 진다.
사전 조회, 추가, 삭제 시간 복잡 도?
평균 시간 복잡 도 는 모두 O (1) 다.여기 서 언급 한 것 은 평균 시간 복잡 도 이 고 최 악의 상황 은 O (n) 이 며 나중에 원인 을 언급 할 것 이다.
사전 키 를 반복 할 수 있 습 니까?
이 질문 을 하 는 사람 은 사전 을 사용 해 본 적 이 없 는 것 같 습 니 다. 일반적으로 중복 하면 안 됩 니 다. 중복 할당 이 되면 뒤의 값 은 앞의 값 을 덮어 씁 니 다.왜 일반적으로 말 합 니까? 만약 에 나중에 어떤 신인 이 무슨 이상 한 개념 을 만들어 서 반복 할 수 있 기 때 문 입 니 다.
소스 코드 비밀 탐지
python 3.6 이전
사전 의 바 텀 실현 은 실제 적 으로 hash 표 입 니 다. 하나의 목록 으로 간단하게 이해 할 수 있 습 니 다. 목록 에 있 는 모든 요 소 는 하 쉬 값 (hash value), 키 (key) 와 값 (value) 세 가지 요 소 를 저장 합 니 다.

entries = [
	["--", "--", "--"],
	["--", "--", "--"],
	[hash_value_1, key1, value1],
	[hash_value_2, key2, value2]
]
#       

이 목록 을 통 해 모든 두 요소 이전에 약간의 공간 이 존재 한 다 는 것 을 알 수 있 습 니 다. 이런 공간 은 당연히 후속 으로 들 어 오 는 값 을 위해 준비 한 것 입 니 다. 어떻게 삽입 을 실현 하 는 지 살 펴 보 겠 습 니 다.

hash 함 수 를 통 해 key 를 hash 하여 hash value 를 얻 습 니 다.

mask 와 (and) 작업 을 합 니 다. mask 를 - 1 로 설정 하고 숫자 (index) 를 얻 습 니 다. 이것 이 바로 삽입 할 entries 해시 표 의 위치 입 니 다.

index 아래 표 시 된 위치 가 점용 되면 entries 의 key 가 삽입 할 key 와 같 는 지 판단 합 니 다.

키 가 같 으 면 키 가 존재 한 다 는 뜻 으로 value 값 을 업데이트 합 니 다.

key 가 같 지 않 으 면 hash conflict 를 나타 내 고 해시 충돌 이 발생 하면 남 은 빈 자 리 를 찾 을 때 까지 빈 자 리 를 계속 찾 습 니 다.따라서 모든 위치 가 가득 차 면 O (n) 의 시간 복잡 도가 전체 목록 을 옮 겨 다 녀 야 합 니 다.

우 리 는 코드 를 통 해 이 과정 을 이해 해 보 자.

my_dict = {
     }
#         ，key hello，value world
my_dict["hello"] = "world"

#         ，hash     
entries = [
    ["--", "--", "--"],
    ["--", "--", "--"],
    ["--", "--", "--"],
    ["--", "--", "--"]
]

hash_value = hash("hello")                 #      11111  ：         
index = hash_value & ( len(entries) - 1)   #   index      2

#        entries 
entries = [
    ["--", "--", "--"],
    ["--", "--", "--"],
    [11111, "hello", "world"], # index=2
    ["--", "--", "--"]
]

#            
my_dict["benz"] = "car"

hash_value = hash("benz")                 #       11111
index = hash_value & ( len(entries) - 1)  #   index        2

#        entries 
entries = [
    ["--", "--", "--"],
    ["--", "--", "--"],
    [11111, "hello", "world"], #   index=2        ， key   ，     hash conflict，      
    [11111, "benz", "car"]     #            
]

위의 원리 해석 과 코드 프로 세 스 설명 을 통 해 우 리 는 사전 의 삽입 과정 을 이미 알 게 되 었 다.서로 다른 키 가 hash 를 통 해 계 산 된 index 값 이 다 를 수 있 습 니 다. entries 에 삽 입 된 위치 가 다 를 수 있 기 때문에 사전 을 옮 겨 다 닐 때 필드 의 순 서 는 우리 가 삽입 한 순서 와 다 를 수 있 습 니 다.
python 3.6 이후
이전 사전 은 간단 한 hash table 만 있 었 습 니 다. 새로운 사전 은 hash table 뿐만 아니 라 indices 색인 표 도 보조 하여 사전 의 질 서 를 실현 할 수 있 었 습 니 다.
새로운 구조:

indices = [index0, index0, index0, None]
entries = [
    [hash_value_0, key0, value0],
    [hash_value_1, key1, value1],
    [hash_value_2, key2, value2],
    ["--", "--", "--"],
]

구체 적 인 실현 과정 에는 또 어떤 변화 가 있 습 니까?

hash 함 수 를 통 해 key 를 hash 하여 hash value 를 얻 습 니 다.

mask 와 (and) 작업 을 합 니 다. mask 를 - 1 로 설정 하고 숫자 (index) 를 얻 습 니 다. 이것 이 바로 삽입 할 indices 색인 표 의 위치 입 니 다.

index 를 받 은 후 indices 의 위치 에 대응 하지만 이 위 치 는 저 장 된 hash value 가 아니 라 저 장 된 번호 로 이 값 이 entries 에 있 는 위 치 를 나타 낸다.

충돌 이 없 으 면 entries 에 해당 하 는 요 소 를 삽입 합 니 다.

충돌 처 리 는 이전 과 일치 합 니 다.

다음은 코드 구현 에서 다시 한 번 보 겠 습 니 다.

my_dict = {
     }
#         ，key hello，value world
my_dict["hello"] = "world"

#         ，hash     
indices = [None, None, None, None]
entries = [
	["--", "--", "--"],
    ["--", "--", "--"],
    ["--", "--", "--"],
    ["--", "--", "--"]
]

hash_value = hash('hello')                #      11111
index = hash_value & ( len(indices) - 1)  #   index      2

#    indices index 2   ，   entries   
indices = [None, None, 0, None]
#   entries       
entries = [
    ["--", "--", "--"],
    ["--", "--", "--"],
    [11111, "hello", "world"],
    ["--", "--", "--"]
]

#            
my_dict["benz"] = "car"

hash_value = hash("benz")                 #      22222
index = hash_value & ( len(indices) - 1)  #   index       0

#    indices index 0   ，   entries   
indices = [1, None, 0, None]
#   entries     index  
entries = [
    [22222, "benz", "car"],
    ["--", "--", "--"],
    [11111, "hello", "world"],
    ["--", "--", "--"],
]

따라서 indices 표 가 있 는 상황 에서 전체 hash table 은 질서 있 게 변 할 수 있 습 니 다. 이것 은 왜 dict 가 질서 가 있 는 지 설명 합 니 다.
참고 자료
[Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered. https://mail.python.org/pipermail/python-dev/2016-September/146327.html