用java源代码学数据结构<六>: HashSet HashMap 详解(三)
}
//将表格大小扩展到toSize
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
table = new Entry[capacity];
//根据capacity初始化hashSeed
initHashSeedAsNeeded(capacity);
}
// internal utilities
void init() {
}
/**
* Initialize the hashing mask value. We defer initialization until we
* really need it.
*/
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
//根据系统函数得到一个hash
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
//如果hashSeed初始化为0则跳过switching
//否则使用系统函数得到新的hashSeed
if (switching) {
hashSeed = useAltHashing
sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
/*
哈希算法的核心：哈希函数
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
*/
final int hash(Object k) {
int h = hashSeed;
//通过hashSeed初始化的值的不同来选择不同的hash方式
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//Returns index for hash code h.通过得到的hash值来确定它在table中的位置
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);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);//查看调用函数，在下面
return null == entry null : entry.getValue();
}
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;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hash值确定table下标（null对应下标0）
int hash = (key == null) 0 : hash(key);
//indexFor() = h & (length-1) = hash&(table.length-1)
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next)
//对冲突的处理办法是将线性探查，即将元素放到冲突位置的下一个可用位置上
{
Object k;
/*注意：因为元素可能不是刚好存在它