Java数据结构源码分析HashMap

1.HashMap

1.1 Map接口

在开始介绍HashMap的源码前，我们先来了解下HashMap的在内存的数据组织方式：
整个结构分为两部分，第一部分是一个Entry[]数组，其数组的索引就是hash之后的slot位置。 第二部分是一个链表，每个Entry对象都会有一个Entry next的引用指向下一个Entry对象，如此当出现冲突时，只需要将冲突的数据加入到链表中就行了

接下来，我们来看看Map的接口形式，其定义了构造Map最关键的两个核心接口和方法，Map和Entry，不同类型的Map会使用不同的Entry来实现。

package java.util;
public interface Map {
interface Entry {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
void clear();
boolean containsKey(Object key);
boolean containsValue(Object value);
Set<Map.Entry> entrySet();
boolean equals(Object o);
V get(Object key);
int hashCode();
boolean isEmpty();
Set keySet();
V put(K key, V value);
void putAll(Map m);
V remove(Object key);
int size();
Collection values();
}

1.2 HashMap源码分析

在开始HashMap具体方法之前我们先来看看，其中几个比较重要的内部类的作用

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry next;
int hash;
}
private abstract class HashIterator<E> implements Iterator<E> {
Entry next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry current; // current entry
}
}
类：Entry
该类是用于构造HaspMap数据结构的核心类。其主要用于保存数据
类：HashIterator
该类用于遍历HashMap的Entry,按照列的顺序，从数组的第一列的所有Entry到最后一列的Entry

接下来我们分析HashMap的使用过程：

1.HashMap的内存分配过程
Map map1=new HashMap(10,0.8);
上述过程中并不会立即对Map进行分配内存，即table任然是EMPTY_TABLE;
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static final Entry[] EMPTY_TABLE = {};
其内存的分配是第一次调用put方法向容器中插入数据的时候。内存分配的大小是大于initialCapacity的最小2的幂级数。例如此处为2^4>=10
2.threshold为threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 即其是table分配大小*loadFactor
该Threshold和HashMap中table的重新分配大小有关，当table中原始大于threshold，并且该次插入数据的位置产生了冲突，那么将会按照现有Map的大小的2倍进行重新分配，并进行新的hashseed的重新计算和现存元素的重新hash.
3.HashMap在插入数据时遇到冲突，会将冲突的数据插入到链表的表头位置，对于key为null的数据对，会别插入到table[0]的位置
4.modCount表示HashMap被修改的次数，在每次调用put、remove、clear等方法时，都会加一

1.3 插入操作

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 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;
}
private V putForNullKey(V value) {
for (Entry 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++;
addEntry(0, null, value, 0);
return null;
}
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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

对于put方法：首先会通过hash(key)和indexFor方法去获取key在table中slot的位置，然后通for循环去遍历链表，如果存在现有key则替换，返回旧值。否则addEntry去插入数据。
在addEntry方法中会首先判断HashMap的load是否超过阈值threshold，如果是扩大一倍内存，并rehash原有数据，并重新计算slot的位置。然后通过设置Entry的hash、key、value、next几个字段，并使用链表的表头插入方法插入数据。

1.3 删除操作

public V remove(Object key) {
//真正删除元素的位置
Entry e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry prev = table[i];
Entry e = prev;
//循环更新prev和e，根据删除的数据是否在表头分开考虑
while (e != null) {
Entry next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
//如果找到要删除的key，则返回value，否则返回为null
//清空方法，只需要把table的各个位置引用赋值为空，则gc负责回收栈上的对象空间
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}

1.4 其他操作

//双层循环查找是否存在value
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
public Object clone() {
HashMap result = null;
try {
result = (HashMap)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
//首先clone HashMap对象本身，然后通过result.inflateTable方法clone HashMap中的table对象，
//其次putAllForCreate取出HashMap中的Entry对象，并构造新的Entry对象并将Key和Value的引用传递给新的Entry,
//从而实现元素的浅拷贝。
//注意：HashMap的clone只是clone了HashMap的table对象，而table中的元素并没有被拷贝，其拷贝的是对象的引用。因此其是浅层的拷贝，
//如果想就行深层次拷贝可以通过使用seriablize手段来实现
public Object clone() {
HashMap result = null;
try {
result = (HashMap)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
//HashMap的持久化
//从持久化的对象字段可以看出，其主要分为如下两部分：
//1、写入table相关的属性包括threshold、size、length用于重建table
//2、table中保存的对象的持久化，分别持久化key和value字段，
//要求改类对象都实现了Seriablizable接口，否则会报错
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
if (table==EMPTY_TABLE) {
s.writeInt(roundUpToPowerOf2(threshold));
} else {
s.writeInt(table.length);
}
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {
for(Map.Entry e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// set other fields that need values
table = (Entry[]) EMPTY_TABLE;
// Read in number of buckets
s.readInt(); // ignored.
// Read number of mappings
int mappings = s.readInt();
if (mappings <0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
// capacity chosen by number of mappings and desired load (if >= 0.25)
int capacity = (int) Math.min(
mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
// allocate the bucket array;
if (mappings > 0) {
inflateTable(capacity);
} else {
threshold = capacity;
}
init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}

注意：
out = new ObjectOutputStream(memoryBuffer);
out.writeObject(src);
在调用如上方法进行序列化时，其要求src必须实现serizable接口，并且其字段也必须实现了serizable接口，并且对于每个对象如果实现了writeObject方法，那么在序列化该对象的时候回调用该对象的writeObject方法。writeObject方法主要是用于个性化定制该对象的序列化方法

private void writeSerialData(Object obj, ObjectStreamClass desc)
throws IOException
{
ObjectStreamClass.ClassDataSlot[] slots = desc.getClassDataLayout();
for (int i = 0; i ObjectStreamClass slotDesc = slots[i].desc;
//通过反射判断是否有writeObject方法，有则使用该方法序列化对象
if (slotDesc.hasWriteObjectMethod()) {
PutFieldImpl oldPut = curPut;
curPut = null;
SerialCallbackContext oldCOntext= curContext;
if (extendedDebugInfo) {
debugInfoStack.push(
"custom writeObject data (class \"" +
slotDesc.getName() + "\")");
}
try {
curCOntext= new SerialCallbackContext(obj, slotDesc);
bout.setBlockDataMode(true);
slotDesc.invokeWriteObject(obj, this);
bout.setBlockDataMode(false);
bout.writeByte(TC_ENDBLOCKDATA);
} finally {
curContext.setUsed();
curCOntext= oldContext;
if (extendedDebugInfo) {
debugInfoStack.pop();
}
}
curPut = oldPut;
} else {
//否则调用默认方法序列化对象
defaultWriteFields(obj, slotDesc);
}
}
}