基本方法
Put方法(具体流程看下面的执行流程分析或者代码注释)
具体执行流程:
(1) 判断当前table是否为EMPTY_TABLE={},证明没有初始化,调用inflateTable初始化,具体详见后面inflateTable()方法代码分析.
(2) 判断key是否为null,是null调用putForNullKey插入方法(证明1.7的HashMap允许key为null),具体详见后面putForNullKey()方法代码分析.
(3) 获取当前key的hash,然后算出hash在数组的位置i(hash & (tab.length - 1)).给大家解释下为什么数组的长度必须是2的冥,是和算i的位置有关系,因为如果一个数是2的冥次方,假如这个数是n,那么 hash % n = hash & (n -1),这就是为什么i的位置一定会在数组长度范围中,因为取得是余数,还有就是位运算比直接取余效率高.
(4) 判断当前位置上有没有值table[i],如果有值,遍历链表,找出相同的key和hash,然后替换value,返回旧的value(oldOvalue).
(5) 如果没有找到相同的key和hash,那么就添加这个节点(Entry),方法addEntry().
(6) 在addEntry()方法里面判断需不需扩容,需要就扩容,调用扩容方法resize(),然后在调用 createEntry()方法添加节点,size++.
// 插入
public V put(K key, V value) {
// 当插入第一个元素时,需要初始化
if (table == EMPTY_TABLE) {
// 初始化
inflateTable(threshold);
}
// key为null是
if (key == null)
// 找出key为null,替换返回旧值
// 没有则新添加一个key为null的Entry
return putForNullKey(value);
// 计算hash值
int hash = hash(key);
// 根据hash,找出table的位置
int i = indexFor(hash, table.length);
// 因为在table[i]中,可能存在多个元素(同一个hash),所以要基于链表实现
// 循环table[i]上的链表(不为空),存在就修改,返回旧值(oldValue)
for (Entry 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;
}
inflateTable初始化方法(懒加载,只有第一次调用put方法时才初始化)
// 初始化table
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 计算出大于等于toSize最邻近的2^n(所以capacity一定是2^n)
int capacity = roundUpToPowerOf2(toSize);
// 在此计算阈值 capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor,
MAXIMUM_CAPACITY + 1);
// 创建capacity大小的capacity数组就是hashmap的容器
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
putForNullKey方法(存储key为null的数据)
具体执行流程:
(1) 遍历table[0]处的链表(说明nullkey永远存在table[0]位置)
(2) 找到key==null 的数据,替换value,返回旧的value
(3) 没有找到,就在table[0]位置添加一个key为null的Entry,调用addEntry()方法.
private V putForNullKey(V value) {
// 遍历table[0]的链表
// 找到key等于null的,把值覆盖,返回旧值(oldValue)
for (Entry 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++;
// 没有找到就添加一个key为null的Entry
addEntry(0, null, value, 0);
return null;
}
addEntry方法(判断是否需要扩容,然后在添加节点Entry)
执行流程:
(1) 判断是否需要扩容,size(每次添加一个entry size++)>=threshold(阈值)并且当前这个key的hash算出的位置必须有元素才扩容,具体详解看代码注释.
(2) 如果满足扩容条件,调用扩容方法resize(2 * table.length),table长度扩大2倍,然后重新算当前key的hash和位置bucketIndex.
(3) 调用createEntry()方法,添加节点.
// 添加节点到链表
void addEntry(int hash, K key, V value, int bucketIndex) {
/*
* 扩容机制必须满足两个条件
* (1) size大于等于了阈值
* (2) 到达阈值的这个值有没有发生hash碰撞
* 所以阈值在默认情况下是12 是一个重要节点
* 扩容范围是12-27
* 最小12进行扩容,最大27时必须进行扩容
* 分析最小12扩容
* 当size是12时,判断有没有hash碰撞,有扩容,没有继续不扩容.
* 分析最大27扩容
* 当12没有进行扩容时,size大于阈值就一直满足了
* 就只需要判断接下来的hash有没碰撞,有就扩容,没有就不扩容
* 最大是一种极端情况,前面11个全部在一个table索引上,接下来
* 15个全部没有碰撞,11+15=26,table所有索引全部有值,在插入一个
* 值必须碰撞就是26+1=27最大进行扩容
* */
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容(方法里面重点讲)
resize(2 * table.length);
// 计算hash,null时为0
hash = (null != key) ? hash(key) : 0;
// 计算位置
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
createEntry方法(在传入位置加入一个节点)
// 创建一个新的Entry,放在链表的表头,size++
void createEntry(int hash, K key, V value, int bucketIndex) {
// 这里可以理解为当前的第一个节点
Entry next = table[bucketIndex];
// 创建一个新的节点,next节点是当前的第一个节点,然后设置到bucketIndex位置
table[bucketIndex] = new Entry<>(hash, key, value, next);
size++;
}
resize方法(扩容方法,扩容成原来的2倍)
执行流程:
(1) 计算oldTable的长度,如果oldTable的长度已经是最大值了,那么就把阈值设置成Integer.MAX_VALUE,return.
(2) 根据新的容量创建table.
(3) 调用transfer方法转移数据.
(4) 将新table赋值给旧table,重新就算阈值.
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 如果当前值已经是最大值了(2^30),就设置阈值为Integer的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 根据传入Capacity重新创建新数组,扩容完成
Entry[] newTable = new Entry[newCapacity];
// 把原来的数据迁移到新的table(newTable)
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将table设为新table(newTable)
table = newTable;
// 设置新的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer方法(负载转移数据,把旧table的数据迁移到新table,至此扩容完成)
注意:扩容完成后链表的顺序会反转,如下图解释.
// 扩容之后迁移数据(重新计算hash,分配地址),很耗性能
// 顺便提一下jdk7(get死循环)就是扩容时造成,造成环形链表
void transfer(Entry[] newTable, boolean rehash) {
// 新数组的容量
int newCapacity = newTable.length;
// 遍历原table
for (Entry e : table) {
// 轮询e不等于null
while(null != e) {
// 保存下个元素
Entry next = e.next;
if (rehash) {
// 计算出key的hash
e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算出table的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
get方法(通过key获取数据)
执行流程:
(1) 判断key是否为null,为null调用getForNullKey()方法
(2) 不为null,调用getEntry方法
// get方法
public V get(Object key) {
// key等于null
if (key == null)
return getForNullKey();
// 不为null是查找
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
getForNullKey()方法(遍历table[0]位置数据,找到key==null的返回)
private V getForNullKey() {
// 没数据
if (size == 0) {
return null;
}
// 从table[0]处遍历链表,找到key=null的返回
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
getEntry()方法(根据hash算出位置,遍历当前位置的数据,找到key和hash相同的返回)
final Entry getEntry(Object key) {
// 没数据
if (size == 0) {
return null;
}
// 获取hash
int hash = (key == null) ? 0 : hash(key);
// 获取table的位置,找到hash和key相同的返回
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;
}
remove()方法
final Entry removeEntryForKey(Object key) {
// 没数据
if (size == 0) {
return null;
}
// 获取hash
int hash = (key == null) ? 0 : hash(key);
// 计算位置
int i = indexFor(hash, table.length);
// 获取i位置的entry
Entry prev = table[i];
Entry e = prev;
// 遍历链表
while (e != null) {
Entry next = e.next;
Object k;
// 找到了hash和key相等的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
// 容量减减
size--;
// 说明是第一个元素
// 把头结点设置成他的下一个元素
if (prev == e)
table[i] = next;
// 删除当前e,把上一个元素的next指向当前e.next
// 1 -2 -3-null 删除2,把1的next指向2的next,就是1-3-null
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
