Наилучшая структура данных для заданного набора операций - Добавить, Извлечь Мин / Макс и Извлечь конкретный объект

Question

Я ищу оптимальную (временную и пространственную) оптимальную структуру данных для поддержки следующих операций:

1. Добавление лиц ( имя, возраст ) в глобальное хранилище данныхлиц
2. Выбор человека с минимальным и максимальным возрастом
3. Поиск лица возраст с указанием имени

Вото чем я мог бы подумать:

• Сохранять массив Person и продолжать добавлять в конец массива при добавлении нового Person
• Сохранять хэш имени Person противage, чтобы помочь определить возраст человека с указанным именем
• Поддерживать два объекта minPerson и maxPerson для Person с минимальным и максимальным возрастом.Обновите его, если необходимо, при добавлении нового персонажа.

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

Есть ли что-нибудь, что может быть дополнительно оптимизировано здесь?

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

Answer 1

Вы можете избавиться от массива, поскольку он не предоставляет ничего, чего не могут сделать две другие структуры.

В противном случае, хеш-таблица + мин / макс, вероятно, будет работать хорошо для вашего варианта использования. На самом деле, это именно то, что я бы использовал.

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

Answer 2

Похоже, вам нужна структура данных, которая требует быстрой вставки, а также поддерживает быстрые запросы на 2 разных ключа (имя и возраст).

Я бы предложил сохранить две структуры данных, одну - отсортированную структуру данных (например, сбалансированное двоичное дерево поиска), где ключ - это возраст, а значение - указатель на объект Person, а другую - хеш-таблицу, гдеключ - это имя, а значение - указатель на объект Person.Обратите внимание, что мы не храним две копии одного и того же объекта.

Сбалансированное бинарное дерево поиска будет обеспечивать вставки O (log (n)) и запросы max / min, а hastable даст нам O (1)(амортизируется) вставляет и ищет.

Когда мы добавляем новую персону, мы просто добавляем указатель на нее на обе структуры данных.Для запроса минимального / максимального возраста мы можем получить объект, запросив BST.Для запроса имени мы можем просто запросить хеш-таблицу.

Ваш вопрос не запрашивает обновления / удаления, но они также выполнимы путем соответствующего обновления обеих структур данных.

Answer 3

Похоже, вы ожидаете, что имя будет уникальным идентификатором;в противном случае ваша операция 3 является неоднозначной (каков правильный результат возврата, если у вас есть две записи для Джона Смита?)

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