一、HashMap的继承关系
简易类图
HashMap实现Map接口，同时继承了AbstractMap.
Map接口定义了 get put contains 等方法
AbstractMap则实现了一些各种类型的Map都通用的方法。
二、HashMap实现原理
2.1、数据结构
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
数据是存储在一个Entry的数组中的，然后Entry是定义成：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
Entry 是一个链表的结构，存有下一个节点的引用。
所以HashMap的数据结构，就是数组+链表。
结构图.png
三、HashMap实现细节
3.1、初始化
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();
}
- initialCapacity用来表示初始设置的容量是多大，如果不传的话，则默认为16，最大是2的30次方。
- loadFactor 作为负载因子，当size>容量*loadFactor 时就需要扩容。
- init() 方法是为子类提供的钩子方法，可以在初始化完成，同时还没有对象放进去的时候，完成一些工作。
3.2、Put
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;
}
- 如果是空的Map的话，需要先进行inflate，主要做的是把Entry数组的大小设置为大于初始capacity的最小的2的次方值。
- 然后如果key为null，则去数组的第0位的链表里去找，找不到则新建一个key为null的Entry。所以可以看出HashMap支持key value 为 null。
- key不为null,则用一个复杂的算法去计算key的Hash值，然后对数组的大小取模，得到该key对应在数组位置的下表。
- 遍历这个位置上的链表，找到相同的key,更新value值，并返回旧的value。
- 如果没有找到相同的key,则新增一个Entry。
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);
}
如果size>阈值 （容量*负载因子）并且这个key所在的位置已经有对象，则进行扩容,容量是之前的两倍。
扩容后把要新增的对象重新计算一下位置，添加到该位置的链表头上。
扩容
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);
}
如果之前的容量已经是最大容量了，那么只把阈值调整为最大整数。
否则新建一个容量是之前两倍的数组，把旧数组的对象映射到新的数组上，更新阈值。
3.3 get
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;
}
get方法比较简单，得到Hash值，计算出在数组中的下标，然后遍历链表。
四、HashMap使用注意
4.1、Key的选取
HashMap的key如果选择是自己定义的对象，要保证对象的HashCode不会变化，如果变化了，有可能导致Put进去的对象，没法get出来。
尽量选择 不可变的对象 最为Key,比如String。
4.2、预估容量
HashMap在初始化时，可以设置容量值，如果预计这个Map的容量很大的话，可以事先设置一个大的容量，避免频繁的扩容,rehash。
