2008-03-22

解读java.util.HashMap

HashMap 的实际容量就 因子*容量，其默认值是 16×0.75＝12；当存入HashMap的对象超过这个容量时，HashMap 就会重新构造存取表。这就是一个大问题.


put方法

Object k = maskNull(key);

这个就是判断键值是否为空，其实如果为空，它会返回一个static Object 作为键值，这就是为什么HashMap允许空键值的原因。

int hash = hash(k);

int i = indexFor(hash, table.length);

其中 hash 就是通过 key 这个Object的 hashcode 进行 hash，然后通过 indexFor 获得在Object 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，然后再一个个indexfor进去！注意！！这就是效率！！如果你能让你的HashMap不需要重构那么多次，效率会大大提高！

评论
发表评论

您还没有登录，请登录后发表评论

Azi
搜索本博客
存档
最新评论