HashSet、HashMap，散列表数据结构（哈希表） (二)

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode()); // 获取key的hash值
int i = indexFor(hash, table.length); // h & (length-1); 通过hashcode取模数组长度， 定位hash值在table数组中的索引
// 如果table数组中i索引所在位置有元素，循环遍历该链表中的下一个元素
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
// 遍历到了hash值相同并且equals也相同的key，把value用新值替换掉
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
// table中i索引所在位置没有元素，添加key、value到指定索引处。
addEntry(hash, key, value, i);
return null;
}
addEntry()方法源码：

[java]
void addEntry(int hash, K key, V value, int bucketIndex) {
// 下面两行代码将entry保存进了table数组中Entry内部链表的第一个位置。
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold) // 需要扩容了
resize(2 * table.length); // 重新计算数组大小
}

void addEntry(int hash, K key, V value, int bucketIndex) {
// 下面两行代码将entry保存进了table数组中Entry内部链表的第一个位置。
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold) // 需要扩容了
resize(2 * table.length); // 重新计算数组大小
}
由于元素的位置是通过hashcode取模数组长度而得， 现在由于需要扩容，数组长度会发生变化，
所以会在resize方法跟transfer方法中进行元素位置的重新分配。

resize()方法源码： // 重新计算数组长度
[java]
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor); // 新的扩容阀值
}

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);
table = newTable;
threshold = (int)(newCapacity * loadFactor); // 新的扩容阀值
}
transfer()方法源码：// 重新分配
[java]
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}

void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];