您将使用哪种数据结构：树形图还是哈希图？（爪哇）
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
描述 | 一个 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 中）的实现会很有帮助。
解决方案
TreeMap 似乎不费吹灰之力对我来说 - 仅仅因为<！>按字母顺序排列<！>需求。迭代时HashMap没有排序; TreeMap以自然键顺序迭代。
编辑：我认为Konrad的评论可能暗示<！>使用HashMap，然后排序。<！> quot;这很好，因为尽管我们最初会进行N次迭代，但由于重复，我们最终会得到K <！> lt; = N个密钥。我们不妨将昂贵的位（排序）保存到最后，当我们得到的密钥少于采取小的但非常量的命中时保持它的排序。
话虽如此，我现在仍然坚持我的答案：因为这是实现目标的最简单方式。我们并不是真的知道OP特别担心性能，但问题暗示他关注优雅和简洁。使用TreeMap使这个非常简短，这对我很有吸引力。我怀疑如果性能真的是一个问题，可能有一种比TreeMap或HashMap更好的攻击方式：）
其他提示
TreeMap胜过HashMap，因为TreeMap已经为你排序了。
但是，您可能需要考虑使用更合适的数据结构，即包。看到 Commons Collections - 以及 TreeBag 类：
这有一个很好的内部结构和API：
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
我看到很多人说<！>“; TreeMap查找需要O(n log n) <！>”!!怎么会？
我不知道它是如何实现的，但在我脑海中需要O(log n)。
这是因为树中的查找可以在O(n + k log k)中完成。每次在其中插入项目时，都不会对整个树进行排序。这就是使用树的全部想法！
因此，回到最初的问题，比较的数字结果是：
HashMap方法： O(k + n log k)平均情况，最坏情况可能会大得多
TreeMap方法： <=>最坏情况
其中n =文本中的单词数，k =文本中不同单词的数量。
哈希地图应该快得多。您不应该根据您希望最终安排项目的方式选择容器;只需在最后对（字，频率）对列表进行排序。通常会有比文件中的单词更少的这类对，因此使用哈希映射的渐近（和真实）性能会更好。
您不能将TreeMap<String,Number>指定给类型为Map<String,Integer>的变量。 Double，Long等可以是<！>“put <！>”;进入Integer。当我<！>“get <！>”时来自<=>的值，它必须是<=>。
完全忽略任何i18n问题，内存限制和错误处理，这里是：
class Counter {
public static void main(String... argv)
throws Exception
{
FileChannel fc = new FileInputStream(argv[0]).getChannel();
ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
CharBuffer cb = Charset.defaultCharset().decode(bb);
Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
Map<String, Integer> counts = new TreeMap<String, Integer>();
Matcher m = p.matcher(cb);
while (m.find()) {
String word = m.group();
Integer count = counts.get(word);
count = (count == null) ? 1 : count + 1;
counts.put(word, count);
}
fc.close();
for (Map.Entry<String, Integer> e : counts.entrySet()) {
System.out.printf("%s: %d%n", e.getKey(), e.getValue());
}
}
}
<！> quot;当一个键已经存在时，它具有与HashMap相同的性能。<！> quot; - 这是完全错误的。 HashMap具有O（1）插入和TreeMap O（n log n）。至少需要n个n次检查才能确定它是否在表中！
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class TreeMapExample {
public static void main (String args[]){
Map<String,Integer> tm = new TreeMap<String,Integer>();
try {
FileInputStream fis = new FileInputStream("Test.txt");
DataInputStream in = new DataInputStream(fis);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String line;
int countValue = 1;
while((line = br.readLine())!= null ){
line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
StringTokenizer st = new StringTokenizer(line, " ");
while(st.hasMoreTokens()){
String nextElement = (String) st.nextElement();
if(tm.size()>0 && tm.containsKey(nextElement)){
int val = 0;
if(tm.get(nextElement)!= null){
val = (Integer) tm.get(nextElement);
val = val+1;
}
tm.put(nextElement, val);
}else{
tm.put(nextElement, 1);
}
}
}
for(Map.Entry<String,Integer> entry : tm.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
这样，在我看来，更好地使用 Apache Commons Collections <的bag / HashBag.html“rel =”nofollow“> HashBag / a>或 HashMultiset 来自番石榴或 HashBag proposal / eclipse-collections“rel =”nofollow“> Eclipse集合（格式 GS Collections ）或以下任何类别：
Order | Guava | Apache | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define | HashMultiset | HashBag | HashBag | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted | TreeMultiset | TreeBag | TreeBag | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked |LinkedHashMultiset| - | - | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash- |Synchroniz-|Synchroniz- | Collections.synchronizedMap(
not define | Multiset | edBag | edBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent | - |Synchroniz-|Synchroniz- | Collections.synchronizedSorted-
and sorted | |edSortedBag| edSortedBag | Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab- | Collections.unmodifiableMap(
not define | | leBag | leBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab- | Collections.unmodifiableSorted-
sorted | Multiset |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────
示例：
1。 使用来自Apache的SynchronizedSortedBag ：
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));
// Print count words
System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
// Print all unique words
System.out.println(bag.uniqueSet()); // print [All!, Hello, Hi, World!]- in natural (alphabet) order
// Print count occurrences of words
System.out.println("Hello = " + bag.getCount("Hello")); // print 2
System.out.println("World = " + bag.getCount("World!")); // print 2
System.out.println("All = " + bag.getCount("All!")); // print 1
System.out.println("Hi = " + bag.getCount("Hi")); // print 1
System.out.println("Empty = " + bag.getCount("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.uniqueSet().size()); //print 4
2。使用Eclipse（GC）中的TreeBag ：
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
MutableSortedBag<String> bag = TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
// Print all unique words
System.out.println(bag.toSortedSet()); // print [All!, Hello, Hi, World!]- in natural order
// Print count occurrences of words
System.out.println("Hello = " + bag.occurrencesOf("Hello")); // print 2
System.out.println("World = " + bag.occurrencesOf("World!")); // print 2
System.out.println("All = " + bag.occurrencesOf("All!")); // print 1
System.out.println("Hi = " + bag.occurrencesOf("Hi")); // print 1
System.out.println("Empty = " + bag.occurrencesOf("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.toSet().size()); //print 4
3。 使用来自番石榴的LinkedHashMultiset ：
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
// Print all unique words
System.out.println(multiset.elementSet()); // print [Hello, World!, All!, Hi] - in predictable iteration order
// Print count occurrences of words
System.out.println("Hello = " + multiset.count("Hello")); // print 2
System.out.println("World = " + multiset.count("World!")); // print 2
System.out.println("All = " + multiset.count("All!")); // print 1
System.out.println("Hi = " + multiset.count("Hi")); // print 1
System.out.println("Empty = " + multiset.count("Empty")); // print 0
// Print count all words
System.out.println(multiset.size()); //print 6
// Print count unique words
System.out.println(multiset.elementSet().size()); //print 4
您可以使用更多示例在我的github项目中找到
我肯定会选择 TreeMap：
- TreeMap 在插入时自动对新键进行排序，之后不需要排序。
- 当键已经存在时，它具有与 HashMap 相同的性能。
TreeSet 内部使用 TreeMap，所以为什么不直接使用 TreeMap。
根据速度要求，您还可以使用 Trie 。但是，如果TreeMap足够快，那么实现其中一个就没有意义了。
考虑数据结构的添加或删除频率。如果它很高，TreeMap就不理想了。除了搜索现有的入境nLn之外，它还经常进行重新平衡。
另一方面，哈希结构在内存上有点夸张（超过分配）。如果你可以咬那个子弹，那就去哈希结构并在需要时进行排序。
以下是用于读取文本文件，基于键进行排序，然后根据值进行排序的java示例;取决于文件中单词的出现次数。
public class SortFileWords {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
ValueCompare vc = new ValueCompare(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
List<String> list = new ArrayList<>();
Scanner sc;
try {
sc = new Scanner(new File("c:\\ReadMe1.txt"));
while (sc.hasNext()) {
list.add(sc.next());
}
sc.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
for (String s : list) {
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else
map.put(s, 1);
}
System.out.println("Unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("Sorted map on keys: " + sorted_map);
TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
sorted_value_map.putAll(map);
System.out.println("Sorted map on values: " + sorted_value_map);
}
}
class ValueCompare implements Comparator<String> {
Map<String, Integer> map;
public ValueCompare(Map<String, Integer> map) {
this.map = map;
}
@Override
public int compare(String s1, String s2) {
if (map.get(s1) >= map.get(s2))
return -1;
else
return 1;
}
}
为什么不使用 TreeSet
与TreeMap相同的排序概念，除了它是一个Set - 根据定义，它是<！> quot;一个不包含重复元素的集合<！> quot;。
从您的问题描述中，听起来好像您需要一个Set，我看不到您要映射的键和值。
此类实现由TreeMap实例支持的Set接口。此类保证有序集按升序元素顺序排序，根据元素的自然顺序排序（请参阅Comparable），或者根据设置创建时提供的比较器进行排序，具体取决于使用的构造函数。
基本上取决于要求。有时哈希映射有时候是树形图。但是哈希映射最好只使用它们对开销进行排序的一些约束。
