众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干

1. 特性

我们可以用任何类作为HashMap的key，但是对于这些类应该有什么限制条件呢？且看下面的代码：

publicclassPerson{privateStringname;publicPerson(Stringname){this.name=name;}}MaptestMap=newHashMap();testMap.put(newPerson("hello"),"world");testMap.get(newPerson("hello"));//--->null

本是想取出具有相等字段值Person类的value，结果却是null。对HashMap稍有了解的人看出来——Person类并没有override hashcode方法，导致其继承的是Object的hashcode（返回是其内存地址），两次new出来的Person对象并不equals——这也是为什么在工程项目中常用不变类（如String、Integer等）做为HashMap的key的原因。那么，HashMap是如何利用hashcode给key做索引的呢？

2. 原理

首先，我们来看《Thinking in Java》中一个简单HashMap的实现方案：

//:containers/SimpleHashMap.java//AdemonstrationhashedMap.importjava.util.*;importnet.mindview.util.*;publicclassSimpleHashMapextendsAbstractMap{//Chooseaprimenumberforthehashtablesize,toachieveauniformdistribution:staticfinalintSIZE=997;//Youcan'thaveaphysicalarrayofgenerics,butyoucanupcasttoone:@SuppressWarnings("unchecked")LinkedList>[]buckets=newLinkedList[SIZE];publicVput(Kkey,Vvalue){VoldValue=null;intindex=Math.abs(key.hashCode())%SIZE;if(buckets[index]==null)buckets[index]=newLinkedList>();LinkedList>bucket=buckets[index];MapEntrypair=newMapEntry(key,value);booleanfound=false;ListIterator>it=bucket.listIterator();while(it.hasNext()){MapEntryiPair=it.next();if(iPair.getKey().equals(key)){oldValue=iPair.getValue();it.set(pair);//Replaceoldwithnewfound=true;break;}}if(!found)buckets[index].add(pair);returnoldValue;}publicVget(Objectkey){intindex=Math.abs(key.hashCode())%SIZE;if(buckets[index]==null)returnnull;for(MapEntryiPair:buckets[index])if(iPair.getKey().equals(key))returniPair.getValue();returnnull;}publicSet>entrySet(){Set>set=newHashSet>();for(LinkedList>bucket:buckets){if(bucket==null)continue;for(MapEntrympair:bucket)set.add(mpair);}returnset;}publicstaticvoidmain(String[]args){SimpleHashMapm=newSimpleHashMap();m.putAll(Countries.capitals(25));System.out.println(m);System.out.println(m.get("ERITREA"));System.out.println(m.entrySet());}}

SimpleHashMap构造一个hash表来存储key，hash函数是取模运算Math.abs(key.hashCode()) % SIZE，采用链表法解决hash冲突；buckets的每一个槽位对应存放具有相同（hash后）index值的Map.Entry，如下图所示： JDK的HashMap的实现原理与之相类似，其采用链地址的hash表table存储Map.Entry：

/***Thetable,resizedasnecessary.LengthMUSTAlwaysbeapoweroftwo.*/transientEntry[]table=(Entry[])EMPTY_TABLE;staticclassEntryimplementsMap.Entry{finalKkey;Vvalue;Entrynext;inthash;…}

Map.Entry的index是对key的hashcode进行hash后所得。当要get key对应的value时，则对key计算其index，然后在table中取出Map.Entry即可得到，具体参看代码：

publicVget(Objectkey){if(key==null)returngetForNullKey();Entryentry=getEntry(key);returnnull==entry?null:entry.getValue();}finalEntrygetEntry(Objectkey){if(size==0){returnnull;}inthash=(key==null)?0:hash(key);for(Entrye=table[indexFor(hash,table.length)];e!=null;e=e.next){Objectk;if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}returnnull;}

可见，hashcode直接影响HashMap的hash函数的效率——好的hashcode会极大减少hash冲突，提高查询性能。同时，这也解释开篇提出的两个问题：如果自定义的类做HashMap的key，则hashcode的计算应涵盖构造函数的所有字段，否则有可能得到null。