Java. Является ли обычной практикой использование хеш-таблицы (например, HashMap) для отображения объектов на себя?
Я делаю Java-приложение, которое будет хранить кучу случайных слов (которые могут быть добавлены или удалены из приложения в любое время). Я хочу быстрый поиск, чтобы увидеть, есть ли данное слово в словаре или нет. Какую структуру данных Java лучше всего использовать для этого? На данный момент я думал об использовании hashMap и использовании одного и того же слова в качестве значения и ключа для этого значения. Это обычная практика? Использование одной и той же строки для ключа и значения в паре (ключ, значение) кажется мне странным, поэтому я хотел убедиться, что не было какой-то лучшей идеи, которую я пропустил.
Я также думал об альтернативном использовании treeMap для сортировки слов, давая мне время поиска O(lgn), но hashMap должен дать ожидаемое время поиска O(1), насколько я понимаю, поэтому я решил, что будет лучше,
В общем, я просто хочу убедиться, что идея hashMap с удвоением строк как ключа и значения в каждой паре (ключ, значение) будет хорошим решением. Благодарю.
4 ответа
Я хочу быстрый поиск, чтобы увидеть, есть ли данное слово в словаре или нет. Какую структуру данных Java лучше всего использовать для этого?
Это учебный пример использования Set, Вы можете использовать HashSet, Наивная реализация для Set<T> использует соответствующий Map<T, Object> просто пометить, существует ли запись или нет.
Если вы храните это как набор слов в словаре, я бы посоветовал взглянуть на Tries. Они требуют меньше памяти, чем Set и иметь быстрые времена поиска наихудшего случая O(string length),
Любой класс, который является Set должно помочь вашей цели. Тем не менее, обратите внимание, что Set не позволит дубликатов. В этом отношении даже Map не позволит дублировать ключи. Я бы предложил использовать ArrayList(при условии, что синхронизация не требуется), если вам нужно добавить дубликаты записей и обрабатывать их как отдельные.
Моя единственная проблема - память, если вы используете HashSet и у вас очень большая коллекция слов... Тогда вам придется загрузить всю коллекцию в память... Если это не проблема.... (И ваша коллекция должна быть очень большой, чтобы это было проблемой)... Тогда HashSet должен быть в порядке... Если у вас действительно очень большая коллекция слов, то вы можете попробовать использовать дерево и загружать только в память частей, которые вас интересуют.
Также имейте в виду, что вставка выполняется быстро, но не так быстро, как в дереве, помните, что для этого нужно, чтобы Java вставляла каждый отсортированный элемент. Опять же, ничего особенного, но если вы добавляете много слов за раз, вы можете рассмотреть возможность использования дерева...