[python] 사전에서 순서가 임의 인 이유는 무엇입니까?

이것은 파이썬 3.41 A에 대한 응답 입니다.

다른 사람들도 옳습니다. 명령에 의존하지 마십시오. 존재하는 척조차하지 마십시오.

즉, 신뢰할 수있는 한 가지가 있습니다.

list(myset) == list(myset)

즉, 순서가 안정적 입니다.

지각 된 순서 가있는 이유를 이해 하려면 몇 가지 사항을 이해해야합니다.

• 파이썬은 해시 세트를 사용 합니다 .

• CPython의 해시 세트가 메모리에 저장되는 방법

• 숫자가 해시되는 방법

상단에서 :

해시 세트 정말 빠른 검색 시간으로 임의 데이터를 저장하는 방법이다.

백업 배열이 있습니다.

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

우리는 특수 더미 객체를 무시할 것입니다.이 더미는 제거하기가 쉽지 않기 때문에 제거하기가 더 쉽습니다.

정말 빠른 조회를 위해 객체에서 해시를 계산하는 마술을합니다. 유일한 규칙은 동일한 두 객체가 동일한 해시를 갖는 것입니다. 그러나 두 객체에 동일한 해시가 있으면 동일하지 않을 수 있습니다.

그런 다음 배열 길이로 모듈러스를 가져와 인덱스를 만듭니다.

hash(4) % len(storage) = index 2

따라서 요소에 빠르게 액세스 할 수 있습니다.

해시는 다음과 같이 이야기의 대부분을하다 hash(n) % len(storage)와 hash(m) % len(storage)같은 숫자가 발생할 수 있습니다. 이 경우 여러 가지 다른 전략이 충돌을 시도하고 해결할 수 있습니다. CPython은 복잡한 작업을 수행하기 전에 “선형 프로빙”을 9 번 사용하므로 다른 곳을보기 전에 슬롯 왼쪽 에서 최대 9 개의 위치를 ​​찾습니다.

CPython의 해시 세트는 다음과 같이 저장됩니다.

• 해시 세트는 2/3 이하일 수 없습니다 . 요소가 20 개이고 백업 배열의 길이가 30 개이면 백업 저장소의 크기가 더 커집니다. 작은 백업 저장소와의 충돌이 자주 발생하고 충돌로 인해 모든 속도가 느려지기 때문입니다.

• 백업 저장소는 2의 거듭 제곱으로 크기가 조정되는 큰 세트 (50k 요소)를 제외하고 8에서 시작하여 4의 거듭 제곱으로 크기가 조정됩니다 (8, 32, 128, …).

따라서 배열을 만들 때 백업 저장소의 길이는 8입니다. 5가 가득 차서 요소를 추가하면 간단히 6 개의 요소가 포함됩니다. 6 > ²⁄₃·8이렇게하면 크기 조정이 시작되고 백업 저장소는 크기가 4 배가됩니다.

마지막으로 숫자를 hash(n)반환 n합니다 ( -1특별한 제외 ).

첫 번째를 보자.

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)은 10이므로 모든 항목이 추가 된 후 백업 저장소는 15 (+1) 이상 입니다. 2의 관련 거듭 제곱은 32입니다. 따라서 백업 저장소는 다음과 같습니다.

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

우리는

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

따라서 다음과 같이 삽입하십시오.

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

그래서 우리는 같은 순서를 기대할 것입니다

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

다른 곳에서 시작하지 않는 1 또는 33으로. 이것은 선형 프로빙을 사용하므로 다음 중 하나를 갖습니다.

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

또는

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

1이 이미 있었기 때문에 33이 변위 된 것으로 예상 할 수 있지만 세트가 빌드 될 때 발생하는 크기 조정으로 인해 실제로는 그렇지 않습니다. 세트가 재구성 될 때마다 이미 추가 된 항목이 효과적으로 재정렬됩니다.

지금 당신은 이유를 볼 수 있습니다

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

순서대로있을 수 있습니다. 14 개의 요소가 있으므로 백업 저장소는 21 + 1 이상이며 이는 32를 의미합니다.

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

처음 13 개 슬롯에서 1 ~ 13 개의 해시. 20은 슬롯 20에 들어갑니다.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55는 슬롯 hash(55) % 3223에 들어갑니다 .

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

대신 50을 선택하면

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

그리고 보라.

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop 그것은 단순히 사물의 모양에 의해 구현됩니다 : 그것은 목록을 가로 지르고 첫 번째를 팝합니다.

이것은 모든 구현 세부 사항입니다.

답변

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

33 & (ht->num_buckets - 1) = 1

'0b100001' & '0b111'= '0b1' # 1 the index of 33

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value