Что-то вроде HashMap, но отсортировано?

Question

Я пишу Java-программу, которая анализирует все слова из текстового файла и затем добавляет их в HashMap. Мне нужно посчитать, сколько разных слов содержится в файле. Мне также нужно выяснить слова с наибольшим количеством слов. HashMap состоит из каждого слова, отображенного в целое число, которое представляет, сколько раз слово встречается.

Есть ли что-то вроде HashMap, которое поможет мне разобраться в этом?

Answer 1

Вы можете использовать HashMultiset из google-collection :

import com.google.common.collect.*;
import com.google.common.collect.Multiset.Entry;

...

  final Multiset<String> words = HashMultiset.create();
  words.addAll(...);

  Ordering<Entry<String>> byIncreasingCount = new Ordering<Entry<String>>() {
    @Override public int compare(Entry<String> a, Entry<String> b) {
      // safe because count is never negative
      return left.getCount() - right.getCount();
    }
  });

  Entry<String> maxEntry = byIncreasingCount.max(words.entrySet())
  return maxEntry.getElement();

РЕДАКТИРОВАТЬ: упс, я думал, что вы хотели только одно наиболее распространенное слово. Но звучит так, как будто вы хотите несколько наиболее распространенных - так что вы можете заменить max на sortedCopy, и теперь у вас есть список всех записей по порядку.

Чтобы найти количество отдельных слов: words.elementSet().size()

Answer 2

Ручной способ сделать это следующим образом:

• Создать составной класс WordCount с полями word и count.
• Создать компаратор для этого класса, который сортирует по количеству.
• Когда вы закончите заполнять вашу HashMap, создайте новый список объектов WordCount, созданный из значений в HashMap.
• Сортировка списка с использованием вашего компаратора.

Answer 3

Вот Groovy-версия самого популярного ответа на этот вопрос:

List leastCommon(Multiset myMultiset, Integer quantity)
{

    Ordering<Multiset.Entry<String>> byIncreasingCount = new Ordering<Multiset.Entry<String>>() {
      @Override public int compare(Multiset.Entry<String> a, Multiset.Entry<String> b) {
          return a.getCount() - b.getCount() }
    }

    maxIndex = Math.min(quantity, myMultiset.entrySet().size() - 1)
    return byIncreasingCount.sortedCopy(myMultiset.entrySet()).subList(0, maxIndex)

}

List mostCommon(Multiset myMultiset, Integer quantity)
{

    Ordering<Multiset.Entry<String>> byDecreasingCount = new Ordering<Multiset.Entry<String>>() {
      @Override public int compare(Multiset.Entry<String> a, Multiset.Entry<String> b) {
          return b.getCount() - a.getCount() }
    }

    maxIndex = Math.min(quantity, myMultiset.entrySet().size() - 1)
    return byDecreasingCount.sortedCopy(myMultiset.entrySet()).subList(0, maxIndex)

}

Answer 4

Если вы хотите отсортировать карту по слову, то TreeMap - это встроенный ответ Java. Вы можете убедиться, что ваши объекты Word сопоставимы, или предоставить собственный компаратор.

SortedMap<Word,Integer> map = new TreeMap<Word,Integer>();
...
for all words {
    Integer count = map.get(word);
    if (count == null ) count = 0;
    map.put(word, count+1);
}

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

Answer 5

Похоже, класс TreeBag из библиотеки commons может делать то, что вы хотите. Он отслеживает, сколько копий объекта добавлено в пакет, и сортирует их в порядке возрастания количества. Чтобы получить элемент с наибольшим количеством, просто вызовите метод last(). Следует помнить, что материал коллекций общих ресурсов еще не обновлен с использованием обобщений, поэтому при его использовании вы можете получить массу предупреждений компилятора.

Answer 6

Вы проверили java.util.PriorityQueue? PriorityQueue - это, в основном, список с приоритетом, сопоставленным каждому элементу (реализуется несинхронизированной кучей приоритетов). Каждый раз, когда вы читаете новую строку, вы можете добавить ее или увеличить ее приоритет на 1, если она уже присутствует (логарифмическое время). Настоящая проверка выполняется по линейному времени, и в конце концов ее будет действительно легко использовать. Чтобы получить числа, которые появляются с наибольшей частотой, просто опрашивайте () для каждого, когда вы закончите!

edit Стандартное PriorityQueue не позволяет вам редактировать приоритет напрямую, поскольку для него требуется компаратор. Вы бы лучше с простой реализацией Hash или что-то вроде , как это

Answer 7

Для подсчета, напишите слова в наборе и подсчитайте размер, когда закончите.

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

Answer 8

• YourBean implements Comparable<YourBean>
• метод compareTo: порядок по числу слов
• TreeMap вместо hashmap