郭颂歌曲:STL map

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

Map是标准关联式容器（associative container）之一，一个map是一个键值对序列，即（key ,value）对。它提供基于key的快速检索能力，在一个map中key值是唯一的。map提供双向迭代器，即有从前往后的（iterator），也有从后往前的（reverse_iterator）。

map要求能对key进行<操作，且保持按key值递增有序，因此map上的迭代器也是递增有序的。如果对于元素并不需要保持有序，可以使用hash_map。

1. public class Problem_3 {   
2.        
3.     //先快速排序后循环查找    O( n*log2(n) + n )   
4.     public static void find1(int[] arr){   
5.            
6.         QuickSort.sort(arr);   
7.            
8.            
9.         int max = arr[0];   
10.         int pre=1;   
11.         int now=1;   
12.            
13.         for(int i=0;i<(arr.length-1);i++){   
14.                
15.             if(arr[i]==arr[i+1])   
16.                 now++;   
17.             else {   
18.                 if(now>=pre){   
19.                     pre=now;   
20.                     now=1;   
21.                     max=arr[i];   
22.                 }      
23.             }   
24.         }   
25.            
26.            
27.            
28.     }   
29.        
30.     //嵌套循环查找   O(n*n)   
31.     public static void find2(int[] arr){   
32.            
33.   
34.         int pre=0;   
35.         int max=arr[0];   
36.            
37.         for(int i=0;i
38.             int now=0;   
39.             for(int j=0;j
40.                    
41.                 if(arr[i]==arr[j]) {   
42.                     now++;     
43.                 }                  
44.             }   
45.                
46.             if(now>=pre){               
47.                 max=arr[i];   
48.                 pre=now;               
49.             }   
50.                
51.                        
52.         }   
53.            
54.        
55.            
56.     }   
57.        
58.     //通过 Hash 方式   
59.     public static void find3(int[] arr){   
60.         HashMap hm=new HashMap();   
61.         for(int i=0;i
62.             if(hm.containsKey(arr[i])) {   
63.                 int count=hm.get(arr[i]);   
64.                 hm.put(arr[i], ++count);   
65.                 
66.             }else{   
67.                 hm.put(arr[i],1);   
68.             }   
69.         }   
70.            
71.         Iterator> it=hm.entrySet().iterator();   
72.         int pre=0;   
73.         int max=arr[0];   
74.         while(it.hasNext()) {   
75.             Entry en=it.next();   
76.             int key=en.getKey();   
77.             int val=en.getValue();   
78.             if(val>pre){    
79.                 pre=val;   
80.                 max=key;   
81.             }   
82.                
83.         }   
84.            
85.        
86.            
87.     }   
88.     public static  void main(String args[]){   
89.   
90.         //数据量800 重复元素多，查找时候分别是：  46  3680  195   
91.         int arr2[]={0,1,2,        .....          
92.                 ,0,1,2,3,6,7,8,9};   
93.            
94.         //数据量800 重复元素少，查找时间分别是     82  3727  360   
95.         int arr[]={0,0,0,11,12,13,14,5,6    ......        
96.                         ,51,52,53,,728,29,730,731,3,794,95,796,797,798,799};   
97.            
98.   
99.            
100.         long start,end;   
101.                
102.         start=System.currentTimeMillis();   
103.         for(int i=0;i<1000;i++) find1(arr);   
104.         end=System.currentTimeMillis();   
105.         System.out.println(end-start);   
106.            
107.         start=System.currentTimeMillis();   
108.         for(int i=0;i<1000;i++) find2(arr);   
109.         end=System.currentTimeMillis();   
110.         System.out.println(end-start);   
111.            
112.            
113.         start=System.currentTimeMillis();   
114.         for(int i=0;i<1000;i++) find3(arr);   
115.         end=System.currentTimeMillis();   
116.         System.out.println(end-start);   
117.            
118.     }   
119. }  

大家都知道在C++的STL中map是使用树来做查找算法，而hash_map使用hash表来排列配对，是使用关键字来计算表位置。那使用起来他们的差别主要是什么呢？对于性能差别是什么，适合什么情况下应用呢？于是我对它们进行了一些测试，并记录了测试数据供大家分享。
    测试的内容主要是map和hash_map的添加、删除、查找和遍历操作，首先进行了几组测试，分别是10万次、30万次，时间单位均为毫秒，具体的性能对照如下：
  hash_map（10万） map（10万） hash_map（20万） map（20万） hash_map（30万） map（30万）
添加 93   47  156   94  203   172
遍历 16   15  16   16  16   15
查找 0   0  32   31  31   32
删除 8422   32  33765   63  76016   78
    通过上面的数据比较，我们很容易发现hash_map的添加和删除操作比map要慢，尤其是删除操作hash_map比map可能慢1000倍；从而得到结论是删除和插入操作较多的情况下，map比hash_map的性能更好，添加和删除的数据量越大越明显。但我们使用map、hash_map一般都用于查找和遍历较多，而且上述测试数据也不能反映出这两方面的性能差距，于是继续对查找和遍历进行了性能测试，得到具体数据如下，时间单位仍为毫秒：
 hash_map（100万） map（100万） hash_map（200万） map（200万） hash_map（300万） map（300万）
遍历 94   31  203   32  297   47
查找 94   234  188   531  281   875
    通过上面的测试数据可以得出结论是map的遍历性能高于hash_map，而查找性能则相反，hash_map比map要好，数据量越大查找次数越多，表现就越好。
    两大组测试完毕，整体结论也可以得出：一般应用情况下，我们保存的数据不超过100万份，查找的频繁程度不高情况下使用map性能比较好；而保存的数据较多时（超过100万），查找频繁时使用hash_map的性能就高于map了。

测试环境具体如下：
操作系统：Windows XP Professional (5.1, Build 2600) Service Pack 3 (2600.xpsp_sp3_gdr.080814-1236)
编译环境：Microsoft Visual C++ 2005   55603-007-4000003-41525
处理器：Intel(R) Core(TM)2 Duo CPU     P8600  @ 2.40GHz (2 CPUs)
内存：2044MB RAM，
     另外，整个测试仅使用物理内存，而没有虚拟内存，使用Release版本直接在控制台中运行，而没有在IDE中运行，避免影响性能；且对于较短时间计时，少于20毫秒以下可能不准确。