Как работает распределение памяти в python словарях?

Question

Я хочу понять, как работает распределение памяти в python при добавлении новых данных в словарь. В приведенном ниже коде я ждал, что все новые добавленные данные будут собраны в конце, однако этого не происходит.

repetitions = {}
for item in new_deltas:
    list_aux = []
    if float(item[1]) <= 30:
        if float(item[0]) in repetitions:
            aux = repetitions[float(item[0])]
            aux.append(item[1])
            repetitions[float(item[0])] = aux
        else:
            list_aux.append(item[1])
            repetitions[float(item[0])] = list_aux
    print(repetitions)

Результаты, которые я получил, как показано ниже. Таким образом, я хотел бы понять, почему новые добавленные данные не добавляются в конец стека, они добавляются в середине.

Мои входные данные:

new_deltas = [[1.452, 3.292182683944702], [1.449, 4.7438647747039795], [1.494, 6.192960977554321], [1.429, 7.686920166015625]] 

Вывод строки печати:

{1.452: [3.292182683944702]}
{1.452: [3.292182683944702], 1.449: [4.7438647747039795]}
{1.452: [3.292182683944702], 1.494: [6.192960977554321], 1.449: [4.7438647747039795]}
{1.429: [7.686920166015625], 1.452: [3.292182683944702], 1.494: [6.192960977554321], 1.449: [4.7438647747039795]}

Answer 1

Краткий ответ

Dicts реализованы в виде ha sh таблиц , а не стеков.

Без дополнительных мер, которые приводят к шифрованию порядок ключей

Ха sh Таблицы

До Python 3.6 порядок в словаре был рандомизирован функцией ha sh. Грубо говоря, вот как это работает:

d = {}        # Make a new dictionary
              # Internally 8 buckets are formed:
              #    [ [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ]
d['a'] = 10   # hash('a') % s gives perhaps bucket 5:
              #    [ [ ] [ ] [ ] [ ] [ ] [('a', 10)] [ ] [ ] ]
d['b'] = 20   # hash('b') % s gives perhaps bucket 2:
              #    [ [ ] [ ] [('b', 20)] [ ] [ ] [('a', 10)] [ ] [ ] ]

Итак, вы можете видеть, что упорядочение этого dict поставит 'b' перед 'a', потому что функция ha sh помещает 'b' в более раннее ведро. .

Более новые таблицы ha sh, которые помнят порядок вставки

Начиная с Python 3.6, также был добавлен стек. См. Это подтверждение концепции для лучшего понимания того, как это работает.

Соответственно, dicts начал запоминать порядок вставки, и это поведение стало гарантированным в Python 3.7 и более поздних версиях.

Используйте OrderedDict в более старых Python реализациях

До версии 3.7 вы можете использовать collection.OrderedDict () , чтобы получить тот же эффект.

Более глубокое погружение

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

Answer 2

До Python 3.6 словари не заказывались (подробнее об этом см. этот поток stackoverflow). Если вы используете Python 3.6 или ниже (в CPython 3.6 тот факт, что порядок поддерживается, является подробностью реализации, но с Python 3.7 он стал языковой функцией), вы можете использовать OrderedDict , чтобы получить желаемое поведение.

Например, вы можете изменить начало фрагмента кода следующим образом:

from collections import OrderedDict
repetitions = OrderedDict()
...