static final int DEFAULT_INITIAL_CAPACITY =16
map初始化的长度，也就是table的长度
transient Entry[] table
table数据里存放着每一个put进去的k,v组成的对象
static final float DEFAULT_LOAD_FACTOR = 0.75f;
int threshold;
初始化赋值默认16，此时table={}为空
这里了解Entry的结构是相当的重要：
static class Entry{
final K key;
V value;
Entry next;这里的next也就是表示Entry是一个链，table的每一个索引存放着一条链状结构，同时对于相同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是否为空，为空则初始化
然后根据key值计算出table里的index，取得对应的entry，首先遍历entry,如果key值已经存在那么直接替换值，如果不存在，在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里当table里存放的entry大于初始化时的capacity便把数组长度扩大两倍
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);
}
数组扩大就要涉及到新数据里和老数据数据复制的过程，所以一般发生扩容的时候效率上也是受到影响的。
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;
}
}
}
我们注意到对table里的每一个index对应的桶bucket复制之后链表的顺序是相反了。。这一点我也不清楚为何要这么处理。
基本了解了hashmap的结构，其他的方法可以自己去看源码。
网友评论