Java中对HashMap的深度阐明与较量
在Java的世界里，无论类照旧各类数据，其布局的处理惩罚是整个措施的逻辑以及机能的要害。由于本人打仗了一个有关机能与逻辑同时并存的问题，于是就开始研究这方面的问题。找遍了大巨细小的论坛，也把《Java 虚拟机类型》，《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》，和《Thinking in Java》翻了也找不到很好的谜底，于是一气之下把JDK的 src 解压出来研究，扩然开朗，遂写此文，跟各人分享感觉温顺便验证我领略尚有没有裂痕。 这里就拿HashMap来研究吧。
HashMap可谓JDK的一大实用东西，把各个Object映射起来，实现了“键－－值”对应的快速存取。但实际内里做了些什么呢？
在这之前，先先容一下负载因子和容量的属性。各人都知道其实一个 HashMap 的实际容量就 因子*容量，其默认值是 16×0.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[i]; 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; //没有沟通的键值返回
}
我们把要害的要领拿出来阐明：
void addEntry(int hash, Object key, Object value, int bucketIndex) {
table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);
因为 hash 的算法有大概令差异的键值有沟通的hash码并有沟通的table索引，如：key＝“33”和key＝Object g的hash都是－8901334，那它颠末indexfor之后的索引必然都为i，这样在new的时候这个Entry的next就会指向这个原本的table[i]，再有下一个也如此，形成一个链表，和put的轮回对定e.next得到旧的值。到这里，HashMap的布局，各人也十分大白了吧？
if (size++ >= threshold) //这个threshold就是能实际容纳的量
resize(2 * table.length); //超出这个容量就会将Object table重构
所谓的重构也不神，就是建一个两倍大的table（我在此外论坛上看到有人说是两倍加1，把我骗了），然后再一个个indexfor进去！留意！！这就是效率！！假如你能让你的HashMap不需要重构那么多次，效率会大大提高！
说到这里也差不多了，get比put简朴得多，各人，相识put，get也差不了几多了。对付collections我是认为，它是适合遍及的，当不完全适合特有的，假如各人的措施需要非凡的用途，本身写吧，其实很简朴。（作者是这样跟我说的，他还发起我用LinkedHashMap,我看了源码今后发明，LinkHashMap其实就是担任HashMap的，然后override相应的要领，有乐趣的同人，本身looklook）建个 Object table，写相应的算法，就ok啦。
#p#分页标题#e#
举个例子吧，像 Vector，list 啊什么的其实都很简朴，最多就多了的同步的声明，其实假如要实现像Vector那种，插入，删除不多的，可以用一个Object table来实现，按索引存取，添加等。
假如插入，删除较量多的，可以建两个Object table，然后每个元素用含有next布局的，一个table存，假如要插入到i，可是i已经有元素，用next连起来，然后size＋＋，并在另一个table记录其位置。
