HashMap在Java开发中扮演着非常重要的角色，每个Java程序员都应该了解HashMap。详细讲解HashMap中的几个概念，深入探究HashMap的内部结构和实现细节，讨论HashMap的性能。我们先来看这样一道面试题：HashMap中存储的一系列键值对，其中key为自定义类型。放入HashMap后，我们在外部改变某个key的属性，然后我们使用这个key从HashMap中取出元素。这个时候HashMap会返回什么？文章中已经给出了示例代码和答案，但是没有给出HashMap原理的解释。1.特点我们可以使用任何类作为HashMap的key，但是对这些类有什么限制呢？看看下面的代码：world");testMap.get(newPerson("hello"));//--->null本来想取出字段值相等的Person类的值结果为null。对HashMap稍有了解的人都能看出来，Person类没有overridehashcode方法，导致它继承了Object的hashcode（返回的是它的内存地址）。这也是为什么不可变类如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;//你不能有泛型的物理数组，但是你可以upcasttoone:@SuppressWarnings("unchecked"MapEntry>[]buckets=newLinkedList[SIZE];publicVput(Kkey,Vvalue){VoldValue=null;intindex=Math.abs(key.hashCode())%SIZE;if(buckets[index]==null)桶[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);//用newfound=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){Si??mpleHashMapm=newSimpleHashMap();m.putAll(Countries.capitals(25));System.out.println(m);System.out.println(m.get("ERITREA"));System.out.println(m.entrySet());}}SimpleHashMap构造哈希表存储key，哈希函数为取模运算Math.abs(key.hashCode())%SIZE，使用链表方法解决hash冲突；桶的每个槽对应于存储具有相同（哈希后）索引值的Map.Entry，如下图所示：JDK的HashMap的实现原理与其类似。它使用链地址的哈希表来存储Map.Entry:/***Thetable,resizedasnecessary.LengthMUSTAAlwaysbeapoweroftwo.*/transientEntry[]table=(Entry[])EMPTY_TABLE;staticclassEntryimplementsMap.Entry{finalKkey;Vvalue;Entrynext;inthash;…}Map.Entry通过key的hashcode哈希得到索引。当要获取key对应的value时，为key计算其索引，然后从表中取出Map.Entry即可获取。具体见代码：publicVget(Objectkey){if(key==null)returngetForNullKey();Entryentry=getEntry(key);returnull==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;ee=e.next){Objectk;if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}returnull;}可见，hashcode直接影响到HashMap的哈希函数的效率——好的hashcode会大大减少哈希冲突，提高查询性能。同时这也解释了开头提出的两个问题：如果使用自定义类作为HashMap的key，hashcode的计算要覆盖构造函数的所有字段，否则有可能得到null。
