-----数组结构
首先，说一下HashMap最重要的一个内部类 Entry<K,V> ,它实现了Map.Entry 接口，对于HashMap来说，Entry是非常重要的数据结构，其所有的数据都是以Entry的形式存储的。值得一提的是，HashMap的底层数据是Entry[] 数据。
-----链条节点（entry）的加挂方式
仔细看一下Entry就可以知道，每个Entry的next属性可以存储下一个Entry对象的引用，因此它是可以链起来的，像拴狗的链子那样。并且要注意的是，每次新建Entry，不是将新的Entry挂在链条的最后边，而是将当前的bucket 里的整条链挂到新建的Entry对象上。这不难理解，如果要将新对象挂到链条的末端，需要迭代整条链子，找到末端对象才能向链尾追加，而将整条链挂到新对象上就容易多了，直接操作即可。
-----计算当前Entry应该存放的bucket（位置）
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
&运算避免了数组越界异常。两个数的&运算结果的最大值是两者的最小值。之所以数组长度要保证是2的非零幂数，或是为了减少碰撞。从这个角度就可以知道，扩容一定是扩容2倍 ，以保证数组长度是2的幂数。(Hashtable 的索引计算方式是： int index = (hash &0x7FFFFFFF) % tab.length;这里是取余算法，直接对数组长度取余，当然也避免了数组越界。通过两者避免数组越界的方式可以帮助体会这两种风格的不同点)。
通过这个找位置的算法可以看出，许多Entry对象是有机会共用同一个bucket并链在一起的，条件是调用该方法时返回相同的值。由于null的hashCode 在HashMap中强制为0，那么键值为null的Entry对象指定放在第一个bucket里，即Entry[0]。但是并不保证null键值的entry一定在链条的首位置，理论上讲它可能在链条的任何位置。从源码中也可以揣测到这一点（遍例去找，而不是锁定首节点）：
private V getForNullKey() {
if (size == 0) { return null; }
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
网友评论