Какую структуру данных использовать для хранения пар ключ-значение типа <String, String>? Один ключ имеет много значений

Question

мое приложение читает словосочетание биграмм (пары) из файла .txt.они должны читаться как пары ключ-значение.один ключ может иметь несколько значений (поэтому исключается любой вид карты как структуры данных) ... Я хочу сохранить их отсортированными в естественном алфавитном порядке.

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

Итак, по сути, я пытаюсь реализовать

SortedList <String, String> 

в некотором роде ..

Я столкнулся со следующими структурами данных, которые соответствуют моим требованиям, хотя я не могу решить, какую из них использовать: (MultiMap, упомянутый здесь, является частьюкаркаса коллекций Google)

1. HashMultiMap

2. Попытки - я знаю только основы этой структуры данных.Я нашел одну реализацию этого в Java здесь .Он не реализует операцию удаления ().

3. FastTreeMap

4. TreeMultimap

5. SortedSetMultimap

или любую другую структуру данных, которую вы бы порекомендовали?Я еще не просмотрел словарь на Java ... Пожалуйста, помогите мне решить, какой из них выбрать ...

Спасибо!

РЕДАКТИРОВАТЬ - ожидается, что список будет содержать около 100-200записи

РЕДАКТИРОВАТЬ2: Операции: поиск, если для данного ключа существует сопоставление значения ключа. Как я уже говорил, dst будет хранить список пар глагола-слова в качестве записей значения ключа;он инициализируется чтением записей из файла ... работа идет примерно так: сначала мы получаем все ключи из dst ... читаем файл и токенизируем его (сделано через OpenNLP, dst не для этого) .. а затемпоиск, если какой-либо из токенов находится в ключе (т. е. является глаголом) в dst ...... как только найден, мы получаем все значения для данного ключа и ищем следующий токен в наборе значений ...если значение также найдено в dst, это означает, что обнаружена совместная локация .. тогда устанавливаются подходящие значения ... ЭТО КАК DST ДОЛЖЕН НАСТОЯЩИМ РАБОТАТЬ ...

Answer 1

Не HashMap или HashMultiMap, поскольку они не позволяют перебирать ключи по порядку.

Не FastTreeMap или ConcurrentSkipListMap ..., если ваше приложение не является многопоточным.

Различные реализации TreeMap или TreeMultiMap в порядке, хотя версии TreeMap повлекут за собой создание их экземпляров как Map<String,List<String>> и управление списками.

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

Answer 2

java.util.NavigableMap - это интерфейс, предоставляющий абстракцию карты с полным упорядочением ключей. JavaSE 6 предоставляет java.util.TreeMap или java.util.concurrent.ConcurrentSkipListMap в качестве реализаций. Первое, вероятно, достаточно для вас. Чтобы было ясно, я бы рекомендовал использовать что-то вроде:

Map<String,Set<String>> со следующим типом бетона TreeMap<String, ArraySet<String>>.

Answer 3

К вашему сведению: проект Google Collections был прекращен и теперь является частью Guava .

от Google.

Guava's ListMultimap гарантирует, что значения в определенном ключе останутся в том же порядке, в котором они появились в файле. Однако он не будет сохранять ключи в том же порядке, в каком они были в файле.