Какая структура данных для O (1) произвольного вставки / удаления и O (1) произвольного доступа?

Question

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

• Постоянное время вставки или удаления.
• Постоянный поиск по идентификатору.

Фактическая система:

У меня есть куча объектов, каждый с уникальным идентификатором. Моя программа должна будет получать запросы на идентификатор и возвращать соответствующий объект.

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

Я использую C.

Вот аналогичный вопрос , но я не уверен, насколько он актуален.

Answer 1

A Хеш-таблица может быть довольно хорошим решением в вашем случае - даже если она не в O (1), когда есть коллизия: это довольно эффективное решение.

Answer 2

Единственная структура, которая ему подходит, это ... C массив. SomeObject arr[MAX_NUM_OBJECTS] справляется с этим быстро и эффективно

Answer 3

Почему бы просто не поместить их все в файл, отразить файл и позволить ОС обрабатывать кэширование?

Answer 4

Зависит от того, сколько данных и какие ключи. Хеш-таблицы хорошо работают с большими объемами данных, которые будет трудно сравнивать (строки, сложные структуры данных и т. Д.). Для небольших наборов данных с целочисленными ключами часто можно добиться лучшей производительности с помощью простых красно-черных деревьев. Это потому, что для выполнения хороших хеш-функций требуется время.

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

Чтобы дать вам лучший ответ, нам действительно нужно знать, чего вы пытаетесь достичь. Любая дополнительная информация о том, для чего вы используете структуру данных, поможет