HashMap是存储key-value的集合，底层采用Node<K,V>[] table实现，初始大小为2^4即16。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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 (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;
}
|
put操作首先根据key的hash值来找到要插入的index，如果存在相同key的元素则替换，否则插入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
|
hash方法采用的是sun.misc.Hashing中的方法。
1
2
3
4
5
6
7
8
9
|
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);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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);
}
|
添加元素的时候会检查是否需要扩容，如果需要会将数组大小增大一倍，同时进行rehash来将之前的元素转移到现在的数组中来。
如果不需要扩容，直接添加元素
1
2
3
4
5
|
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++;
}
|
将table数组index位置元素指向插入元素，插入元素作为链表头。
get操作和put操作差不多，根据key查找Entry
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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;
}
|
table数组的长度是2^n，这样2^n-1的二进制表示每一位都是1，方便进行index计算。
1
2
3
4
|
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);
}
|
LinkedHashMap的Entry除了有一个next来处理冲突，还有before和after来将所有元素连接成一个双向循环链表。
1
2
3
4
5
6
7
8
|
// LinkedHashMap
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**
* Inserts this entry before the specified existing entry in the list.
*/
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
|
Entry的addBefore将元素添加至双向循环链表的尾部，recordAccess将元素从双向循环链表原来的位置移除，重新添加到链表尾部。如果key元素已经存在Map中，在put时会替换value，同时recordAccess，recordAccess在HashMap的Entry中是空实现，在LinkedHashMap中进行移除到链表尾部的操作。recordAccess还在LinkedHashMap的get方法中被调用，这样每次执行get操作返回元素的同时将Entry移动到链表尾部。
WeakHashMap的Entry是WeakReference的子类，创建的时候和ReferenceQueue进行关联，referent是key，当key被回收时将移除key对应的entry。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/**
* Expunges stale entries from the table.
*/
private void expungeStaleEntries() {
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) x;
int i = indexFor(e.hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
while (p != null) {
Entry<K,V> next = p.next;
if (p == e) {
if (prev == e)
table[i] = next;
else
prev.next = next;
// Must not null out e.next;
// stale entries may be in use by a HashIterator
e.value = null; // Help GC
size--;
break;
}
prev = p;
p = next;
}
}
}
|
key被回收时Entry会被放入ReferenceQueue中。在调用size()和resize()方法时会调用expungeStaleEntries方法。
一般情况下，一个对象被标记为垃圾（并不代表被回收了）后会被加入引用队列。
对于虚引用来说，它指向的对象只有被回收后才会加入引用队列，所以可以作为记录该引用指向的对象是否被回收。
reference
