JDK7：Entry数组+链表
JDK8：Node数组+链表+红黑树
本文只讨论JDK1.7的HashMap，JDK1.8的HashMap将在另一篇文章中讨论
源码分析 重要属性// 默认初始化数组长度-16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 默认最大数组长度-2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空tabl
static final Entry[] EMPTY_TABLE = {};
// map中维护的Entry数组
transient Entry[] table = (Entry[]) EMPTY_TABLE;
// 整个map中的元素个数
transient int size;
// 扩容阈值
int threshold;
// 负载因子，用于计算是否需要扩容
final float loadFactor;
// 整个map的修改次数
transient int modCount;
// ？？？
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
// 与此实例关联的随机化值，应用于密钥的哈希代码，以使哈希冲突更难找到。如果为0，则禁用替代哈希。
transient int hashSeed = 0;
重要方法
// 计算key在整个map中的hash值
final int hash(Object k) {
int h = hashSeed; // 默认为0
// 判断 hashSeed 是否不等于0，并且k不属于字符串
if (0 != h && k instanceof String) {
// 调用底层的Hashing方法
return sun.misc.Hashing.stringHash32((String) k);
}
// ----------- 不需要用替代hash -----------
// 减少hash冲突
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 传入hash值-h，数组长度-length
// 返回该hash值在数组中对应的位置
static int indexFor(int h, int length) {
return h & (length-1);
}
// 初始化table
private void inflateTable(int toSize) {
// 找到大于等于toSize的2的次幂，作为当前容量
int capacity = roundUpToPowerOf2(toSize);
// 计算阈值
// 计算方式：(当前容量*负载因子，最大容量+1) 中的最小值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
// 初始化哈希掩码值，在用的时候才进行初始化。
// 一般情况下，都返回false
final boolean initHashSeedAsNeeded(int capacity) {
// ----------- 重点看switching -----------
// switching表示是否需要重新计算hashSeed
// currentAltHashing 一般为false
boolean currentAltHashing = hashSeed != 0;
// capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD 一定为false，所以 useAltHashing 也为false
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// currentAltHashing 和 useAltHashing 不同时，switching才为true
boolean switching = currentAltHashing ^ useAltHashing;
// 如果switching为true，重新计算hashSeed
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
// 返回是否重新计算了hashSeed
return switching;
}
resize()方法
// 进行扩容
void resize(int newCapacity) {
// 用一个局部变量oldTable指向原table
Entry[] oldTable = table;
// 原数组的容量（数组长度）
int oldCapacity = oldTable.length;
// 判断原数组容量是否已经达到设置的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
// 如果是，则将阈值设置为整型最大值，方法结束
threshold = Integer.MAX_VALUE;
return;
}
// 执行到这里说明原数组容量尚未达到设置的最大值
// 创建一个新table
Entry[] newTable = new Entry[newCapacity];
// 调用transfer方法
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将新数组复制给原数组
table = newTable;
// 重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 重新计算每个节点的hashcode，并将其放在新数组的对应位置
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
// e表示当前节点
while(null != e) {
// 存储当前节点e的下一个Entry节点
Entry next = e.next;
// 判断是否需要rehash，一般都不会进行rehash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 当前节点的下一个指向newTable[i]
e.next = newTable[i];
// 把当前节点挪如newTable[i]
newTable[i] = e;
// 让当前节点e指向next
e = next;
}
}
}
需要注意的是，在多线程环境下进行resize()容易产生死循环问题，具体原因我会在另一篇博客里详细讨论
get()方法public V get(Object key) {
// 判断key是否为null
if (key == null)
return getForNullKey();
// --------------- key 不为null ---------------
// 获取entry
Entry entry = getEntry(key);
// 如果entry不为null，则返回entry中的value，否则返回null
return null == entry ? null : entry.getValue();
}
final Entry getEntry(Object key) {
// 判断hashmap是否有元素
if (size == 0) {
// 没有元素
return null;
}
// -------------- hashmap中有元素 ----------------
int hash = (key == null) ? 0 : hash(key);
// 遍历该key对应的hash在table中对应的位置的链表
for (Entry 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;
}
// 获取hashmap中空值的value
private V getForNullKey() {
if (size == 0) {
return null;
}
// 遍历table[0]处的链表
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
put()方法
public V put(K key, V value) {
// 如果table数组为空，则初始化table数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null值，则调用特殊的null值处理方法
if (key == null)
return putForNullKey(value);
// ------------ key 不为null ---------------
// 计算key在HashMap中的hash值
int hash = hash(key);
// 找到对应hash值在数组table中的位置
int i = indexFor(hash, table.length);
// 遍历该位置的链表，也就是遍历该位置的每个Entry节点
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
// 判断当前遍历到的Entry的hash是否与key的hash相同，并且判断key值是否一致
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 如果是，则说明链表中已有key，则进行替换
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
// 返回旧值
return oldValue;
}
}
// ------------ 该位置的链表中没有key ------------
modCount++;
// 新增Entry到Map中
addEntry(hash, key, value, i);
return null;
}
// 新增Entry到Map中
void addEntry(int hash, K key, V value, int bucketIndex) {
// 判断是否需要扩容
// 判断依据：size(当前Map中的元素个数)是否大于threshold(扩容阈值)，当前插入位置是否有Entry节点
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容，数组长度翻倍
resize(2 * table.length);
// 重新计算当前插入key的hash
hash = (null != key) ? hash(key) : 0;
// 重新计算当前插入key的hash在数组table对应的位置
bucketIndex = indexFor(hash, table.length);
}
// 在该插入位置新建Entry节点
createEntry(hash, key, value, bucketIndex);
}
// 在map中新建Entry节点
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
// put的key值为null
private V putForNullKey(V value) {
// 直接在table[0]的位置插入
for (Entry e = table[0]; e != null; e = e.next) {
// 如果table[0]已有key为null的节点，则直接覆盖
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// -------- table[0]中没有key为null的Entry节点 --------
modCount++;
addEntry(0, null, value, 0);
return null;
}
