蚂蚁小窝

haohao提了一个问题，给人第一感觉是要作1000万＊100万，即10万亿次的查找运算，有些吓人。因此，haohao说，要“分析时间复杂度和空间复杂度”。
我对算法是外行，只有些二分查找的概念。
数组，二分查找。
后来想，java 已经10多岁了，我能想到的这些简单的算法，java早就封装得很好了。比如，Hashtable，查找效率如何呢？
copy一个小程序测测：

ackage zdu.filter;

import java.util.*;

public class TestHashtable {

	 public static void main(String[] args) {
	   Hashtable aHashtable=new Hashtable();
	   Vector aVector=new Vector();
	   
	      long t1 = System.currentTimeMillis();
	   System.out.println("开始：:"+t1);
	   for(int i=0;i<1000000;i++){
	     aVector.addElement("论语"+i);  
	     aHashtable.put(aVector.get(i),i);
	   }
	   long t2 = System.currentTimeMillis();
	   System.out.println("数据准备完毕:"+t2);
	     long t3 = t2-t1;
	   System.out.println("数据准备用时:"+t3+"毫秒");
	   long t4 = System.currentTimeMillis();
	   
	   System.out.println("Key:"+aHashtable.get("论语556677"));
	   System.out.println("Key2:"+aHashtable.get("论语116677"));
	   System.out.println("Key3:"+aHashtable.get("论语886633"));
	   System.out.println("Key4:"+aHashtable.get("论语336655"));
	   System.out.println("Key5:"+aHashtable.get("论语96633"));
	   long t5 = System.currentTimeMillis();
	       long t6 = t5-t4;
	   System.out.println("查找用时："+t6+"毫秒");
	 }

	}

在eclipse里直接run一下，结果吓我一跳：
开始：:1179339369314
数据准备完毕:1179339371227
数据准备用时:1913毫秒
Key:556677
Key2:116677
Key3:886633
Key4:336655
Key5:96633
查找用时：1毫秒

在100万记录中任意查5条，竟然总共用了不到1毫秒。
内存？几乎没有可以感觉到的消耗。
空间复杂度与时间复杂度，对100万条记录的查询，根本不是问题。