淘宝2012校招技术笔试题

实现五：统计一个单词可重复的英文文件（假设4G）中每个单词出现的次数，把结果按照英文排序放入一个文件中。并能够检索特定单词的出现次数。由于文件过大，不重复单词总数有限，需要考虑到执行速度和内存使用情况。（淘宝笔试技术题）

[java] view plain copy print?

1. import java.io.File;  
2. import java.io.FileNotFoundException;  
3. import java.io.FileOutputStream;  
4. import java.io.IOException;  
5. import java.io.RandomAccessFile;  
6. import java.nio.ByteBuffer;  
7. import java.nio.MappedByteBuffer;  
8. import java.nio.channels.FileChannel;  
9. import java.nio.channels.FileLock;  
10. import java.nio.charset.Charset;  
11. import java.util.HashMap;  
12. import java.util.Map;  
13. import java.util.StringTokenizer;  
14. import java.util.TreeMap;  
15.   
16. public class TestCountWords {  
17.     public static void main(String[] args) {  
18.         File wf = new File("words.txt");  
19.         final CountWords cw1 = new CountWords(wf, 0, wf.length()/2);  
20.         final CountWords cw2 = new CountWords(wf, wf.length()/2, wf.length());  
21.         final Thread t1 = new Thread(cw1);  
22.         final Thread t2 = new Thread(cw2);  
23.         //开辟两个线程分别处理文件的不同片段  
24.         t1.start();  
25.         t2.start();  
26.         Thread t = new Thread() {  
27.             public void run() {  
28.                 while(true) {  
29.                     //两个线程均运行结束  
30.                     if(Thread.State.TERMINATED==t1.getState() && Thread.State.TERMINATED==t2.getState()) {  
31.                         //获取各自处理的结果  
32.                         HashMap<String, Integer> hMap1 = cw1.getResult();  
33.                         HashMap<String, Integer> hMap2 = cw2.getResult();  
34.                         //使用TreeMap保证结果有序  
35.                         TreeMap<String, Integer> tMap = new TreeMap<String, Integer>();  
36.                         //对不同线程处理的结果进行整合  
37.                         tMap.putAll(hMap1);  
38.                         tMap.putAll(hMap2);  
39.                         //打印输出，查看结果  
40.                         for(Map.Entry<String,Integer> entry : tMap.entrySet()) {  
41.                             String key = entry.getKey();    
42.                             int value = entry.getValue();    
43.                             System.out.println(key+":\t"+value);    
44.                         }  
45.                         //将结果保存到文件中  
46.                         mapToFile(tMap, new File("result.txt"));  
47.                     }  
48.                     return;  
49.                 }  
50.             }  
51.         };  
52.         t.start();  
53.     }  
54.     //将结果按照 "单词：次数" 格式存在文件中  
55.     private static void mapToFile(Map<String, Integer> src, File dst) {  
56.         try {  
57.             //对将要写入的文件建立通道  
58.             FileChannel fcout = new FileOutputStream(dst).getChannel();  
59.             //使用entrySet对结果集进行遍历  
60.             for(Map.Entry<String,Integer> entry : src.entrySet()) {  
61.                 String key = entry.getKey();  
62.                 int value = entry.getValue();  
63.                 //将结果按照指定格式放到缓冲区中  
64.                 ByteBuffer bBuf = ByteBuffer.wrap((key+":\t"+value).getBytes());  
65.                 fcout.write(bBuf);  
66.                 bBuf.clear();  
67.             }  
68.         } catch (FileNotFoundException e) {  
69.             e.printStackTrace();  
70.         } catch (IOException e) {  
71.             e.printStackTrace();  
72.         }  
73.     }  
74. }  
75.   
76. class CountWords implements Runnable {  
77.       
78.     private FileChannel fc;  
79.     private FileLock fl;  
80.     private MappedByteBuffer mbBuf;  
81.     private HashMap<String, Integer> hm;  
82.       
83.     public CountWords(File src, long start, long end) {  
84.         try {  
85.             //得到当前文件的通道  
86.             fc = new RandomAccessFile(src, "rw").getChannel();  
87.             //锁定当前文件的部分  
88.             fl = fc.lock(start, end, false);  
89.             //对当前文件片段建立内存映射，如果文件过大需要切割成多个片段  
90.             mbBuf = fc.map(FileChannel.MapMode.READ_ONLY, start, end);  
91.             //创建HashMap实例存放处理结果  
92.             hm = new HashMap<String,Integer>();  
93.         } catch (FileNotFoundException e) {  
94.             e.printStackTrace();  
95.         } catch (IOException e) {  
96.             e.printStackTrace();  
97.         }  
98.     }  
99.     @Override  
100.     public void run() {  
101.         String str = Charset.forName("UTF-8").decode(mbBuf).toString();  
102.         //使用StringTokenizer分析单词  
103.         StringTokenizer token = new StringTokenizer(str);  
104.         String word;  
105.         while(token.hasMoreTokens()) {  
106.             //将处理结果放到一个HashMap中，考虑到存储速度  
107.             word = token.nextToken();  
108.             if(null != hm.get(word)) {  
109.                 hm.put(word, hm.get(word)+1);  
110.             } else {  
111.                 hm.put(word, 1);  
112.             }  
113.         }  
114.         try {  
115.             //释放文件锁  
116.             fl.release();  
117.         } catch (IOException e) {  
118.             e.printStackTrace();  
119.         }  
120.         return;  
121.     }  
122.       
123.     //获取当前线程的执行结果  
124.     public HashMap<String, Integer> getResult() {  
125.         return hm;  
126.     }  
127. }  

以上代码是我自己实现的，主要思想是：

1.使用具有键值对结构的HashMap来快速存取；

2.由于文件过大，用一个线程处理可能结果较慢，使用到并发机制；

3.IO操作比较耗时，所以使用了nio的相关内容；

4.最终结果要有序的话，可以使用TreeMap。

望同行给予批评指导，相信有更好的解决办法和思路，如果能帮着优化以上代码，请给予留言，或者发邮件至bluesky_taotao@163.com，真诚欢迎各位编程爱好者与我讨论相关技术问题。