按值对元素排序的数据结构

Question

我需要 Java 中的数据结构，它可以操作 Strings，计算 ArrayList<String> 中每个单词的频率，然后我需要根据频率对它们进行排序.

简单来说，数据结构需要是一个关联数组，可以BY VALUES排序，我已经把行进入 HashMap 并且对 它无法排序的事实感到惊讶 ，现在我一直在思考另一个数据结构。

P.S。（使用两个列表不适合我的程序，因为它需要进行大量计算，所以如果单个结构包含每个 String 及其出现而不是 String 的列表会更好s 和另一个频率）。

编辑：感谢您的帮助，但有些人建议 TreeMap，所以我想在这里指定一些内容：我需要按字符串的出现排序的结构（在 [= 的情况下） 16=]s 它将是值而不是键）。

Answer 1

Java 有一个 SortedMap interface with two implementations. The easiest one being TreeMap

Answer 2

HashMap 没有排序，实际上也不应该这样。如果您想对条目进行排序，您可以使用 SortedMap 实现之一，例如 TreeMap.

TreeMap 有一个构造函数，如果您有非标准的 Comparator（例如，如果您想要 Strings 的自然排序），它可以帮助您：

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 来维护以这种方式排序的条目，因为键的顺序只设置一次并且您无法更改它，因为：

这不是传统的，Comparator/compareTo 运算符应该给出与运行相同的结果（这就是为什么可变类在 Maps)
预计这不会给您一些明显的结果，通常不会对键重新排序。

Answer 3

另一种解决方案，使用自定义 bean 和简单列表。

1/ 定义您的自定义 bean

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));

Answer 4

我认为这没有简单的数据结构。

当您收集频率数据时，频率正在发生变化。收集所有字符串频率后应该对哪个进行排序。

我能想到的最简单的方法是：

// 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 5

如果你用一个maxheap数据结构来存储字符串和它的出现频率值，并且始终保持最大值频率在最前面，那么你可以简单地一次性获得频率最大的那个，但是这里的复杂性是重新计算和调整最大堆，因此实际上取决于您希望看到更多的变化类型 - 更多的单词数量或高度变化的单词频率。

按值对元素排序的数据结构

Data Structure to sort elements by values

java

sorting

data-structures

associative-array