这两天找工作，对于HashMap中的put操作流程，已经被问及了多次！！！所以，打算从源码的角度，梳理一下执行的流程。
JDK1.7.0_80 中 HashMap 的put操作源码
jdk1.7 HashMap put操作
构造函数
//无参数构造函数
public HashMap() {
//this(16, 0.75f)
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果初始化的容量大于最大容量,就将初始容量设置为最大允许容量 MAXIMUM_CAPACITY = 1 << 30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子小于零或者不是数字,抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//阈值设置为初始化容量值
threshold = initialCapacity;
//空方法,提供给之类的一个勾子方法
init();
}
put(K key, V value)
public V put(K key, V value) {
//如果table是默认初始化的空数组,则填充数组table,惰性初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//key是null,将key为null的value放入table中
if (key == null)
//当key为null时,则替换或者添加一个新的元素Entry
return putForNullKey(value);
//获取key的hash值
int hash = hash(key);
//获取对应的桶索引
int i = indexFor(hash, table.length);
//以下for循环,是当key相应的key存在时,则替换value
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;
}
inflateTable(int toSize)
//toSize: 填充table数组的大小
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 将容量capacity转换为二的次方,比toSize大的最近一个元素,如 15 -> 16 16 -> 16 17 -> 32
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化容量为capacity (默认:16)
table = new Entry[capacity];
//验证是否有必要初始化hash因子
initHashSeedAsNeeded(capacity);
}
boolean initHashSeedAsNeeded(int capacity)
final boolean initHashSeedAsNeeded(int capacity) {
//hashSeed实例变量,默认为0
boolean currentAltHashing = hashSeed != 0;
//Holder.ALTERNATIVE_HASHING_THRESHOLD是内部静态类Holder的一个属性,Holder静态代码块中有对该值的初始化逻辑
//可以通过配置JVM参数 -Djdk.map.althashing.threshold={int} 初始化,参数为-1或者不配置,默认为Integer.MAX_VALUE
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//异或,只有两个一个为true,一个为false才为true
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
putForNullKey(V value)
private V putForNullKey(V value) {
//由此可知,key为null的元素,放在了table[0]的位置,具体是0位置链表中的哪个元素,就需要循环查询了
//如果已经存在key为null的元素,则替换value
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
//这是一个勾子方法,在HashMap.Entry中是空实现
e.recordAccess(this);
return oldValue;
}
}
//HashMap结构上修改的次数++
modCount++;
//添加一个key为null,值为value的元素
addEntry(0, null, value, 0);
return null;
}
addEntry(int hash, K key, V value, int bucketIndex)
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容
resize(2 * table.length);
//计算hash
hash = (null != key) ? hash(key) : 0;
//计算桶的索引
bucketIndex = indexFor(hash, table.length);
}
//创建新的元素,并将size++
createEntry(hash, key, value, bucketIndex);
}
resize(int newCapacity)
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//当之前的table大小已经为最大的容量,则不再扩容,将阈值调整为Integer.MAX_VALUE
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新建数组
Entry[] newTable = new Entry[newCapacity];
//将原table中的元素拷贝到新的table数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//重新设置阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer(Entry[] newTable, boolean rehash)
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//循环遍历所有旧的元素
for (Entry<K,V> e : table) {
//循环遍历同一个桶中链表的所有元素
while(null != e) {
Entry<K,V> next = e.next;
//判断时候需要重新hash
if (rehash) {
//如果key==null,则hash值设置为0,否则根据新的hashSeed,重新hash
e.hash = null == e.key ? 0 : hash(e.key);
}
//根据新的hash值,重新计算索引值,因为大小为2的次方,重新计算hash的方式与取模是相同的,按照 hash & (newLength - 1)
int i = indexFor(e.hash, newCapacity);
//以下两个操作,将同一个桶的元素,转换为对应的链表
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
Map.Entry<K,V>
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
从Map.Entry的源码来看,Map.Entry是一个单向链表.
网友评论