Существуют ли O (1) структуры данных с произвольным доступом, которые не зависят от непрерывного хранения?

Question

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

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

Есть ли такая вещь?

Answer 1

Распределенные хеш-карты имеют такое свойство. Ну, на самом деле, не совсем, в основном хеш-функция сообщает вам, в каком хранилище следует искать, там вам, вероятно, придется полагаться на традиционные хеш-карты. Он не полностью покрывает ваши требования, так как список, содержащий области / узлы хранения (в распределенном сценарии), опять же, как правило, представляет собой хэш-карту (по сути, превращая ее в хэш-таблицу хеш-таблиц), хотя вы можете использовать некоторые другие алгоритм, например если число областей хранения известно.

РЕДАКТИРОВАТЬ:
Немного забыв, вы, вероятно, захотите использовать разные хеш-функции для разных уровней, в противном случае вы получите много одинаковых хеш-значений в каждой области хранения.