构造函数
HashMap 提供了三个构造函数和一个拷贝构造函数：
public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m);
构造函数
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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();
}
这个构造方法需要提供两个参数，initialCapacity 和 loadFactor 。
- 第一个参数表示 hashMap 的初始化大小，默认值为
static final int DEFAULT_INITIAL_CAPACITY = 4;，且 初始化大小的值必须是 2 的整数次幂。 - 第二个参数表示 todo
在构造方法中，首先对初始化大小 initialCapacity 进行校正，校正范围是 4(默认初始化大小) ~ 2^30(最大容量)。
HashMapEntry
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
}
HashMapEntry 中保存着一个 Key 和 Value ，并持有下一个 HashMapEntry ，很明显这是一个 <K-V> 键值对链表。
数据结构
put 方法
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
- 从上面代码可以看出，HashMap 的 Key 是可以为 null 的，在
key == null的情况下，调用putForNullKey()方法特殊处理
- 正常的情况下，现根据 key 的值计算出 hash 值，并计算出该 hash 值在队列中的 index。在 table 数组中取出 HashMapEntry 的链表，并进行遍历，如果 hash 值相同且 Key 也相同，说明新插入的 Key 在 链表中存在，需要覆盖旧值，并返回旧值。如果没有找到，说明这个 Key 并不存在，需要调用
addEntry添加在 HashMapEntry 的链表中。
**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
从 addEntry 方法的实现可以看出，当此时 hashmap 的 size 大于等于阈值时，需要将 table 的长度扩大一倍，并调用 createEntry() 方法根据新 Key 的 hash 值 存储在 table 中。
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
将 table 中 index = bucketIndex 的 HashMapEntry 作为新节点的下一个 Entry ，并将 table[bucketIndex] 指向新节点。
get 方法
get 方法的思想就是利用 key 的 hash 值获得在 table 中所处的 index ，并对其进行遍历，比较 Key 将对应的 Value 取出。
