HashMap源码阅读-2019/05/06
2019-05-06 本文已影响0人
Tornado灬King
示例代码
HashMap hashMap = new HashMap<String, String>(); // 1
hashMap.put("1", "1"); // 2
hashMap.get("1"); // 3
Iterator iterator = hashMap.entrySet().iterator();
//Map.Entry e = (Map.Entry) iterator.next();
for(Map.Entry e; iterator.hasNext();){
e = (Map.Entry) iterator.next();
System.out.println(e.getKey() + ", " + e.getValue());
hashMap.put("4", "11"); // 报错java.util.ConcurrentModificationException
}
第一行代码创建了一个HashMap对象，内部逻辑如下
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 实际调用的是如下构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
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(); // 函数内容为空
}
第二行代码往hashMap中put一组数据
public V put(K key, V value) {
// transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
if (table == EMPTY_TABLE) {
inflateTable(threshold); // 对空表进行初始化
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length); // 寻找hash对应的数组下标
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++; // 不允许在迭代时put新key，允许put已存在的key
addEntry(hash, key, value, i); // 添加entry
return null;
}
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);
}
private V putForNullKey(V value) {
for (Entry<K,V> 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++; // 记录更改次数，用于迭代器的fail-fast机制
addEntry(0, null, value, 0); // 添加key为null, hash值为0的entry, 在数组中的index为0
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
// 当size(entry总数)>=threshold(capacity*load_factor)并且bucketIndex位置已存在entry时，将hashMap扩容为原来大小的两倍
resize(2 * table.length);
// Hashtable扩容规则：int newCapacity = (oldCapacity << 1) + 1;
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n; // 将新建的entry放在链表头部
key = k;
hash = h;
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1); // 取模
}
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中
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
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;
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;
}
}
}
第三行代码从hashMap中取key对应的value
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> 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;
}
剩余的代码为对hashMap的迭代器的操作
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// EntryIterator、KeyIterator和ValueIterator都继承自HashIterator
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
; // 找到table数组中第一个不为null的entry置于变量next中
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
// 对迭代器的remove会直接remove hashMap中的entry
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount; // 允许一边迭代一边删除
}
}
