Самый быстрый поиск и вставка

Question

У меня есть миллион предметов. Какой самый быстрый способ поиска конкретного объекта с именем в качестве ключа и самый быстрый способ выполнить вставку? Хэширования будет достаточно?

Answer 1

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

Answer 2

Можно использовать дерево B +, это гарантирует меньшую сложность поиска (поскольку вы быстро достигаете конечных узлов, высота = log n до основания k, k = степень узлов).К базам данных предъявляются аналогичные требования, и они используют деревья B + для обслуживания и извлечения данных.

Answer 3

Здесь существует несколько структур, которые вы можете использовать.У каждого есть свои преимущества и недостатки.

HashTable будет иметь большое время поиска и время вставки, если у вас есть таблица, которая минимизирует коллизии.Если нет, то поиск / вставка может привести к гораздо большему времени.

Двоичное дерево поиска имеет вставку и поиск ln (n) при условии, что оно сбалансировано.Иногда балансировка может привести к тому, что вставка займет немного больше времени, чем ln (n), в зависимости от выбранного вами BST.

Answer 4

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

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

Answer 5

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

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

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