Java语言中对HashMap的深度分析与比较

[Erika]

HashMap可谓JDK的一大实用工具，把各个Object映射起来，实现了“键--值”对应的快速存取。但实际里面做了些什么呢?

　　在这之前，先介绍一下负载因子和容量的属性。大家都知道其实一个 HashMap 的实际容量就 因子*容量，其默认值是 16?.75=12; 这个很重要，对效率很一定影响!当存入HashMap的对象超过这个容量时，HashMap 就会重新构造存取表。这就是一个大问题，我后面慢慢介绍，反正，如果你已经知道你大概要存放多少个对象，最好设为该实际容量的能接受的数字。

　　两个关键的方法，put和get：

　　先有这样一个概念，HashMap是声明了 Map，Cloneable, Serializable 接口，和继承了 AbstractMap 类，里面的 Iterator 其实主要都是其内部类HashIterator 和其他几个 iterator 类实现，当然还有一个很重要的继承了Map.Entry 的 Entry 内部类，由于大家都有源代码，大家有兴趣可以看看这部分，我主要想说明的是 Entry 内部类。它包含了hash，value，key 和next 这四个属性，很重要。put的源码如下　　 public Object put(Object key, Object value) {
　　Object k = maskNull(key);


　　这个就是判断键值是否为空，并不很深奥，其实如果为空，它会返回一个static Object 作为键值，这就是为什么HashMap允许空键值的原因。　　 int hash = hash(k);
　　int i = indexFor(hash, table.length);
　　这连续的两步就是 HashMap 最牛的地方!研究完我都汗颜了，其中 hash 就是通过 key 这个Object的 hashcode 进行 hash，然后通过 indexFor 获得在Object table的索引值。

　　table???不要惊讶，其实HashMap也神不到哪里去，它就是用 table 来放的。最牛的就是用 hash 能正确的返回索引。其中的hash算法，我跟JDK的作者 Doug 联系过，他建议我看看《The art of programing vol3》可恨的是，我之前就一直在找，我都找不到，他这样一提，我就更加急了，可惜口袋空空啊!!!

　　不知道大家有没有留意 put 其实是一个有返回的方法，它会把相同键值的 put 覆盖掉并返回旧的值!如下方法彻底说明了 HashMap 的结构，其实就是一个表加上在相应位置的Entry的链表：　　

for (Entry e = table; e != null; e = e.next) {
　　if (e.hash == hash && eq(k, e.key)) {
　　Object oldvalue = e.value;
　　e.value = value; //把新的值赋予给对应键值。
　　e.recordAccess(this); //空方法，留待实现
　　return oldvalue; //返回相同键值的对应的旧的值。
　　}
　　}
　　modCount++; //结构性更改的次数
　　addEntry(hash, k, value, i); //添加新元素，关键所在!
　　return null; //没有相同的键值返回
　　}