Поиск Сложность Hashtable в Hashtable?

Question

Скажем, у нас есть хэш-таблица размера m, и в каждом ведре мы храним хэш-таблицу размера p. Какова будет сложность поиска наихудшего случая/среднего размера?

Я склонен сказать, что, поскольку вычисление хеш-функции по-прежнему является атомарным, единственным худшим сценарием является случай, если значение находится в конце связанного списка в хэш-таблице размера p, поэтому O (n)?

Я понятия не имею, как рассчитать средний случай для этого сценария и будет признателен за любые указатели!

Answer 1

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