| 的解决方案。多重映射（Multimaps）一个multimap与一个map类似, 只是它可以将每个键映射为多个值。Collections Framework不包括多重映射接口，因为它们不是很普遍地被使用。将一个其值为List对象的Map当作多重映射来使用则是相当简单的事情。这个技术在下一个代码举例中将被演示，这个例子是阅读每行（全部小写）一个单词的一部词典并打印所有满足尺寸标准的permutation groups（排列组）。一个排列组是一组单词，它们包含完全相同的字母，但字母顺序不同。这个程序在命令行中使用了两个参数：词典文件名和要打印的排列组的尺寸；排列组包含的单词如果少于指定的最小值，则该排列组不被打印。
有一个查找排列组的标准技巧：将词典中的每个词的字母按字母顺序进行排列（即将一个词的字母按字母顺序记录下来）并将一个项放入一个多重映射，将经过字母排序的单词映射到原来的单词。例如，单词"bad" 导致一个项映射 "abd" 至 "bad" 被放入多重映射。一个瞬间的反射将显示任何给定的键映射到所有单词形成一个排列组。在一个多重映射中迭代键以及打印满足尺寸条件的每一个排列组是一个简单的事情。
下列程序是这个技术的一个直接的实现。仅有的技巧部分是alphabetize方法，它返回一个串，这个串包含与它的参数相同的字符，并按字母顺序排列。这个例程（它与Collections Framework无关) 实现一个巧妙的桶式分类。它假定按字母顺序排列的单词完全由小写字母组成。
import java.util.*;
import java.io.*;
public class Perm {
public static void main(String[] args) {
int minGroupSize = Integer.parseInt(args[1]);
// Read words from file and put into simulated multimap
Map m = new HashMap();
try {
BufferedReader in =
new BufferedReader(new FileReader(args[0]));
String word;
while((word = in.readLine()) != null) {
String alpha = alphabetize(word);
List l = (List) m.get(alpha);
if (l==null)
m.put(alpha, l=new ArrayList());
l.add(word);
}
} catch(IOException e) {
System.err.println(e);
System.exit(1);
}
// Print all permutation groups above size threshold
for (Iterator i = m.values().iterator(); i.hasNext(); ) {
List l = (List) i.next();
if (l.size() $#@62; = minGroupSize)
System.out.println(l.size() + ": " + l);
}
}
private static String alphabetize(String s) {
int count[] = new int[256];
int len = s.length();
for (int i=0; i$#@60; len; i++)
count[s.charAt(i)]++;
StringBuffer result = new StringBuffer(len);
for (char c="a"; c$#@60; ="z"; c++)
for (int i=0; i$#@60; count[c]; i++)
result.append(c);
return result.toString();
}
}
java api接口篇（二)上(5)
时间:2010-12-24
在一台老式UltraSparc 1上运行一个有80,000个单词的词典用了大约16秒；最小排列组尺寸为8 。它生成了下列输出
% java Perm dictionary.txt 8
9: [estrin, inerts, insert, inters, niters, nitres, sinter,
triens, trines]
8: [carets, cartes, caster, caters, crates, reacts, recast, traces]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape, secpar,
spacer]
8: [ates, east, eats, etas, sate, seat, seta, teas]
12: [apers, apres, asper, pares, parse, pears, prase, presa, rapes,
reaps, spare, spear]
9: [anestri, antsier, nastier, ratines, retains, retinas, retsina,
stainer, stearin]
10: [least, setal, slate, stale, steal, stela, taels, tales,
|
