概述
我相信只要写过JAVA的程序要拿99%的都用过HashMap, 其是我们最常用,也是最基础的一个Map.本篇文章将从存储结构、hash规则、扩容策略、迭代器四方面来分析其源代码。
hash规则
当调用get,put后,首先需要计算key的hash值--hash(key),然后计算在数组中的index--indexFor(hash, table.length).
hash(key):
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);
}
hash(key)为什么这么写?遵循一个原则:减少hash冲突,说实话,我也没有深入研究why.
indexFor(hash, table.length):
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);
}
这句代码很有意思,它隐含了一个条件: table.length一个的2的n次方,
从而用&代替%,提高效率。
hashSeed, 在计算hash的时候,用到了一个hash种子:hashSeed,其是怎么得来的呢?
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
Holder:
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
这个地发,没理解透.
网友评论