深入理解HashMap(一)

以前学习HahsMap都是粗略的了解一下，能够用就行了。这次对HahsMap的源代码看了几遍，对此有一定的理解，就我的理解我总结出如下几点。但在此之前，我们先说下HahsMap的结构，简单来说：HahsMap其实是一个数组和链表的结合体。
第一、首先对HahsMap的初始容量（也即DEFAULT_INITIAL_CAPACITY）来说个事，看下面的代码吧：

public class TestHashMap {
	public static void main(String[] args) {
		HashMap<Integer, Integer> hm1=new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> hm2=new HashMap<Integer, Integer>(1024<<7);
		long time1=System.currentTimeMillis();  
		for(int i=0;i<100000;i++){
			hm1.put(i, i);
		}
		long time2=System.currentTimeMillis();  
		long time3=System.currentTimeMillis();  
		for(int i=0;i<100000;i++){
			hm2.put(i, i);
		}
		long time4=System.currentTimeMillis(); 
		System.out.println("默认初始容量8所用时间为："+(time2-time1));
		System.out.println("定义初始容量131072所用时间为："+(time4-time3));
	}
}

程序运行的结果为：默认初始容量8所用时间为：94
               定义初始容量131072所用时间为：47
可以看出，第二种方法所用时间基本上是前面的一半，这是为什么呢？其实，HashMap的rehash是一个非常消耗性能的操作，rehash的次数越多，所消耗的时间也就越长。当插入100000个元素时，使用初始容量rehash的次数会很多，而根据（100000）/0.75=133333（0.75是HashMap的默认装填因子），也即是说第二种方法只要rehash一次即可，所以消耗的时间会大大减少。
第二、HashMap的装填因子，按如上代码，我们稍做修改，把定义的hm1和hm2修改成如下：

HashMap<Integer, Integer> hm1=new HashMap<Integer, Integer>(1024<<7,1);
		HashMap<Integer, Integer> hm2=new HashMap<Integer, Integer>(1024<<7);

在此运行，结果为：定义装填因子为1所用时间为：47
               默认装填因子为0.75所用时间为：62
在这里，我们循环插入100000个数据，但根据HashMap中的hash()函数，基本呈均匀分布，这样，没有什么冲突，那当然是装满更好，插入的效率会提高。但并不是装填因子越大越好，因为我们并不知道插入的数据是不是接近于均匀分布，如果不是的话，那么冲突会很大，查询的效率就会降低，装填因子太小也不好，因为这样会很浪费空间。所以HashMap默认的装填因子取了个折中的数0.75。
小结下：装填因子衡量的是一个散列表的空间使用程度，装填因子越大表示散列表的装填程度越高，反之越小。我们知道对一个链表法的散列表来说，查询一个元素的平均时间为O(1+a),因此，如果装填因子越大，对空间的利用更充分，然而查询效率就会降低；如果装填因子过小，那么散列表的数据就过于稀疏，对空间造成严重的浪费。
总结下：如果你知道所要插入的数据的个数N，那么你可以定义HashMap的容量大小为：N/0.75,有因为HashMap的容量必须是2的幂次方，找一个接近的即可；如果你还知道其近似一个均匀分布的话，那么装填因子也可以自己定义，接近于1会更效率。