Помогите разобрать теорию. При прямой адресации к хэш-таблице ключи перенумерованы целыми числами из множества. Ну и понятно, что тогда к элементу массива (хэш-таблицы) мы добираемся за время O(1).
Но, чтобы по произвольному ключу получить его индекс, требуется время O(n), если эти ключи храняться в списке или массиве, или O(log(n)), если ключи и их индексы хранит сбалансированное двоичное дерево.
Или, все-таки здесь все полагают, что всегда можно придумать hash функцию с трудоемкостью O(1)? Например, есть множество ключей: «one», «two» ..., например n штук. причем n известно. Как добиться разыменования «one»->1, «two»->2 ... за O(1), а не O(n)?
