Возможна ли реализация структуры данных с поиском O (1) без использования массивов?

Question

В настоящее время я прохожу университетский курс по структурам данных, и эта тема уже давно беспокоит меня (это не домашнее задание, а чисто теоретический вопрос).

Предположим, вы хотите реализовать словарь. В словаре, конечно, должна быть функция поиска, принимающая ключ и возвращающая значение .

Прямо сейчас я могу представить только 2 очень общих способа реализации такой вещи:

• Использование некоторого дерева поиска, которое (всегда?) Дало бы O (log n) наихудшее время выполнения для нахождения значения по ключу или
• Хеширование ключа, который, по сути, возвращает натуральное число, соответствующее индексу в массиве значений, давая O (1) время выполнения в худшем случае.

Возможно ли O (1) наихудший случай время работы функции поиска без использования массивов?

Доступен ли произвольный доступ только при использовании массивов?
Возможно ли это благодаря использованию структуры данных на основе указателей (таких как связанные списки, деревья поиска и т. Д.)?

Возможно ли сделать какие-то конкретные предположения, например, ключи находятся в некотором порядке?

Другими словами, можете ли вы представить реализацию (если возможно) для функции поиска и словаря , которая получит любой ключ в словаре и вернет его значение в O ( 1) время без использования массивов для произвольного доступа?

Answer 1

Вот еще один ответ, который я сделал на эту общую тему. По сути, алгоритмы достигают своих результатов, обрабатывая определенное количество бит информации. Время, которое они занимают, зависит от того, как быстро они могут это сделать.

Точка принятия решения, имеющая только 2 ветви, не может обрабатывать более 1 бита информации. Однако точка принятия решения, имеющая n ветвей, может обрабатывать до log (n) битов (основание 2).

Единственный механизм, который мне известен на компьютерах, который может обрабатывать более 1 бита информации за одну операцию, - это индексирование, будь то индексирование массива или выполнение таблицы переходов (которая индексирует массив ).

Answer 2

Это не использование массива, который делает поиск O (1), это факт, что время поиска не зависит от размера хранилища данных. Следовательно, любой метод, который обращается к данным напрямую, без поиска, пропорционально каким-либо образом пропорционального размеру области данных, будет O (1).

Answer 3

вы можете реализовать хеш с помощью дерева trie. Сложность O (max (length (string))), если у вас есть строки ограниченного размера, то вы можете сказать, что он работает в O (1), это не зависит от количества строк в вашей структуре. http://en.wikipedia.org/wiki/Trie