사전의 순서는 왜 임의적인가?

사전의 순서는 왜 임의적인가?

---

사전을 반복하거나 파이썬으로 설정하는 것이 '임의'순서에 의해 어떻게 수행되는지 이해하지 못합니다.

내 말은, 그것은 프로그래밍 언어이므로 언어의 모든 것이 100 % 결정되어야합니까? 파이썬에는 사전이나 세트의 어느 부분이 1, 2 등으로 선택되는지를 결정하는 일종의 알고리즘이 있어야합니다.

내가 무엇을 놓치고 있습니까?

---

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

키가 해시되고 해시 값이 동적 테이블의 슬롯에 할당됩니다 (필요에 따라 증가 또는 축소 될 수 있음). 그리고 매핑 프로세스는 충돌을 일으킬 수 있습니다. 즉, 이미 존재하는 것을 기반으로 다음 슬롯 에 키를 슬롯해야합니다 .

내용을 나열하면 슬롯에 걸쳐 반복되므로 키가 현재 테이블 에있는 순서대로 나열됩니다 .

열쇠를 가지고 'foo'와 'bar', 예를 들어, 테이블의 크기는 8 개 슬롯 가정 할 수 있습니다. 파이썬 2.7 년 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 'foo'를 나열 하므로 앞에 나열됩니다 'bar'.

bar그리고 baz, 그러나, 동일한 슬롯에 매핑 떨어져있어 정확히 8있는 해시 값을 가지고 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 구현 을 살펴보십시오 . CPython의 작동 방식 에 대한 Brandon Rhodes의 Pycon 2010 프레젠테이션을 보거나 Andrew Kuchling 이 작성한 구현에 대한 장을 포함하는 Beautiful Codedict 사본을 선택할 수도 있습니다.

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

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

CPython 3.6은 삽입 순서를 유지하고 부팅하는 데 더 빠르고 더 메모리 효율적인 새로운 dict 구현을 도입했습니다 . 각 행이 저장된 해시 값과 키 및 값 객체를 참조하는 큰 희소 테이블을 유지하기보다는 새로운 구현 은 밀도가 높은 테이블의 인덱스 만 참조 하는 더 작은 해시 배열 을 추가 합니다 (실제만큼 많은 행만 포함하는 것) 키-값 쌍), 포함 된 항목을 순서대로 나열하는 조밀 한 테이블입니다. 자세한 내용은 Python-Dev 제안을 참조하십시오 . 파이썬 3.6에서 이것은 구현 세부 사항으로 간주되며 , 파이썬 언어는 다른 구현이 순서를 유지해야한다고 지정하지 않습니다. 이것은 파이썬 3.7에서 변경되었습니다.이 세부 사항은언어 사양으로 상승 ; 모든 구현이 Python 3.7 이상과 올바르게 호환 되려면 이 순서 유지 동작을 복사 해야합니다 .

Python 2.7 이상은 키 순서를 기록하기 위해 추가 데이터 구조를 추가하는 하위 클래스 인 OrderedDictclass를 제공합니다 dict. 약간의 속도와 여분의 메모리 가격으로이 클래스는 키를 삽입 한 순서를 기억합니다. 키, 값 또는 항목을 나열하면 순서대로 나열됩니다. 주문을 효율적으로 최신 상태로 유지하기 위해 추가 사전에 저장된 이중 연결 목록을 사용합니다. Raymond Hettinger 의 글을 참조하여 아이디어를 요약하십시오 . 점을 유의 set유형은 여전히 정렬되지 않은 것입니다.

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

---

이것은 파이썬 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

We shall ignore the special dummy object, which exists only to make removes easier to deal with, because we won't be removing from these sets.

In order to have really fast lookup, you do some magic to calculate a hash from an object. The only rule is that two objects which are equal have the same hash. (But if two objects have the same hash they can be unequal.)

You then make in index by taking the modulus by the array length:

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

This makes it really fast to access elements.

Hashes are only most of the story, as hash(n) % len(storage) and hash(m) % len(storage) can result in the same number. In that case, several different strategies can try and resolve the conflict. CPython uses "linear probing" 9 times before doing complicated things, so it will look to the left of the slot for up to 9 places before looking elsewhere.

CPython's hash sets are stored like this:

• A hash set can be no more than 2/3 full. If there are 20 elements and the backing array is 30 elements long, the backing store will resize to be larger. This is because you get collisions more often with small backing stores, and collisions slow everything down.

• The backing store resizes in powers of 4, starting at 8, except for large sets (50k elements) which resize in powers of two: (8, 32, 128, ...).

