Структура данных для сортировки элементов по значениям

Question

Мне нужна структура данных на Java, которая может манипулировать String s, вычислять частоту каждого слова в ArrayList<String>, а затем мне нужно отсортировать их на основе частот.

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

P.S. (использование двух списков не подходит для моей программы, потому что для этого нужно выполнить множество вычислений, поэтому было бы лучше, если бы одна структура содержала каждый String и его появление вместо списка для String s, а также для частоты).

EDIT: Я ценю помощь, но некоторые люди предлагая TreeMap, поэтому я хочу, чтобы указать что-то здесь: мне нужна структура, отсортированных по вхождений строк (в случае Map ы было бы значения а не клавиши).

Answer 1

Я не думаю, что для этого есть простая структура данных.

Частоты меняются при сборе частотных данных. Для чего сортировка должна происходить после сбора всех строк.

Самый простой способ, которым я могу думать:

// psuedo-code 
final Map<String, Integer> stringFreq = ....; // it doesn't matter what kind of impl you use 

// collect the String vs frequency in stringFreq 

Map<String, Integer> result = new TreeMap<String, Integer>(stringFreq, 
     new Comparator<String> { 
     @Override 
      public int compare(String a, String b) { 
       int aFreq = stringFreq.get(a); 
       int bFreq = stringFreq.get(b); 
       return (aFreq==bFreq)?a.compareTo(b) : (aFreq-bFreq); 
      } 
     }); 


// result should have data sorted by frequency, and then the string value 

Answer 2

Java имеет интерфейс SortedMap с двумя реализациями. Самый простой из них: TreeMap

Answer 3

HashMap не сортируется, на самом деле и не должно быть так. Если вы хотите отсортировать записи, вы можете использовать одну из реализаций SortedMap, например TreeMap.

TreeMap имеет конструктор, который поможет вам в случае, если у вас есть нестандартные Comparator (например, если вы хотите естественной сортировки для String ы):

TreeMap(Comparator<? super K> comparator) 

UPD: Я пропустил момент, что вам нужно сортировать записи по значению.

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

Вы можете использовать любой Map, например, остаться с HashMap, но затем, перед обработкой, вы можете отсортировать записи:

Set<Map.Entry<String, Integer>> entries = map.entrySet(); 
Set<Map.Entry<String, Integer>> sorted = new TreeSet<>(
     Comparator.comparingInt(Map.Entry::getValue).reversed()); // it's Java 8, but you may extract this lambda 
sorted.addAll(entries); 
for (Map.Entry<String, Integer> entry: sorted) { 
    //... 
    // the entries will be sorted by value 
} 

Чтобы быть точным, вы не можете вы любой вид Map к сохранять записи, отсортированные таким образом, потому что порядок ключей устанавливается только один раз, и вы не можете изменить его, из-за:

1. Это не-обычный, Comparator/compareTo оператор должен дать тот же результат по прогон (вот почему изменяемые классы не оцениваются в Map s)
2. Это не должно дать вам ощутимого результата, ключи не будут повторно сортироваться в целом.

Answer 4

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

1/Определить пользовательский боб

public class StringOccurence { 
    String string ; 
    int occurrence ; 
} 

2/Создать компаратор

public class StringOccurrenceComparator implements Comparator<StringOccurence> { 
    @Override 
    public int compare(StringOccurrence so1, StringOccurrence so2) { 
    return Integer.compare(so1.occurrence, so2.occurrence); 
    } 
} 

3/Сортировка вы список с помощью компаратора

List<StringOccurrence> list = constructList(); 
Collections.sort(list, new StringOccurrenceComparator()); 

Если вы, к счастью для используйте java8, вот короткая версия пунктов 2 и 3:

List<StringOccurrence> list = constructList(); 
Collections.sort(list, (so1, so2) -> Integer.compare(so1.occurrence, so2.occurrence));