Есть миллион объектов, которые названы, и мне нужна структура данных, которая позволит мне быстро искать по имени и быстро вставлять их. Какой лучший выбор и каковы ваши рассуждения?Какая структура данных хранит миллионы объектов?
Я думал о хэш-таблице или двоичном дереве, но я не уверен.
Оптимизация для поиска и для вставки принципиально тянет вас в противоположных направлениях. Для вас важно хорошо понимать ваш вариант использования, чтобы решить, какой из них более важен. Как только вы это знаете, вы можете выбрать правильную структуру.
Несколько вариантов являются:
Это ложная дилемма, потому что есть третий вариант: игнорировать (или, по крайней мере, девальвацию) пространство и оптимизировать как для вставки, так и для поиска, создавая структуру данных, которая объединяет две или более базовые структуры. –
Конечно, вы можете это сделать, но, как вы сказали, вам понадобятся две разные структуры данных, выделяющие мою точку зрения. – DevShark
Двоичные деревья поиска (BST) имеют наихудшую сложность O (Log (n)) для операции поиска (ключа), а также операции Insert() , Поиск (объект) не поддерживается в традиционном дизайне (но вы можете добавить эту функциональность).
Поскольку вы указали только двоичное дерево, а не BST, поиск (ключ), поиск (объект) и вставка (объект) будут O (n), O (n) и O (1) соответственно.
Для Hashmap поиск (объект) - это O (n), Содержит (ключ) - O (1), а Insert (ключ, объект) также O (1), при условии, что много цепочки и функция хеширования хороша.
Имейте выбор.
Hashmap имеет «содержит» в O (1). Итерирование с помощью ключей для поиска - O (n) –
@ cricket_007: Обновлено время выполнения для каждого случая. – displayName
Вы должны перефразировать свой вопрос, чтобы быть более конкретным. Вы должны упомянуть хотя бы язык, на котором можно реализовать алгоритм, возможно, платформу и дать более подробную информацию о структуре кода, который вы пытались. Если вы говорите об простых алгоритмах компьютерных наук, тогда вы должны говорить в терминах алгоритмов обозначения «O» или аналогичных. Например, вы говорите, что вы «мыслили» в хэш-таблице или двоичном дереве, но вы не сказали, на каком языке, что может резко изменить результат. –
Используйте базу данных в памяти. В значительной степени предназначен для вашего прецедента здесь –