So when you create an array the backing store is length 8. When it is 5 full and you add an element, it will briefly contain 6 elements. 6 > ²⁄₃·8 so this triggers a resize, and the backing store quadruples to size 32.

Finally, hash(n) just returns n for numbers (except -1 which is special).

---

So, let's look at the first one:

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

len(v_set) is 10, so the backing store is at least 15(+1) after all items have been added. The relevant power of 2 is 32. So the backing store is:

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

We have

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

so these insert as:

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

So we would expect an order like

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

with the 1 or 33 that isn't at the start somewhere else. This will use linear probing, so we will either have:

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

or

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

You might expect the 33 to be the one that's displaced because the 1 was already there, but due to the resizing that happens as the set is being built, this isn't actually the case. Every time the set gets rebuilt, the items already added are effectively reordered.

Now you can see why

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

might be in order. There are 14 elements, so the backing store is at least 21+1, which means 32:

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

1 to 13 hash in the first 13 slots. 20 goes in slot 20.

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

55 goes in slot hash(55) % 32 which is 23:

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

If we chose 50 instead, we'd expect

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

And lo and behold:

{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 is implemented quite simply by the looks of things: it traverses the list and pops the first one.

---

This is all implementation detail.

---

"Arbitrary" isn't the same thing as "non-determined".

What they're saying is that there are no useful properties of dictionary iteration order that are "in the public interface". There almost certainly are many properties of the iteration order that are fully determined by the code that currently implements dictionary iteration, but the authors aren't promising them to you as something you can use. This gives them more freedom to change these properties between Python versions (or even just in different operating conditions, or completely at random at runtime) without worrying that your program will break.

Thus if you write a program that depends on any property at all of dictionary order, then you are "breaking the contract" of using the dictionary type, and the Python developers are not promising that this will always work, even if it appears to work for now when you test it. It's basically the equivalent of relying on "undefined behaviour" in C.

---

The other answers to this question are excellent and well written. The OP asks "how" which I interpret as "how do they get away with" or "why".

The Python documentation says dictionaries are not ordered because the Python dictionary implements the abstract data type associative array. As they say

the order in which the bindings are returned may be arbitrary

In other words, a computer science student cannot assume that an associative array is ordered. The same is true for sets in math

the order in which the elements of a set are listed is irrelevant

and computer science

a set is an abstract data type that can store certain values, without any particular order

Implementing a dictionary using a hash table is an implementation detail that is interesting in that it has the same properties as associative arrays as far as order is concerned.

---

Python use hash table for storing the dictionaries, so there is no order in dictionaries or other iterable objects that use hash table.

But regarding the indices of items in a hash object, python calculate the indices based on following code within hashtable.c:

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

Therefor, as the hash value of integers is the integer itself^* the index is based on the number (ht->num_buckets - 1 is a constant) so the index calculated by Bitwise-and between (ht->num_buckets - 1) and the number itself^* (expect for -1 which it's hash is -2) , and for other objects with their hash value.

consider the following example with set that use hash-table :

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

For number 33 we have :

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

That actually it's :

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

Note in this case (ht->num_buckets - 1) is 8-1=7 or 0b111.

And for 1919 :

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

And for 333 :

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

For more details about python hash function its good to read the following quotes from python source code :

Major subtleties ahead: Most hash schemes depend on having a "good" hash function, in the sense of simulating randomness. Python doesn't: its most important hash functions (for strings and ints) are very regular in common cases:

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

This isn't necessarily bad! To the contrary, in a table of size 2**i, taking the low-order i bits as the initial table index is extremely fast, and there are no collisions at all for dicts indexed by a contiguous range of ints. The same is approximately true when keys are "consecutive" strings. So this gives better-than-random behavior in common cases, and that's very desirable.

OTOH, when collisions occur, the tendency to fill contiguous slices of the hash table makes a good collision resolution strategy crucial. Taking only the last i bits of the hash code is also vulnerable: for example, consider the list [i << 16 for i in range(20000)] as a set of keys. Since ints are their own hash codes, and this fits in a dict of size 2**15, the last 15 bits of every hash code are all 0: they all map to the same table index.

But catering to unusual cases should not slow the usual ones, so we just take the last i bits anyway. It's up to collision resolution to do the rest. If we usually find the key we're looking for on the first try (and, it turns out, we usually do -- the table load factor is kept under 2/3, so the odds are solidly in our favor), then it makes best sense to keep the initial index computation dirt cheap.

---

_{* The hash function for class int :}

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

---

Starting with Python 3.7 (and already in CPython 3.6), dictionary items stay in the order they were inserted.

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