Dlaczego kolejność w słownikach i zestawach jest dowolna?

Jest to bardziej odpowiedź na Python 3.41 a set zanim został zamknięty jako DUPLIKAT.

Inni mają rację: nie polegaj na rozkazie. Nawet nie udawaj, że istnieje.

To powiedziawszy, jest jedna rzecz, na której możesz polegać:

list(myset) == list(myset)

Czyli porządek jest stabilny .

Zrozumienie dlaczego istnieje postrzegany porządek wymaga zrozumienia kilku rzeczy:

• Że Python używa zestawy hash,

• W Jaki Sposób zestaw skrótów CPython jest przechowywany w pamięci i

• W Jaki Sposób liczby są haszowane

Od góry:

A hash set jest metodą przechowywania losowych danych z naprawdę szybkim czasem wyszukiwania.

Ma tablicę nośną:

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

Zignorujemy specjalny atrapa obiekt, który istnieje tylko po to, aby ułatwić usuwanie, ponieważ nie będziemy usuwać z tych zestawów.

W aby mieć naprawdę szybkie wyszukiwanie, wykonujesz magię, aby obliczyć hash z obiektu. Jedyną zasadą jest to, że dwa równe obiekty mają ten sam hash. (Ale jeśli dwa obiekty mają ten sam hash, mogą być nierówne.)

Następnie tworzymy indeks, biorąc moduł przez długość tablicy:

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

Hasze to tylko większość historii, ponieważ hash(n) % len(storage) i hash(m) % len(storage) mogą dać tę samą liczbę. W takim przypadku kilka różnych strategie mogą próbować rozwiązać konflikt. CPython używa" sondy liniowej " 9 razy przed zrobieniem skomplikowanych rzeczy, więc będzie wyglądać po lewej stronie gniazda do 9 miejsc, zanim zajrzy gdzie indziej.

Zestawy hashów Cpythona są przechowywane w następujący sposób:

• Zestaw skrótów może być nie więcej niż 2/3 pełnego . Jeśli jest 20 elementów, a tablica nośna ma długość 30 elementów, magazyn nośny zmieni rozmiar na większy. Dzieje się tak dlatego, że masz więcej kolizji często z małymi zapasami, a kolizje spowalniają wszystko.

• W skład zestawu wchodzą dwa zestawy: (8, 32, 128,...).

Więc kiedy tworzysz tablicę, magazyn kopii zapasowej ma długość 8. Gdy jest 5 pełnych i dodasz element, na krótko będzie zawierał 6 elementów. 6 > ²⁄₃·8 więc to powoduje zmianę rozmiaru, a backing store poczwórnie zmienia rozmiar 32.

Wreszcie, hash(n) po prostu zwraca n dla liczb (z wyjątkiem -1, które jest specjalne).

Spójrzmy więc na pierwszy:

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

len(v_set) jest 10, więc sklep jest co najmniej 15(+1) po dodaniu wszystkich pozycji . Odpowiednia moc 2 wynosi 32. Tak więc zaplecze to:

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

Mamy

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

Więc te wstawki jako:

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

Więc spodziewamy się takiego zamówienia jak

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

Z 1 lub 33, które nie są na start gdzie indziej. Będzie to miało zastosowanie sondy liniowej, więc będziemy mieli albo:

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

Lub

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

Możesz oczekiwać, że 33 będzie tym, który został przesunięty, ponieważ 1 już tam był, ale ze względu na zmianę rozmiaru, która dzieje się w trakcie budowania zestawu, tak naprawdę nie jest. Za każdym razem, gdy zestaw zostanie przebudowany, przedmioty już dodane są skutecznie zmieniane.

Teraz widzisz dlaczego

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

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

1 do 13 hash w pierwszych 13 slotach. 20 idzie w szczelinie 20.

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

55 idzie w slocie hash(55) % 32 czyli 23:

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

Gdybyśmy wybrali 50 zamiast tego, spodziewalibyśmy się

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

I oto:

