参考博文
put操作
节点Entry特征
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
初始化（以默认构造方法为例）
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
...
// 负载因子，默认0.75f
this.loadFactor = loadFactor;
// 阈值，默认为16
threshold = initialCapacity;
// 默认为空操作，供LinkedHashMap使用
init();
}
数据存储
public V put(K key, V value) {
// 第一个阶段，table为空
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 第二阶段，键为空
if (key == null)
return putForNullKey(value);
// 第三阶段，根据键的hash值寻找键值对在table中对应的索引
int hash = hash(key);
int i = indexFor(hash, table.length);
// 第四阶段，遍历散列表寻找
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 第五阶段，找不到则增进新的键值对
modCount++;
addEntry(hash, key, value, i);
return null;
}
第一阶段，方法highestOneBit解决了如何设置变量capacity的问题；
提问：为甚么table容量要设置为 2的幂次方 呢？？？
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 返回大于toSize的最小的 2的幂次方数
int capacity = roundUpToPowerOf2(toSize);
// 更正阈值 threshold = capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化table
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
第二阶段，方法putForNullKey解决了键为空的 键值对 的存储问题。
说明：从源码中可以看出，table零号元素的位置可以存储 键为NULL 的键值对
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
第三阶段，方法hash用于避免低位相同而高位不相同时indexFor操作发生冲突
方法indexFor用于寻找hash值对应的索引，及键key对应的索引
解决：hash%length和hash&(length-1)取余效果相同，但位操作效率更高
特别说明：使用hash&(length-1)的前提是length必须为 2的幂次方
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);
}
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);
}
第四阶段，遍历链表，根据hash值寻找键值对；如果找到更新并返回旧值
第五阶段，如果没有找到键值对，则使用头插法（效率高）添加新节点Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
...
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
remove操作
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
// 如果待删除的元素在链表的第一个位置
if (prev == e)
table[i] = next;
// 如果待删除的元素不在链表的第一个位置
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
get操作
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}