Блог

Мы все знаем, что временная сложность вставки чего-либо в хэш-набор составляет в среднем O (1) . Тем не менее, я сосредоточен на наихудшем поведении. Я имею в виду, что должна существовать определенная последовательность интегральных ключей, которая может вызвать множество коллизий хэшей при последовательной вставке элементов, и это «наихудший случай», о котором я говорил.

Более конкретно:

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

Вот моя работа до сих пор

 from time import time
from math import log2


dummy = {}
elapsed = float('inf')
for k in range(20, 38):
    tic = time()
    dummy[1<<(1<<k)] = k
    elapsed, last = time() - tic, elapsed
    print(f"{k=}, {elapsed=:.4f}, {elapsed/last=:.4f}")
 

Приведенный выше состязательный ввод, по-видимому, приводит к временной сложности O (N ^ 2)… или, может быть, это O(N ^ 2 * ln (N))? Я не могу сказать.

 k=20, elapsed=0.0002, elapsed/last=0.0000
k=21, elapsed=0.0004, elapsed/last=2.1508
k=22, elapsed=0.0007, elapsed/last=1.8340
k=23, elapsed=0.0013, elapsed/last=1.7360
k=24, elapsed=0.0024, elapsed/last=1.9031
k=25, elapsed=0.0048, elapsed/last=1.9879
k=26, elapsed=0.0086, elapsed/last=1.8034
k=27, elapsed=0.0182, elapsed/last=2.1088
k=28, elapsed=0.0361, elapsed/last=1.9787
k=29, elapsed=0.0730, elapsed/last=2.0242
k=30, elapsed=0.1419, elapsed/last=1.9442
k=31, elapsed=0.2844, elapsed/last=2.0040
k=32, elapsed=0.5733, elapsed/last=2.0154
k=33, elapsed=1.1388, elapsed/last=1.9865
k=34, elapsed=3.5476, elapsed/last=3.1152
k=35, elapsed=8.3034, elapsed/last=2.3405
k=36, elapsed=16.0347, elapsed/last=1.9311
k=37, elapsed=35.1934, elapsed/last=2.1948
 

Для вставки Dict требуется O (n) сравнений элементов в худшем случае, где n — количество занятых записей в таблице. Кроме того, для отдельной вставки может потребоваться перестроение хэш-таблицы, что может привести к повторному столкновению каждого элемента с каждым другим элементом и к сравнению элементов O (n ^ 2).

Однако замедление ваших тестов вызывает не столкновение хэшей — ваши тесты тратят все свое время на построение и хеширование абсурдно огромных целых чисел. 1<<(1<<33) например, целое число размером в целый гигабайт.

Довольно легко создать состязательный ввод. Например,

 In [4]: for i in range(20): 
   ...:     print(hash(i*(2**61-1))) 
   ...:                                                                                                                                                                                                                          
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
 

вы можете просто взять кратные 2**61-1 .