사전 및 집합의 순서가 임의인 이유는 무엇입니까?

사전 및 집합의 순서가 임의인 이유는 무엇입니까?

나는 사전이나 파이썬 세트 위에 루프하는 것이 어떻게 '임의' 순서로 이루어지는지 이해할 수 없습니다.

제 말은, 프로그래밍 언어이기 때문에 언어의 모든 것이 100% 결정되어야 한다는 것입니다, 그렇죠?Python은 사전이나 세트의 어떤 부분을 선택할지를 결정하는 일종의 알고리즘을 가지고 있어야 합니다. 첫 번째, 두 번째 등등.

제가 무엇을 빠뜨리고 있나요?

참고: 이 답변은 다음을 구현하기 전에 작성되었습니다.dictPython 3.6에서 유형이 변경되었습니다.이 답변의 구현 세부 정보 대부분은 여전히 적용되지만 사전의 키 나열 순서는 더 이상 해시 값에 의해 결정되지 않습니다.설정된 구현은 변경되지 않은 상태로 유지됩니다.

순서는 임의가 아니지만 사전 또는 집합의 삽입 및 삭제 기록과 특정 Python 구현에 따라 달라집니다.이 답변의 나머지 부분인 '사전'의 경우 'set'도 읽을 수 있습니다. 세트는 키만 있고 값이 없는 사전으로 구현됩니다.

키는 해시되고 해시 값은 동적 테이블의 슬롯에 할당됩니다(필요에 따라 증가하거나 축소할 수 있음).그리고 그 매핑 과정은 충돌로 이어질 수 있습니다. 즉, 이미 존재하는 것을 기준으로 다음 슬롯에 키를 삽입해야 합니다.

내용을 나열하면 슬롯에 루프가 발생하므로 키는 테이블에 현재 있는 순서대로 나열됩니다.

열쇠를 가져가세요.'foo'그리고.'bar'예를 들어 테이블 크기를 8개의 슬롯으로 가정합니다. 2 Python 2.에서는hash('foo')이라-4177197833195190597,hash('bar')이라327024216814240868모듈로 8. 즉, 이 두 개의 키가 슬롯 3과 4에 슬롯되어 있습니다.

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

목록 순서를 알려줍니다.

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

한 모든 슬롯이 있습니다. 슬롯 3이 되고, 그 슬롯 4가 됩니다. 따라서 3번 슬롯 4번 슬롯이 됩니다. 테이블 위에 루프하면 슬롯 3이 나열되고, 그 다음 슬롯 4가 나열됩니다.'foo'앞에나됨 앞에 .'bar'.

bar그리고.baz을 두고 슬롯에 값을 있습니다.4:

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

이제 순서는 어떤 키가 먼저 슬롯에 삽입되었는지에 따라 달라집니다. 두 번째 키는 다음 슬롯으로 이동해야 합니다.

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

하나 또는 다른 키가 먼저 슬롯에 삽입되었기 때문에 테이블 순서가 다릅니다.

CPython(가장 일반적으로 사용되는 Python 구현체)에서 사용되는 기본 구조의 기술 이름은 오픈 어드레싱을 사용하는 해시 테이블입니다.C가 궁금하고 C를 충분히 이해하고 있다면 모든 (잘 문서화된) 세부 사항에 대해 C 구현을 살펴보십시오.또한 Brandon Rodes의 Pycon 2010 프레젠테이션을 볼 수 있습니다. Cython이 어떻게dictAndrew Kuchling이 작성한 구현에 대한 장이 포함된 Beautiful Code의 복사본을 선택하거나 작업합니다.

Python 3.3에서는 랜덤 해시 시드도 사용되므로 특정 유형의 서비스 거부를 방지하기 위해 해시 충돌을 예측할 수 없습니다(공격자가 대량 해시 충돌을 일으켜 Python 서버를 응답하지 않게 만드는 경우).이는 주어진 사전 또는 집합의 순서가 현재 Python 호출에 대한 랜덤 해시 시드에도 의존한다는 것을 의미합니다.

다른 구현은 문서화된 Python 인터페이스를 충족하는 한 사전에 다른 구조를 자유롭게 사용할 수 있지만, 지금까지의 모든 구현은 해시 테이블의 변형을 사용한다고 생각합니다.

Cython 3.6은 새로운 기능을 도입했습니다. dict삽입 순서를 유지하고 부팅 속도와 메모리 효율성이 향상된 구현입니다.각 행이 저장된 해시 값과 키 및 값 개체를 참조하는 큰 희소 테이블을 유지하는 대신, 새로운 구현은 별도의 '밀도' 테이블(실제 키-값 쌍만큼의 행만 포함하는 테이블)에서 인덱스만 참조하는 더 작은 해시 어레이를 추가합니다.그리고 포함된 항목을 순서대로 나열하는 것은 조밀한 테이블입니다.자세한 내용은 Python-Dev에 대한 제안서를 참조하십시오.Python 3.6에서는 이것이 구현 세부사항으로 간주되지만 Python-the-language에서는 다른 구현이 순서를 유지해야 한다고 지정하지 않습니다.이것은 Python 3.7에서 변경되었으며, 여기서 이 세부 정보는 언어 사양으로 승격되었습니다. 모든 구현이 Python 3.7 이상과 제대로 호환되려면 이 순서 보존 동작을 복사해야 합니다.그리고 명시적으로 말하자면, 이 변경 사항은 이미 '작은' 해시 구조를 가진 집합에는 적용되지 않습니다.

