Какую структуру данных вы бы использовали: TreeMap или HashMap? (Джава)

Question

Описание | Java-программа для чтения текстового файла и печати каждого из уникальных слов в алфавитном порядке вместе с количеством совпадений слова в тексте.

Программа должна объявить переменную типа Map<String, Integer> для хранения слов и соответствующей частоты встречаемости. Какой конкретно тип? TreeMap<String, Number> или HashMap<String, Number>?

Ввод необходимо преобразовать в нижний регистр.

Слово не содержит ни одного из следующих символов: \t\t\n]f.,!?:;\"()'

Пример вывода |

 Word            Frequency
  a                 1
  and               5
  appearances       1
  as                1
         .
         .
         .

Замечание | Я знаю, я видел элегантные решения этого в Perl с примерно двумя строками кода. Тем не менее, я хочу видеть это на Java.

Редактировать: О да, было бы полезно показать реализацию, использующую одну из этих структур (в Java).

Answer 1

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

Answer 2

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

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

Answer 3

Почему бы не использовать TreeSet ?

Та же концепция упорядочения, что и у TreeMap, за исключением того, что это Set - который, по определению, представляет собой «коллекцию, которая не содержит повторяющихся элементов».

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

Этот класс реализует интерфейс Set, поддерживаемый экземпляром TreeMap. Этот класс гарантирует, что отсортированный набор будет в порядке возрастания элементов, отсортирован в соответствии с естественным порядком элементов (см. Comparable) или компаратором, предоставленным во время создания набора, в зависимости от того, какой конструктор используется.

Answer 4

В зависимости от требований к скорости вы также можете использовать Trie . Но нет смысла реализовывать один из них, если TreeMap достаточно быстр.