java2集合框架的一些个人分析和理解(三)
next = n;
key = k;
hash = h;
}
同List一样，在其内部也维护叫size的变量，保存元素个数。在new HashMap()的时候，table数组是空的，一旦put则会扩容，
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
初始扩容的容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
，在扩容的过程中同时会计算下次扩容的阈值threshold，它=数组大小*负载因子。为什么在达到threshold的时候扩容而不是在达到数组最大长度的时候？这是为了减少每个数组元素上的Entry数，因为根据hash()方法，在把table数组占满之前，很可能在其他元素上已经有多个了(从概率角度)，但负载因子又不能太小，否则会造成很多空间浪费，所以作者权衡(这里可能也是根据hash()或某些数学原理)取0.75作为负载因子，即达到table数组3/4时就扩容，并且是扩容2倍，不是ArrayList那样扩容一半
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
其原因和hash的算法有关。为了提高效率，在HashMap里大量使用了&、>>>这样的二进制运算，比如HashMap初始化是1<<<4，在用hashCode在table数组中取模求余时用的是hashCode&table.length-1
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的倍数，才能使用这些快速的二进制方式。
关于上面indexFor我们可以用两组数来算下：
假设hashCode是17，数组长度是7，那么就是10001&00110=00000，而正确结果是17%7=3；假设数组长度是8，那么就是10001&00111=00001，与正确结果17%8=1相一致。所以保持数组长度是2的倍数，就是为了提高HashMap的效率所做的一个小技巧，同时在内存分配上等都要更快一些。
在根据key来定位其hashCode的时候，并不是简单调用key.hashCode()，而是再度进行了一些运算，其目的是为了使最终哈希出来的值更均匀，
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
至于为什么这么做，比较复杂，我也没搞太清，尤其是其中为什么选择20、12、7、4这样的来右移。还有hashSeed的选择也不太清楚。
这里必须要提下HashMap扩容的效率问题。前面提到ArrayList的扩容性能并不差，而HashMap就完全不一样了，经实验，扩容至少带来性能下降1半以上，但有临界点，元素超过10万数量级差距就不明显了。下面是代码和测试结果
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
public class ResizePerformanceTest {
public static void main(String[] args) {
run(1000);
run(10000);
run(100000);
run(1000000);
run(10000000);
}
public static void run(int times) {
System.out.println("增加"+times+"次");
long startTime=new Date().getTime();
Map map=new HashMap();
for(int i=0;i
map.put(i, i);
}
long endTime=new Date().getTime();
System.out.println("HashMap自动扩容的方式,增加"+times+"次,耗费时间="+(endTime-startTime));
long startTime1=new Date().getTime();
Map map1=new HashMap(times);