2012年软考软件设计师辅导之JavaHashMap分析基本结构

会计考友

Java的HashMap非常的常用，本篇研究它的实现算法，最后希望计算出内存占用，性能的量化数据，然后得出什么时候使用HashMap，什么时候不能滥用的结论。 　　HashMap实际上是一个数组，数组里面的每个元素都是一个链表。每个元素在通过put方法放入HashMap中的时候，要按照如下步骤进行：1.根据该元素自身提供的hashcode计算出散列值，该散列值就是数组的下标2.将新元素放入该数组位置的链表中先来看一下数组的定义：[java]viewplaincopy/***Thetable，resizedasnecessary.LengthMUSTAlwaysbeapoweroftwo.*/transientEntry[]table；
　　这是一个数组，transient关键字告诉我们它不会参与序列化。既然是一个数组，总有数目上限，也就意味着如果存入HashMap的元素太多，导致数组大小不能够存放所有的链表的时候，数组大小必须要能够调整。所以首先来考察一下数组容量的相关算法。
& y: H2 H! P' {3 O7 n　　第一，Entry是什么类型？
0 \7 `1 h2 [3 A  Q. T# U
　　 [java]viewplaincopystaticclassEntryimplementsMap.Entry{finalKkey；Vvalue；Entrynext；finalinthash；
7 W; d8 f( n- O  u' J　　 /***Createsnewentry.*/Entry（inth，Kk，Vv，Entryn）{value=v；next=n；key=k；hash=h；}…… 　　 publicfinalbooleanequals（Objecto）{if（！（oinstanceofMap.Entry））
　　 returnfalse；Map.Entrye=（Map.Entry）o；Objectk1=getKey（）；Objectk2=e.getKey（）；if（k1==k2||（k1！=null&&k1.equals（k2）））{Objectv1=getValue（）；Objectv2=e.getValue（）；if（v1==v2||（v1！=null&&v1.equals（v2）））
- N/ X/ ~. `: f1 Q7 C/ M1 D　　 returntrue；}returnfalse；}
* @$ S* s: a) g1 Q: B　　 publicfinalinthashCode（）{return（key==null？0：key.hashCode（））^（value==null？0：value.hashCode（））；}……
　　这是一个HashMap类的内部静态类。实现了Map.Entry接口。接受两个模板参数K和V.key和hash一旦在构造函数中被初始化，就不可改变，并且由于有next的存在，Entry可以构成一个单向链表。
& b& p1 m: T- R% R　　比较重要的是equals和hashCode方法。代码先列出来，后面再解释。
　　第二，初始容量的设定大多数都在下面的构造函数里面。用于指定的initialCapacity不准小于0，也不能超过最大值。并且最终的capicity必须是2的n次方。还有如果使用了无参数的构造函数，默认会创建一个拥有16个元素的数组。
' g7 i: `  I0 G8 ?7 \3 i/ n　　 [java]viewplaincopypublicHashMap（intinitialCapacity，floatloadFactor）{if（initialCapacityMAXIMUM_CAPACITY）
% x" o! F+ w" I8 E% q% b
1 L# {) \& [8 o, M　　 initialCapacity=MAXIMUM_CAPACITY；if（loadFactor=initialCapacityintcapacity=1；while（capacity