В какой ситуации, если мы добавим упорядоченные числа в качестве ключей в хэш-таблицу, мы можем ожидать, что хэш будет упорядочен? [закрыто]

Поведение в Perl задокументировано в ключах :

Ключи хэша возвращаются в явно случайном порядке. Фактический случайный порядок может быть изменен в будущих версиях Perl, но он гарантированно будет в том же порядке, что и значения или создаваемые каждой функцией (при условии, что хэш не был изменен). Начиная с Perl 5.8.1 порядок может отличаться даже между различными запусками Perl по соображениям безопасности (см. Алгоритмическая сложность Атаки в perlsec).

Вы можете использовать Связь::IXHASH:

Этот модуль Perl реализует хэши Perl, которые сохраняют порядок, в котором были добавлены элементы хэша. Порядок не изменяется при изменении значений, соответствующих существующим ключам в IxHash. Элементы также могут быть установлены в любом произвольном порядке. Знакомые операции с массивом Perl также могут быть выполнены на IxHash.

Как указала Эмбер, коллекции .OrderedDict - это инструмент Python, гарантирующий сохранение порядка вставки.

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

>>> from random import sample
>>> dict.fromkeys(range(5)).keys()
[0, 1, 2, 3, 4]
>>> dict.fromkeys(range(25)).keys()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
>>> dict.fromkeys(range(0,25,2)).keys()
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
>>> dict.fromkeys(sorted(sample(range(50), 40))).keys()
[0, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 15, 16, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49]

Этот результат хрупок и не является гарантированным поведением. Он основан на следующих свойствах:

• ключи располагаются в соответствии с их хэш-значением по модулю размера dict (который начинается с 8)
• хэш-значения целых чисел являются самими целыми числами
• когда хэш-таблица заполнена на две трети, ее размер увеличивается в четыре раза (до 50 000, когда она затем начинает удваиваться), и существующие пары ключ/значение получают вставлено заново.

Вопрос: В какой ситуации, если мы добавим упорядоченные числа в качестве ключей в хэш-таблицу, мы можем ожидать, что хэш будет упорядочен?

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

• Первые пять элементов (8 * 2 // 3 ) должны быть отсортированы по модулю 8.
• Первые двадцать один элемент (32* 2 // 3 ) должны быть отсортированы по модулю 32.
• Первые восемьдесят пять элементов (128 * 2 // 3 ) должны быть отсортированы при использовании модуля 128.
• и так далее...

В коде:

def will_remain_sorted(seq):
    i, n = 0, 8
    while i < len(seq):
        i = n * 2 // 3
        if not sorted(seq[:i], key=lambda x: x%n) == seq[:i]:
            return False
        n *= 4 if n < 50000 else 2
    return True