Перебор словаря возвращает ключи в отсортированном порядке

Question

У меня есть вопрос о том, как Python обрабатывает данные в словарях. Допустим, у меня есть простой словарь с числом в качестве ключа и числом в качестве значения, как показано ниже:

a = { 5: 3, 20: 1, 1: 1, 5: 2, 100: 3, 11: 6,
     14: 1, 15: 2, 16: 4, 17: 2, 25: 1, 19: 1 }

Я хочу перебрать этот словарь и распечатать ключи. Каждый раз, когда я перебираю словарь (как показано ниже), он печатает ключи в порядке возрастания.

Это то, что я хочу сделать, но мне было интересно, насколько я знаю, почему это происходит? Это автоматически сортирует это в возрастающем порядке каждый раз? Как вы можете видеть из словаря выше, ключи явно не в порядке возрастания, но вывод ниже печатает их в порядке возрастания.

Я просто пытаюсь получить четкое понимание, любая помощь будет принята с благодарностью. Спасибо

пример

for i in a:
    print i

Выход:

1
5
11
14
15
16
17
19
20
25
100

Answer 1

Целые числа в словаре не всегда упорядочены по ключу:

a = {2:0, 9:0}
print a.keys()  # [9, 2]

Словари Python - это хеш-таблицы, представляющие собой особый вид массива, в котором индекс ячейки, в которой хранится значение, определяется с помощью специальной функции (назовем ее hash функция) на ключ. Таким образом, если вы хотите получить значение для определенного ключа, вы можете снова вычислить hash функция ключа, которая будет возвращать тот же результат, что и раньше, получая индекс, в котором хранится значение.

hash Функция преобразует большинство типов данных в целое число:

print hash(1)             # 1
print hash('hello')       # 840651671246116861
print hash((2,3))         # 3713082714463740756

Каждый тип может определять свой собственный способ вычисления хеша и int обычно возвращает себя:

print hash(1)             # 1
print hash(20)            # 20
print hash(1000)          # 1000

Как вы можете видеть, числа скоро станут большими, и мы не хотим иметь массив с 840651671246116861 ячейками, чтобы сохранить строку hello, Чтобы избежать проблемы, мы можем создать массив с n элементы, а затем использовать оставшуюся часть хеша, разделенную на n в качестве индекса.

Например, если мы хотим найти индекс для hello в массиве из 8 элементов:

print hash('hello') % 8   # 5

Таким образом, наш словарь будет знать, что значение для ключа hello в индексе 8. Вот как словари реализованы.

Итак, почему {2:0, 9:0} не заказывается на ключи? Это потому, что словари python создаются с 8 элементами и растут по мере необходимости (подробнее об этом здесь).

Давайте вычислим индекс для хранения данных, имеющих key = 2 а также key = 9 в словаре с n = 8:

print hash(2) % 8         # 2  [hash(2) = 2 and 2 % 8 = 2]
print hash(9) % 8         # 1  [hash(9) = 9 and 9 % 8 = 1]

Это означает, что массив, содержащий данные словаря, будет:

| index | key | value |
|-------|-----|-------|
|   0   |     |       |
|   1   |  9  |   0   |
|   2   |  2  |   0   |
|   3   |     |       |
|   4   |     |       |
|   5   |     |       |
|   6   |     |       |
|   7   |     |       |

При его итерации порядок будет тот, который представлен в этом представлении, поэтому 9 будет раньше 2,

Вы можете прочитать больше по теме здесь.

Answer 2

Если вы хотите знать, почему Python всегда размещает ключи в отсортированном порядке... ответ - нет.

Если вы хотите знать, почему какая-то конкретная версия какой-то конкретной реализации Python размещает ваши конкретные ключи в отсортированном порядке, единственным реальным ответом на этот вопрос является исходный код.

Для CPython (реализация, которую вы, вероятно, используете, если вы не знаете, какую вы используете), источник находится в Objects/dictobject.c, Это резко изменилось в 3.4, а до этого в... я думаю 2.6/3.2, и в истории произошли некоторые другие менее драматические изменения. Таким образом, вы должны будете обязательно найти версию, которая вам действительно нужна. Для версии 3.4 источник находится по адресу http://hg.python.org/cpython/file/3.4/Objects/dictobject.c. Это на C, но есть несколько замечательных комментариев, объясняющих, что он делает. Если вы действительно хотите изучить его, вы можете даже портировать его на Python и запустить его под pdb,

Одна из ключевых проблем, которая может быть неочевидна при чтении кода, если вы не понимаете хеш-таблицы, заключается в том, что здесь есть два "совпадения", а не одно. Во-первых, в некоторых версиях CPython, когда дается небольшой заговор, созданный сразу, ключи будут упорядочены по их значениям хеш-функции. Во-вторых, до сих пор во всех версиях CPython маленькие целые числа хэшируются сами по себе, поэтому, в отличие от почти любого другого типа, "по порядку по значению хеша" также означает "по порядку по значению".

Answer 3

каждый раз, когда я перебираю словарь (как показано ниже), он печатает ключи в порядке возрастания.

Это просто случайно. Словари представляют собой неупорядоченную коллекцию объектов, доступных по ключам.

Здесь нет "автосортировки" или какой-либо другой сортировки.

Подумайте об этом на одну секунду - весь смысл установки ваших собственных ключей в том, чтобы их можно было извлечь из них, поэтому для ключей не важно иметь "порядок" - дело в том, что вы знаете, как обращаться к каждый объект, потому что вы устанавливаете его ключ. Это позволяет очень быстро получить объект; потому что его очень легко найти. Двойных ключей нет, поэтому внутри словарь можно хранить оптимизированным способом для быстрого доступа.

Сравните это со списком, который заказан (и его порядок гарантирован). В списке цель состоит в том, чтобы извлечь объект по его ссылке в списке, то есть по его положению относительно других объектов в списке. Поэтому имеет смысл поддерживать порядок.

Кортежи похожи на списки тем, что они упорядочены. Одно из различий между кортежами и списками заключается в том, что когда-то установленные кортежи не могут быть изменены (вы не можете "увеличить" или "сжать" кортеж). Чтобы изменить кортеж, вы должны создать еще один кортеж. Таким образом, чтобы "вырастить" кортеж, добавьте два кортежа вместе, чтобы получить третий, другой кортеж. Оригинальные два кортежа остаются без изменений.

Если вы хотите узнать технические детали реализации словарей и то, как они работают "под капотом", у этого вопроса есть отличный ответ со всей различной информацией.

Answer 4

Док говорит:

Лучше всего рассматривать словарь как неупорядоченный набор пар ключ: значение с требованием, чтобы ключи были уникальными

В отличие от списков или кортежей Python, пары ключ и значение в объектах dict расположены не в определенном порядке. Хотя пары ключ-значение находятся в определенном порядке, когда вы создаете экземпляр словаря, просто вызвав dict, вы можете увидеть, что они хранятся не в том же порядке. Тогда, если вы хотите отсортировать их, просто используйте встроенный метод сортировки