История изменений
Исправление a--, (текущая версия) :
Тут вот https://en.wikipedia.org/wiki/Dynamic_perfect_hashing якобы смогли сделать О(1) даже в худшем случае и даже при заранее неизвестных данных.
Правда search в хэше неполноценный в том смысле, что выдает 1 бит (есть ключ / нет ключа), а я неявно имел в виду полноценный ответ «равный мне или следующий за мной ключ это ...» что будет |K| бит.
Причем их О(1) это не знаю что от длины ключа.
Исправление a--, :
Тут вот https://en.wikipedia.org/wiki/Dynamic_perfect_hashing якобы смогли сделать О(1) даже в худшем случае и даже при заранее неизвестных данных.
Правда search в хэше неполноценный в том смысле, что выдает 1 бит (есть ключ / нет ключа), а я неявно имел в виду полноценный ответ «равный мне или следующий за мной ключ это ...».
Причем их О(1) это не знаю что от длины ключа.
Исходная версия a--, :
Тут вот https://en.wikipedia.org/wiki/Dynamic_perfect_hashing якобы смогли сделать О(1) даже в худшем случае и даже при заранее неизвестных данных.
Правда search в хэше неполноценный в том смысле, что выдает 1 бит (есть число / нет числа), а я неявно имел в виду полноценный ответ «равное мне или следующее за мной число это ...».