构造函数
HashMap有４个构造函数.分别为:
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
前两种构造方法调用的都是第３个构造方法。这里２个参数 DEFAULT_INITIAL_CAPACITY和DEFAULT_LOAD_FACTOR.
static final int DEFAULT_INITIAL_CAPACITY = 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
DEFAULT_INITIAL_CAPACITY为默认初始容量，默认值为４，必须为２的幂数。这里有一个问题：第一个构造方法public HashMap()注释中说，构造一个空的HashMap,默认初始容量为１６，默认构造因子为0.75。 但是这个值默认的４。
在public HashMap(int initialCapacity, float loadFactor)中会判断initialCapacity的大小，范围为４到1 « 30。 最后将initialCapacity赋给threshold。这个threshold是大小是capacity * load factor，为什么是这个呢，因为在调用put(Key, value)方法时会初始化tab(HashMapEntry<K,V>[]),初始化inflateTable(threshold)时，将threshold赋值为capacity * loadFactor；同时初始化table = = new HashMapEntry[capacity];table的大小为２的幂数。
####HashMapEntry HashMapEntry实现了接口Map.Entry.它的构造方法如下，４个参数分别为hash值，Key,Value,还有一个HashMapEntry<K,V> next，这就是一个链表结构。理想状态下是单链表，但是有时候数据太多时，有可能形成循环链表。
/**
* Creates new entry.
*/
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
####put(Key,value) 方法如下：
public V put(K key, V value) {
//如果tab为空，就初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为空，就将value保存在tab[0]位置
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//获取索引i
int i = indexFor(hash, table.length);
//获取tab[i]处的HashMapEntry，循环这条链上的HashMapEntry
//进行遍历
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果hash值相等，同时key也相等。就替换新值，返回旧值；
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);//在索引i处添加Entry
return null;
}
#####putForNullKey 1.先判断table是否为空，为空就初始化table;2.如果key为null, 返回putForNullKey(value)
private V putForNullKey(V value) {
for (HashMapEntry<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++;
addEntry(0, null, value, 0);
return null;
}
#####addEntry(int hash, K key, V value, int bucketIndex) 方法如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//threshold这个值是capacity * loadFactor,例如（１６＊0.75）
//如果HashMap的size大于threshold这个值是capacity，
//同时null != table[bucketIndex],此时需要扩容(变为原来的２倍)
//在resize()方法中，扩容时，创建一个新的table,
//同时把旧的table中的所有Entry重新计算hash
//获得新的index，再放入新的table中
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//创建新的Entry
createEntry(hash, key, value, bucketIndex);
}
#####createEntry 方法如下：在创建过程中，就是把新值放在索引bucketIndex处，把新值的next指向原来bucketIndex的值，在bucketIndex处就形成了一条单向链.
void createEntry(int hash, K key, V value, int bucketIndex) {
//将bucketIndex处的Entry赋值给e,
//创建新的Entry(key,value为新值),同时新的Entry.next指向e;
//将新的Entry放在table[bucketIndex]处，
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
//HashMap的sizｅ+1
size++;
}
以上就实现了HashMap的put过程。
####get(Object key)过程 取值的过程很简单，如果key==null,就遍历table[0]处的链表，获取value;如果key!=null,先计算key的hash值，获取hash&(table.lenth-1)的值index，遍历table[index]处的链表，获取value。
public V get(Object key) {
//key == null,取空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;
}
//遍历index=0处的链表，如果key == null,就返回e.value
for (HashMapEntry<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;
}
//计算key的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//遍历indexFor(hash, table.length)处的链表，获取e.value
for (HashMapEntry<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;
}
####remove(Object key)过程 移除的过程相对于插入的过程就稍微有点复杂。因为需要在一条链表上移除一个Entry，过程也很简单。获取链表表头，也就是key对应索引index处table[index]，从表头向下遍历，获取当前的Entry和Entry.next;还有Entry的表头。如果当前Entry对应key，则将Entry的表头.next指向Entry.next。
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
//获取key对应的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//获取index
int i = indexFor(hash, table.length);
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
while (e != null) {
HashMapEntry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//pre为表头
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}