Спасибо)

ну собссно да, внутренние фактически отработают только один раз

какой load factor теоретически нужен для хэштаблицы, чтобы операции были за O(1)?

Встречал в какой-то лекции, что количество бакетов должно расти не медленнее, чем количество занятых бакетов в квадрате, чтобы коллизий было минимум (теоретически).

Подтверждения теперь найти не могу

Любой константный, не?

не

1 уже не годится, а большие надо ещё доказать)

*меньшие

а, вот что-то похожее:

An elaboration on this approach is the so-called dynamic perfect hashing,[16] where a bucket that contains k entries is organized as a perfect hash table with k2 slots. While it uses more memory (n2 slots for n entries, in the worst case and n × k slots in the average case), this variant has guaranteed constant worst-case lookup time, and low amortized time for insertion. It is also possible to use a fusion tree for each bucket, achieving constant time for all operations with high probability.[17]

вы говорите об идеальном хешировании, 5 пункт 11 главы Кормена

стр. 292 того же кормена

Это про какую?

не понял сути вопроса

Как устроена таблица?

метод цепочек

Спам-реклама средств спам-рекламы 👍

Вспомнил где можно прочесть все детали хеширования более детально, Д. Кнут в 3 части искусства программирования, в разделе 6.4 приводит очень детальное сравнение всех возможных методов хеширования и устройств хеш-таблиц. Имейте в виду, что это не самая простая книга для прочтения, но детальнее чем Кнут рассказывают только в статьях

Ну и че эт =/

спасибо