要使用哪种数据结构？

我有这样一个场景，我需要存储的字符串的数和我需要回到前十弦它具有最大计数，要使用哪种数据结构？

例如，

String Count 
--------------------------------- 
String1 10 
String2 9 
String3 8 
. 
. 
. 
String10 1

我考虑使用散列表来存储字符串和它的计数，但是很难从它中检索前十个字符串，因为我必须再次循环来找到它们。

此处有任何其他建议吗？

来源

2012-08-02 Lokn

只需使用一个有序映射像

Map<Integer, List<String>> strings

，其中的关键是频率值和值与频率出现字符串列表。

然后，循环遍历地图，并通过值列表的内部循环，直到看到10个字符串。那些是最常见的10个之一。

随着额外要求，该算法应该支持更新频率：将字符串添加到像Map<String, Integer>一个地图，关键是字符串和值实际频率（增量，如果你的价值再次看到一个字符串）。之后将键/值对复制到我上面建议的地图。

来源

2012-08-02 14:52:03

+1好主意...... – assylias 2012-08-02 14:53:41

如何在计算字符串时更新这样的结构？（虽然没有明确提及，但通常是用例）。 – ffriend 2012-08-02 15:01:10

让我们来计算字符串出现的频率并将其添加到此地图中，并假设有10个字符串，每个字符串都出现10次，那么此地图将具有像1-字符串1这样的条目.... string10，2-string1 ... string10类似地，它对地图中的所有值都有相同的条目，是否有任何优化的解决方案。 – Lokn 2012-08-02 15:03:04

Priority Que。

你可以让一个类来把它：

public class StringHolder{ 
    private String string; 
    private int value; 

    //Compare to and equals methods 
}

则按照当您插入，很容易获得前10名。

来源

2012-08-02 14:50:25 Brinnis

如果字符串已经存在，那么我只需要增加计数，如何找到特定的字符串对象呢？ – Lokn 2012-08-02 14:53:24

这将是一个相对缓慢的操作。你将不得不遍历所有查找该String的对象。如果你这样做了很多哈希映射可能会更好。您必须决定是否希望get top 10变慢，或者如果将数据结构中已有的内容更新得更慢。 – Brinnis 2012-08-02 14:59:57

@Lokn：你可以用一个哈希映射对字符串进行计数，然后使用优先级队列来查找N个频率最高的字符串。这将是2次通过，但渐近运行时间仍将摊销O（n）。 – ffriend 2012-08-02 15:20:24

对于喜欢“找到前N的任何任务项目“优先队列是完美的解决方案。请参阅Java的PriorityQueue类。

来源

2012-08-02 14:52:00 ffriend

我不知道，但我想这对于您需要的最合适的优雅类是番石榴的 http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/TreeMultiset.html

来源

2012-08-02 14:59:32

TreeMultiset可以使用，但它比HashMultiset有更多的开销。它强加的顺序是实际的键，而不是数。因此，您为关键订单付出的开销被浪费了。 – Matt 2012-08-02 15:26:30

番石榴这将是对这个非常有用的一个HashMultiset。

HashMultiset<String> ms = Hashmultiset.create(); 
ms.add(astring); 
ms.add(astring, times); 


ImmutableMultiset<String> ims = Multisets.copyHighestCountFirst(ms); 

// iterator through the first 10 elements, and they will be your top 10 
// from highest to lowest.

来源

2012-08-02 15:04:15 Matt

为此，您需要Max Heap数据结构。把它全部放入最大堆，并连续10次（或任何n次）清除。

如果您打算在数据加载到内存后继续重用数据，则可能值得按值而不是堆排序。

来源

2012-08-03 17:01:04 Ambar

要使用哪种数据结构？

回答

相关问题