static final int DEFAULT_INITIAL_CAPACITY =16
map初始化的長(zhǎng)度研底，也就是table的長(zhǎng)度
?transient Entry[] table?
table數(shù)據(jù)里存放著每一個(gè)put進(jìn)去的k,v組成的對(duì)象
static final float DEFAULT_LOAD_FACTOR = 0.75f;
int threshold;
初始化賦值默認(rèn)16泼掠，此時(shí)table={}為空
這里了解Entry的結(jié)構(gòu)是相當(dāng)?shù)闹匾?/p>
static class Entry{
final K key;?
V value; ? ? ??
Entry ?next;這里的next也就是表示Entry是一個(gè)鏈，table的每一個(gè)索引存放著一條鏈狀結(jié)構(gòu)，同時(shí)對(duì)于相同hash的entry,采用頭插法。
int hash;
/**? ? ? ? * Creates new entry.? ? ? ? */? ? ??
? Entry(int h, K k, V v, Entryn) {
value = v;
next = n;
key = k;
hash = h;
}
}
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 = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
初始化table
public V put(K key, V value) {??
? ? ? if (table == EMPTY_TABLE) {? ? ? ?
?? ? inflateTable(threshold);? ??
? ? }? ? ?
?? if (key == null)? ? ? ??
? ? return putForNullKey(value);? ?
?? ? int hash = hash(key);? ? ?
?? int i = indexFor(hash, table.length);? ? ??
? for (Entrye = 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;
}
put方法的思路大致為：先判斷table是否為空，為空則初始化
然后根據(jù)key值計(jì)算出table里的index盆色，取得對(duì)應(yīng)的entry灰蛙，首先遍歷entry,如果key值已經(jīng)存在那么直接替換值，如果不存在隔躲，在entry的表頭添加最新的key? value.addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
我們注意到addEntry里當(dāng)table里存放的entry大于初始化時(shí)的capacity便把數(shù)組長(zhǎng)度擴(kuò)大兩倍
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
數(shù)組擴(kuò)大就要涉及到新數(shù)據(jù)里和老數(shù)據(jù)數(shù)據(jù)復(fù)制的過(guò)程摩梧，所以一般發(fā)生擴(kuò)容的時(shí)候效率上也是受到影響的。
void transfer(Entry[] newTable, boolean rehash) {? ? ? ? int newCapacity = newTable.length;? ? ? ? for (Entrye : table) {? ? ? ? ? ? while(null != e) {? ? ? ? ? ? ? ? Entrynext = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
我們注意到對(duì)table里的每一個(gè)index對(duì)應(yīng)的桶bucket復(fù)制之后鏈表的順序是相反了宣旱。仅父。這一點(diǎn)我也不清楚為何要這么處理。
基本了解了hashmap的結(jié)構(gòu)浑吟，其他的方法可以自己去看源碼笙纤。
