Java Collections Framework中实际操作的都是数组或者链表,而我们通常不需要显示的维护集合的大小,而是集合类框架中内部维护,方便的同时,也带来了性能的问题。
HashMap有两个参数影响其性能:初始容量和加载因子。默认初始容量是16,加载因子是0.75。容量是哈希表中桶(Entry数组)的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用 rehash 方法将容量翻倍。我们先看看默认的构造器吧,以下为我本机的JDK6.0的源代码.
static final int DEFAULT_INITIAL_CAPACITY = 16; static final float DEFAULT_LOAD_FACTOR = 0.75f; int threshold; public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
从代码可以看出,默认的容量是16,而 threshold是16*0.75 = 12;
我们来看看增加的部分代码。public V put(K key, V value) { // 我们忽略掉这部分的代码,只看我们这里最关心的部分 addEntry(hash, key, value, i); // 这里增加了一个Entry,我们看看代码 return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entrye = table[bucketIndex]; table[bucketIndex] = new Entry (hash, key, value, e); if (size++ >= threshold) // 这里是关键,一旦大于等于threshold的数值 resize(2 * table.length); // 将会引起容量2倍的扩大 } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; // 新的容器空间 transfer(newTable); // 复制数据过去 table = newTable; threshold = (int)(newCapacity * loadFactor); // 重新计算threshold的值 }
好了,我想我们已经清楚大部分了。
其中有一点,起始容量必须是2的幂次,这如何保证呢?我们来看看其构造方法public HashMap(int initialCapacity, float loadFactor) { // 忽略掉一部分代码.... // Find a power of 2 >= initialCapacity // 重新查找不比指定数值大的最大的2的幂次数 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; // 其它的初始化代码 ... }
好了,关于起始容量和加载因子的探讨我们就到这里了。我们应该有了一定的了解了。
总结: 相对准确的估算数据量,将极大的影响HashMap的性能,因为resize是一个重新分配的过程,耗时应该是里面最大的。 加载因子较小,会有更多的空间空闲,我不知道这个0.75是不是一个折中方案。也许0.9也是一个不错的选择,特别是那些数据量虽然很大,但不是经常变化的地方,比如公司人员,城市列表等相对比较固定的数据。