{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 jest zaimplementowany po prostu wyglądem rzeczy: przemierza listę i wyskakuje pierwszy.

To wszystko szczegóły implementacji.

"arbitralny "to nie to samo co"nieokreślony".

Mówią, że nie ma użytecznych właściwości porządku iteracji słownika, które są "w interfejsie publicznym". Prawie na pewno istnieje wiele właściwości porządku iteracji, które są w pełni określone przez kod, który obecnie implementuje iterację słownika, ale autorzy nie obiecują ci ich jako czegoś, czego możesz użyć. Daje im to większą swobodę zmiany tych właściwości pomiędzy Pythonem wersje (lub nawet po prostu w różnych warunkach pracy, lub całkowicie losowo w czasie wykonywania) bez obawy, że program się zepsuje.

Tak więc, jeśli piszesz program, który zależy od jakiejkolwiek właściwości porządku słownika, to "łamiesz umowę" używania typu słownika, a deweloperzy Pythona nie obiecują, że to zawsze zadziała, nawet jeśli wydaje się działać na razie podczas testowania. To w zasadzie odpowiednik polegania na " undefined zachowanie " w C.

Inne odpowiedzi na to pytanie są doskonałe i dobrze napisane. OP pyta "Jak", które interpretuję jako" jak im się ujdzie na sucho " lub "dlaczego".

Dokumentacja Pythona mówi, że słowniki nie są uporządkowane, ponieważ słownik Pythona implementuje abstrakcyjny typ danych tablica asocjacyjna . Jak to mówią

Kolejność zwracania wiązań może być dowolna

Innymi słowy, student informatyki nie może Załóżmy, że tablica asocjacyjna jest uporządkowana. To samo dotyczy zbiorów w Matematyka

Kolejność w jakiej wymienione są elementy zbioru jest nieistotna

I Informatyka

Zbiór jest abstrakcyjnym typem danych, który może przechowywać pewne wartości, bez określonego porządku

Implementacja słownika za pomocą tabeli hash jest szczegółem implementacji , który jest interesujący, ponieważ ma te same właściwości jako tablice asocjacyjne, jeśli chodzi o porządek.

Użycie Pythona tabela hash do przechowywania słowników, więc nie ma kolejności w słownikach lub innych obiektach iteracyjnych, które używają tabeli hash.

Ale jeśli chodzi o indeksy elementów w obiekcie hash, python oblicza indeksy na podstawie następującego kodu wewnątrz hashtable.c:

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

Do tego, ponieważ wartość hashowa liczb całkowitych jest liczbą całkowitą^* indeks jest oparty na liczbie ({[9] } jest stałą), więc indeks obliczany przez bitowo-i między (ht->num_buckets - 1) a samą liczbą^* (oczekuj dla -1, którego hash to -2), oraz dla innych obiektów z ich wartością hash.

Rozważ następujący przykład z set, które używają hash-table:

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

Dla liczby 33 mamy:

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

Że właściwie to jest:

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

Uwaga w tym przypadku (ht->num_buckets - 1) jest 8-1=7 lub 0b111.

I dla 1919:

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

I dla 333:

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

Dla więcej szczegółów na temat funkcji hash Pythona warto przeczytać następujące cytaty z kodu źródłowego Pythona:

Główne subtelności przed nami: większość schematów hash zależy od posiadania "dobrego" hasha funkcja, w sensie symulowania losowości. Python nie: jego najbardziej ważne funkcje hash (dla ciągów i ints) są bardzo regularne przypadki:

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

To niekoniecznie jest złe! Przeciwnie, w tabeli wielkości 2 * * i, biorąc low-order i bitów jako początkowy indeks tabeli jest niezwykle szybki, a tam nie ma kolizji w ogóle dla dictów indeksowanych przez ciągły zakres int. To samo jest w przybliżeniu prawdziwe, gdy klucze są "kolejnymi" łańcuchami. Więc to daje lepsze niż przypadkowe zachowanie w typowych przypadkach, a to jest bardzo pożądane.

OTOH, gdy dochodzi do kolizji, tendencja do wypełniania sąsiadujących ze sobą plastrów tabela hash sprawia, że dobra strategia rozwiązywania kolizji ma kluczowe znaczenie. Biorąc tylko the last I bits of the hash kod jest również podatny na zagrożenia: na przykład rozważ lista [i << 16 for i in range(20000)] jako zestaw kluczy. ponieważ ints są własnymi kodami hashowymi, a to pasuje do dict o rozmiarze 2* * 15, ostatnie 15 bitów każdego kodu hashowego wynosi 0: Wszystkie mapują do tego samego indeksu tabeli.

Ale catering nietypowych przypadków nie powinien spowolnić tych zwykłych, więc po prostu wziąć ostatnie i tak się rozpadło. Reszta zależy od rozwiązania kolizji. Jeśli my Zwykle znajdujemy klucz, którego szukamy za pierwszą próbę (i okazuje Na zewnątrz, zwykle robimy - współczynnik obciążenia stołu jest utrzymywany poniżej 2/3, więc kursy są solidnie na naszą korzyść), wówczas najlepiej jest zachować początkowy indeks / align = "left" /

_{* Funkcja hash dla klasy int :}

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

Począwszy od Pythona 3.7 (i już w CPython 3.6), pozycje słownika pozostają w kolejności, w jakiej zostały wstawione .