Быстрый алгоритм / структура данных, которая позволяет линейное расположение?

Question

Я пытаюсь реализовать систему, в которой у меня будут пары структуры ключ-значение. Их нужно будет удерживать каким-то линейным образом (то есть они могут быть проиндексированы), и однажды заданная позиция не может быть перемещена, поэтому вставки могут только добавляться (и в действительности не может быть много сортировки). Просто в качестве примера это то, что имело в виду:

Data list:
    0: { "somekey", somevalue }
    1: { "someotherkey", someothervalue }
    ...
    n: { "justanotherkey", justanothervalue }

Я спроектировал систему так, чтобы при поиске ключа его индекс мог кэшироваться, а затем вызываться с постоянным временем. Теперь, поскольку у меня нет возможности предсказать порядок или объем данных, и я не могу их отсортировать, мне нужны идеи алгоритмов или структур данных, которые были бы лучше, чем просто линейный поиск, но все же сохраняли ограничения, которые я мне нравится.

У кого-нибудь есть идеи? Я сомневаюсь, что смогу значительно ускорить его, но каждая мелочь помогает, так как это будет ядром моей системы. Заранее спасибо!

== EDIT ==

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

struct Entry {
    /* Key is actually a complex struct itself with string, and params */
    Key key;
    Data* data; 
}

Answer 1

Как насчет ключа хеш-таблицы -> индекс в массиве?

Answer 2

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

Надеюсь, это поможет!