Python 2.7 이상 버전은 또한 다음과 같은 클래스를 제공합니다.dict키 순서를 기록하기 위해 추가 데이터 구조를 추가합니다.일부 속도와 추가 메모리의 가격으로 이 클래스는 키를 삽입한 순서를 기억합니다. 키, 값 또는 항목을 나열하면 그 순서대로 기억합니다.추가 사전에 저장된 이중 링크 목록을 사용하여 주문을 효율적으로 최신 상태로 유지합니다.아이디어를 요약한 Raymond Hettinger의 게시물을 참조하십시오. OrderedDict개체에는 재주문 가능한 것과 같은 다른 이점이 있습니다.

주문한 세트를 원한다면 패키지를 설치할 수 있습니다. Python 2.5 이상에서 작동합니다.

이것은 Python 3.41 A 세트가 복제로 닫히기 전에 대한 응답입니다.

---

다른 것들이 옳습니다. 순서에 의존하지 마세요.있는 척도 하지 마.

그렇긴 하지만, 여러분이 의지할 수 있는 한 가지가 있습니다.

list(myset) == list(myset)

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

---

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

• 파이썬은 해시 집합을 사용합니다.

• Cython의 해시 집합이 메모리에 저장되는 방법 및

• 숫자가 해시되는 방법

맨 위에서:

해시 집합은 검색 시간이 매우 빠른 랜덤 데이터를 저장하는 방법입니다.

백업 배열이 있습니다.

# 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)결과적으로 동일한 수가 될 수 있습니다.이 경우 여러 가지 다른 전략을 사용하여 충돌을 해결할 수 있습니다.Cython은 의사 무작위 프로빙을 수행하기 전에 "선형 프로빙"을 9번 사용하므로 다른 곳을 보기 전에 슬롯의 오른쪽을 최대 9개까지 봅니다.

Cython의 해시 집합은 다음과 같이 저장됩니다.

• 해시 집합은 60%를 초과할 수 없습니다(참고: 이 로드 팩터는 이전에 66%로 Python 3.7에서 감소했습니다).요소가 20개이고 백업 배열이 30개인 경우 백업 저장소의 크기가 더 커집니다.이는 소규모 백업 저장소와의 충돌이 더 자주 발생하고 충돌로 인해 모든 속도가 느려지기 때문입니다.

• 백업 저장소가 너무 꽉 차면 사용되지 않은 공간의 비율이 증가하도록 크기가 자동으로 조정됩니다(사용되지 않은 공간의 비율이 높을수록 해시 충돌을 처리할 때 슬롯을 찾는 속도가 빠름).소형 세트의 경우 스토리지의 크기가 4배, 대형 세트(50,000개 이상)의 경우 크기(소스)가 2배가 됩니다.

따라서 어레이를 생성할 때 백업 저장소의 길이는 8입니다.4가 차면 요소를 추가하면 5개의 요소가 포함됩니다. 5 > ³⁄₅·8따라서 크기 조정이 트리거되고 백업 저장소 크기가 32배로 4배 증가합니다.

>>> import sys
>>> s = set()
>>> for i in range(10):
...     print(len(s), sys.getsizeof(s))
...     s.add(i)
... 
0 216
1 216
2 216
3 216
4 216
5 728
6 728
7 728
8 728
9 728

마내침.hash(n)정당한 보답n단, 경우의수제(외정)경))는 )hash(-1)어느 쪽이 돌아옵니까?-2값이 다른 용도로 예약되어 있기 때문입니다.

---

첫 번째는 다음과 같습니다.

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

len(v_set)즉, 모든 항목이 추가된 후 백업 저장소가 최소 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번 슬롯에 들어갑니다.

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

55번 슬롯에 들어갑니다.hash(55) % 32, 23198, 23:

__  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기본 배열을 통과하고 첫 번째 요소를 팝업하여 사용하지 않는 슬롯과 "슬롯" 항목(제거된 요소에서 마커를 제거)을 건너뜁니다.

---

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

"임의"와 "비결정"은 다릅니다.

그들이 말하는 것은 "공용 인터페이스"에 있는 사전 반복 순서의 유용한 속성이 없다는 것입니다.현재 사전 반복을 구현하는 코드에 의해 완전히 결정되는 반복 순서의 속성이 거의 확실히 많이 있지만, 저자들은 사용할 수 있는 것으로 약속하지 않습니다.이를 통해 프로그램이 중단될 것을 걱정하지 않고 Python 버전 간(또는 다른 작동 조건에서 또는 런타임에 완전히 임의로) 이러한 속성을 변경할 수 있습니다.

