现在很多的Java程序员都会把HashMap当作一个热门话题今天我也来说一说Hashmap
我假设你对HashMap感兴趣另外我认为你已经了解了HashMap的基础这里我就不再赘述HashMap是个什么东东如果对于你来讲HashMap还是一个新概念的话你可以去看看官方的javadoc
目录
一句话回答
什么是哈希
关于Entry类的一点介绍
put()方法实际上做了什么
get()方法内部工作机制
注意点
一句话回答
如果任何人让我描述一下HashMap的工作机制的话我就简单的回答基于Hash的规则这句话非常简单但是要理解这句话之前首先我们得了解什么是哈希不是么？
什么是哈希
哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串用这个串来确定变量/对象的唯一性一个正确的哈希函数必须遵守这个准则
当哈希函数应用在相同的对象或者equal的对象的时候每次执行都应该返回相同的值换句话说两个相等的对象应该有相同的hashcode
注所有Java对象都从Object类继承了一个默认的hashCode()方法这个方法将对象在内存中的地址作为整数返回这是一个很好的hash实现他确保了不同的对象拥有不同的hashcode
关于Entry类的一点介绍
一个map的定义是一个映射键（key）到值（value）的对象非常简单对吧
所以在HashMap中一定有一定的机制来存储这些键值对使得HashMap有一个内部类Entry看起来像这样
staticclassEntry<KV>implementsMapEntry<KV>
{
finalKkey;
Vvalue;
Entry<KV>next;
finalinthash;
//Morecodegoeshere
}
当然Entry类有属性用来存储键值对映射key被final标记除了key和value我们还能看到两个变量next和hash接下来我们试着理解这些变量的含义
put()方法实际上做了什么
再进一步看put方法的实现之前我们有必要看一看Entry实例在数组中的存储HashMap中是这样定义的
/**
*ThetableresizedasnecessaryLengthMUSTAlwaysbeapoweroftwo
*/
transientEntry[]table;
现在再来看put方法的实现
/**
*Associatesthespecifiedvaluewiththespecifiedkeyinthismap
*Ifthemappreviouslycontainedamappingforthekeytheold
*valueisreplaced
*
*@paramkeykeywithwhichthespecifiedvalueistobeassociated
*@paramvaluevaluetobeassociatedwiththespecifiedkey
*@returnthepreviousvalueassociatedwith<tt>key</tt>or
* <tt>null</tt>iftherewasnomappingfor<tt>key</tt>
* (A<tt>null</tt>returncanalsoindicatethatthemap
* previouslyassociated<tt>null</tt>with<tt>key</tt>)
*/
publicVput(KkeyVvalue){
if(key==null)
returnputForNullKey(value);
inthash=hash(keyhashCode());
inti=indexFor(hashtablelength);
for(Entry<KV>e=table[i];e!=null;e=enext){
Objectk;
if(ehash==hash&&((k=ekey)==key||keyequals(k))){
VoldValue=evalue;
evalue=value;
erecordAccess(this);
returnoldValue;
}
}
modCount++;
addEntry(hashkeyvaluei);
returnnull;
}
让我们一步一步的看
首先检查key是否为null如果key是null值被存在table[]的位置因为null的hashcode始终为接下来通过key的hashCode()方法计算了这个key的hash值这个hash值被用来计算存储Entry对象的数组中的位置JDK的设计者假设会有一些人可能写出非常差的hashCode()方法会出现一些非常大或者非常小的hash值为了解决这个问题他们引入了另外一个hash函数接受对象的hashCode()并转换到适合数组的容量大小
接着是indexFor(hashtablelength)方法这个方法计算了entry对象存储的准确位置
接下来就是主要的部分我们都知道两个不相等的对象可能拥有过相同的hashCode值两个不同的对象是怎么存储在相同的位置[叫做bucket]呢？
答案是LinkedList如果你记得Entry类有一个next变量这个变量总是指向链中的下一个变量这完全符合链表的特点
所以在发生碰撞的时候entry对象会被以链表的形式存储起来当一个Entry对象需要被存储的时候hashmap检查该位置是否已近有了一个entry对象如果没有就存在那里如果有了就检查她的next属性如果是空当前的entry对象就作为已经存储的entry对象的下一个节点依次类推
如果我们给已经存在的key存入另一个value会怎么样的？逻辑上旧的值将被替换掉在检测了Entry对象的存储位置后hashmap将会遍历那个位置的entry链表对每一个entry调用equals方法这个链表中的所有对象都具有相同的hashCode()而equals方法都不等如果发现equals方法有相等的就执行替换
在这种方式下HashMap就能保证key的唯一性
get方法的工作机制
现在我们已经了解了HashMap中存储键值对的机制下一个问题是怎样从一个HashMap中查询结果
其实逻辑跟put是一样的如果传入的key有匹配就将该位置的value返回如果没有就返回null
/**
*Returnsthevaluetowhichthespecifiedkeyismapped
*or{@codenull}ifthismapcontainsnomappingforthekey
*
*<p>Moreformallyifthismapcontainsamappingfromakey
*{@codek}toavalue{@codev}suchthat{@code(key==null?k==null:
*keyequals(k))}thenthismethodreturns{@codev};otherwise
*itreturns{@codenull} (Therecanbeatmostonesuchmapping)
*
*<p>Areturnvalueof{@codenull}doesnot<i>necessarily</i>
*indicatethatthemapcontainsnomappingforthekey;itsalso
*possiblethatthemapexplicitlymapsthekeyto{@codenull}
*The{@link#containsKeycontainsKey}operationmaybeusedto
*distinguishthesetwocases
*
*@see#put(ObjectObject)
*/
publicVget(Objectkey){
if(key==null)
returngetForNullKey();
inthash=hash(keyhashCode());
for(Entry<KV>e=table[indexFor(hashtablelength)];
e!=null;
e=enext){
Objectk;
if(ehash==hash&&((k=ekey)==key||keyequals(k)))
returnevalue;
}
returnnull;
}
上面的代码看起来跟put()方法很像除了if (ehash == hash && ((k = ekey) == key || keyequals(k)))
注意点
存储Entry对象的数据结构是一个叫做Entry类型的table数组
数组中一个特定的索引位置称为bucket因为它可以容纳一个LinkedList的第一个元素的对象
Key对象的hashCode()需要用来计算Entry对象的存储位置
Key对象的equals()方法需要用来维持Map中对象的唯一性
get()和put()方法跟Value对象的hashCode和equals方法无关
null的hashCode总是这样的Entry对象总是被存储在数组的第一个位置