따라서 사전 순서에 상관없이 모든 속성에 의존하는 프로그램을 작성하면 사전 유형을 사용하는 "계약을 깨는" 것이며, Python 개발자들은 테스트할 때 이것이 현재로서는 작동하는 것처럼 보일지라도 이것이 항상 작동할 것이라고 장담하지 않습니다.이것은 기본적으로 C의 "정의되지 않은 행동"에 의존하는 것과 같습니다.

이 질문에 대한 다른 대답들은 훌륭하고 잘 쓰여져 있습니다.OP는 제가 "어떻게 그들이 도망칠 수 있는지" 또는 "왜"라고 해석하는 "어떻게"를 묻습니다.

Python 문서에서는 Python 사전이 추상 데이터 유형 연관 배열을 구현하기 때문에 사전 순서가 지정되지 않는다고 합니다.소문대로

바인딩이 반환되는 순서는 임의일 수 있습니다.

다시 말해, 컴퓨터 과학 학생은 연상 배열이 정렬되어 있다고 가정할 수 없습니다.수학의 집합에 대해서도 마찬가지입니다.

집합의 요소가 나열되는 순서는 관련이 없습니다.

그리고 컴퓨터 과학

집합은 특정한 순서 없이 특정한 값을 저장할 수 있는 추상적인 데이터 유형입니다.

해시 테이블을 사용하여 사전을 구현하는 것은 순서에 관한 한 연관 배열과 동일한 속성을 가지고 있다는 점에서 흥미로운 구현 세부 사항입니다.

Python은 사전을 저장하기 위해 해시 테이블을 사용하므로 해시 테이블을 사용하는 사전이나 다른 반복 가능한 개체에는 순서가 없습니다.

그러나 해시 개체의 항목 인덱스와 관련하여 python은 다음 코드를 기반으로 인덱스를 계산합니다.

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

따라서, 정수의 해시 값은 정수^* 그 자체이기 때문에 인덱스는 다음과 같은 숫자를 기반으로 합니다.ht->num_buckets - 1는 상수)이므로 비트와이즈에 의해 계산된 지수입니다.(ht->num_buckets - 1)숫자^* 자체(해시인 -1의 경우 -2) 및 해시 값을 가진 다른 개체의 경우.

다니합고려를과 함께 다음의 를 생각해 .set해시 테이블을 사용하는 경우:

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

숫에대여하자에 대하여33다음이 있습니다.

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

사실은 다음과 같습니다.

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

이 경우의 참고 사항(ht->num_buckets - 1)이라8-1=7또는0b111.

리고그.1919:

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

리고그.333:

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

파이썬 해시 함수에 대한 자세한 내용은 파이썬 소스 코드에서 다음 인용문을 읽어보는 것이 좋습니다.

앞으로의 주요 세부 사항:대부분의 해시 체계는 무작위성을 시뮬레이션하는 의미에서 "좋은" 해시 함수를 갖는 것에 의존합니다.Python은 그렇지 않습니다. 가장 중요한 해시 함수(문자열 및 int)는 일반적인 경우에 매우 규칙적입니다.

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

이것이 꼭 나쁜 것만은 아닙니다!반대로 크기가 2**i인 테이블에서는 낮은 순서의 ibit를 초기 테이블 인덱스로 사용하는 것이 매우 빠르며, int 범위로 인덱싱된 딕트에 대한 충돌이 전혀 없습니다.키가 "연속" 문자열인 경우에도 마찬가지입니다.그래서 이것은 일반적인 경우에 무작위보다 더 나은 행동을 제공합니다. 그리고 그것은 매우 바람직합니다.

OTOH는 충돌이 발생할 때 해시 테이블의 연속 슬라이스를 채우는 경향이 있으므로 양호한 충돌 해결 전략이 중요합니다.합니다. 를 들어, " 해코의마비가것다취니도약합는오져시만트막지"를 . 예를 들어 목록을 고려하십시오.[i << 16 for i in range(20000)]열쇠 꾸러미로int는 자체 해시 코드이며 크기가 2**15인 딕트에 들어맞기 때문에 모든 해시 코드의 마지막 15비트는 모두 0입니다. 이들은 모두 동일한 테이블 인덱스에 매핑됩니다.

하지만 특이한 경우를 처리하는 것은 일반적인 경우를 지연시켜서는 안 되기 때문에 어쨌든 마지막 한 입만 먹습니다.나머지는 충돌 해결에 달려 있습니다.만약 우리가 보통 첫 번째 시도에서 우리가 찾고 있는 키를 찾는다면(그리고, 우리가 보통 찾는 것으로 밝혀졌습니다. 테이블 하중 계수가 2/3 이하로 유지되어 확률이 확실히 우리에게 유리합니다.) 초기 지수 계산을 훨씬 싸게 유지하는 것이 가장 합리적입니다.

---

_{클에대해의 입니다.int:}

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

언급URL : https://stackoverflow.com/questions/15479928/why-is-the-order-in-dictionaries-and-sets-arbitrary