本文根据android API 21
构成HashMap最基本的单位是HashMapEntry,所以先来看HashMapEntry的结构。
HashMapEntry
先来看成员变量
Member
key 用来存储键
final K key;value 用来存储键对应的值
V value;value 用来存储键对应的值
final int hash;next 用来指向下个HashMapEntry的指针。
HashMapEntry<K, V> next;构造方法
construct
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}这里的构造方法是为成员变量赋值，每个值具体的含义，前面已经说明。
获得每个HashMapEntry对应的键
1 getKey()
public final K getKey() {
return key;
}获得每个HashMapEntry对应的值
2 getValue()
public final V getValue() {
return value;
}把HashMapEntry的值替换为value
3 setValue(V value)
public final V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}判断两个HashMapEntry是否相等
4 equals(Object o)
@Override public final boolean equals(Object o) {
//先判断是否属于Entry的实例
if (!(o instanceof Entry)) {
return false;
}
//再判断键和值是否都相等
Entry<?, ?> e = (Entry<?, ?>) o;
return Objects.equal(e.getKey(), key)
&& Objects.equal(e.getValue(), value);
} 5 hashCode()
@Override public final int hashCode() {
//^按位异或,比如二进制 1001 ^ 1100 = 0101
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}返回键和值key=value
6 toString()
@Override public final String toString() {
return key + "=" + value;
}下面看HashMap中的内容
HashMap
先来看成员变量
Member
HashMap的最小容量是4
private static final int MINIMUM_CAPACITY = 4;HashMap的最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;一维HashMapEntry[]
transient HashMapEntry<K, V>[] table;构造一个容量为HashMap最大容量一半的空的HashMapEnty[]。
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];当table的容量超过threshold时，table将会重新计算hash值，
除了容量值为0，threshold的值通常为容量值得0.75。
一般作用于EMPTY_TABLE以及比这个容量 多的时候
private transient int threshold;键为空对应的元素
transient HashMapEntry<K, V> entryForNullKey;构造方法
HashMap()
创建一个HashMapEntry[].其值为EMPTY_TABLE
public HashMap() {
//table赋值给EMPTY_TABLE
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}初始化容量的HashMap
HashMap(int capacity)
public HashMap(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity: " + capacity);
}
//和无参构造一样
if (capacity == 0) {
@SuppressWarnings("unchecked")
HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
table = tab;
threshold = -1; // Forces first put() to replace EMPTY_TABLE
return;
}
//如果指定容量比最小容量小，指定的容量为最小容量
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
//如果指定容量比最大容量大，指定的容量为最大容量
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {//表示指定容量比最小容量大，比最大容量小
//这段不理解
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
makeTable(capacity);
}我用黄色表示私有方法
makeTable(int newCapacity)
重新给table赋值
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
//创建容量为newCapacity的局部数组newTable
@SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
//把局部数组赋值给table
table = newTable;
//threshold的值为table容量的3/4
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
}这段代码调用了下面这个方法，看下这个方法的实现
首先来看 |= 的含义：
当两边操作数的位有一边为1时,结果为1,否则为0
5的2进制数表示为0101,6的2进制数表示为0110
5|6为2进制数相与所得到的数,即0111,而0111的十进制数就是7
我照着翻一下原文的注释吧，没明白这个算法是什么意思。
返回二次方和参数的最小值，有如下警告
如果参数是没有预期值得，并且不是Integer.MIN_VALUE.这个方法返回0
如果参数>2^30或者等于Integer.MIN_VALUE.这个方法返回Integer.MIN_VALUE
如果参数是0，这个方法返回0
public static int roundUpToPowerOfTwo(int i) {
i--; // If input is a power of two, shift its high-order bit right.
// "Smear" the high-order bit all the way to the right.
i |= i >>> 1;
i |= i >>> 2;
i |= i >>> 4;
i |= i >>> 8;
i |= i >>> 16;
return i + 1;
}这里为什么要重新创建一个呢？
HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;这个算法不理解
capacity = Collections.roundUpToPowerOfTwo(capacity); HashMap(int capacity, float loadFactor)
这里的和仅初始化容量的构造一样， 从内部的注释和代码中可以看出，这段代码忽略了这个参数。这个参数经常用于值为3/4。这里简化了代码.主要为了提高执行。
public HashMap(int capacity, float loadFactor) {
this(capacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
/*
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
}HashMap(Map< ? extends K, ? extends V> map）
用指定的集合构造一个HashMap()实例
public HashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));
constructorPutAll(map);
}可以看出这里初始化这个HashMap的实例实的容量为指定的map的的长度。在这个方法中调用了constructorPutAll（）方法。下面看这个方法的实现
constructorPutAll(Map< ? extends K, ? extends V> map)
把map中的所有元素插入到HashMap中。此方法被final修饰，说明map不能被重新赋值
final void constructorPutAll(Map<? extends K, ? extends V> map) {
//如果table为默认的空数组 先扩容
if (table == EMPTY_TABLE) {
doubleCapacity(); // Don't do unchecked puts to a shared table.
}
for (Entry<? extends K, ? extends V> e : map.entrySet()) {
constructorPut(e.getKey(), e.getValue());
}
}当table为空数组时，调用了下面这个方法，先来看下这个方法：
doubleCapacity()
HashMap的容量扩展2倍
这个方法不理解
private HashMapEntry<K, V>[] doubleCapacity() {
//声明一个局部变量 = table
HashMapEntry<K, V>[] oldTable = table;
//获取table的容量
int oldCapacity = oldTable.length;
//如果table的容量为最大容量 说明不能再扩容了 直接将此容量的数组返回
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
//重新定义数组容量为原容量的2倍
int newCapacity = oldCapacity * 2;
//用新容量newCapacity重新给table赋值 并且newTable = talbe
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
//如果table的元素数量 = 0 ，直接返回table 因为此时table已经扩容
if (size == 0) {
return newTable;
}
//遍历原来table中的真实元素
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
//获取一维数组中的每个元素
HashMapEntry<K, V> e = oldTable[j];
//如果元素为null，跳出此次循环
if (e == null) {
continue;
}
//用当前遍历的元素和原始容量来算出一个hash值
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
//给新数组newTable[]的下标为j|highBit赋值
newTable[j | highBit] = e;
//遍历二维链表上的元素
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) { //重新计算二维链表的第二个元素的hash值
int nextHighBit = n.hash & oldCapacity;
//比较二维链表的第一个和第二个元素的hash值
if (nextHighBit != highBit) {//如果hash值不相等 说明不在一横排
if (broken == null)
//表示在一维数组上创建一个元素
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}当table数组元素不为空时，调用了如下方法。遍历所有要添加的元素，来通过这个方法添加到table中
constructorPut(K key, V value)
private void constructorPut(K key, V value) {
//键为空
if (key == null) {
//定义一个元素entryForNullKey
HashMapEntry<K, V> entry = entryForNullKey;
//表示不存在键为空的元素
if (entry == null) {
//定义一个键为空的元素
entryForNullKey = constructorNewEntry(null, value, 0, null); //元素数量+1
size++;
} else {
//存在键为空的元素 重新给键为空的元素赋值
entry.value = value;
}
return;
}
//根据key经过两次hash算法。得出hash
int hash = Collections.secondaryHash(key);
//把table赋值给tab
HashMapEntry<K, V>[] tab = table;
//根据两次哈希得出的hash值和table数组的长度得出index
int index = hash & (tab.length - 1);
//把tab数组中下标为index的元素，作为没一横行的第一个节点
HashMapEntry<K, V> first = tab[index];
//遍历table中下标为index对应的一横行节点，查找是否存在key值。
for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
//表示在这一横行中存在和key值相等的entry
if (e.hash == hash && key.equals(e.key)) {
//将此entry的值重置
e.value = value;
return;
}
}
//表示没有找到和当前key相等的key.直接创建一个节点，做为首节点。
// No entry for (non-null) key is present; create one
tab[index] = constructorNewEntry(key, value, hash, first);
size++;
}上述代码中找不到这个节点为什么就直接把first做为首节点呢？也有可能存在这一行。但是不存在键相等的节点啊？为什么不在这一行的末尾添加一个节点？
重新创建一个节点
HashMapEntry<K, V> constructorNewEntry(
K key, V value, int hash, HashMapEntry<K, V> first) {
return new HashMapEntry<K, V>(key, value, hash, first);
}capacityForInitSize(int size)
？
static int capacityForInitSize(int size) {
int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth
// boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY;
}1 clone()
@SuppressWarnings("unchecked")
@Override public Object clone() {
/*
* This could be made more efficient. It unnecessarily hashes all of
* the elements in the map.
*/
HashMap<K, V> result;
try {
result = (HashMap<K, V>) super.clone();
} catch (CloneNotSupportedException e) {
throw new AssertionError(e);
}
// Restore clone to empty state, retaining our capacity and threshold
result.makeTable(table.length);
result.entryForNullKey = null;
result.size = 0;
result.keySet = null;
result.entrySet = null;
result.values = null;
result.init(); // Give subclass a chance to initialize itself
result.constructorPutAll(this); // Calls method overridden in subclass!!
return result;
}2 isEmpty()
判断 HashMap元素个数是否为空
@Override public boolean isEmpty() {
return size == 0;
}3 size()
返回HashMap中元素的数量
@Override public int size() {
return size;
}4 get(Object key)
返回键对应的值
public V get(Object key) {
//返回key=null时，对应的值
if (key == n/ull) {
HashMapEntry<K, V> e = entryForNullKey;
return e/ == null ? null : e.value;
}
//根据key得出的hash值
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//根据hash值，找到相应的某一排的头元素 并根据这个头元素遍历这一排
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
//如果指定的key和遍历找到的key相等或者
//指定的key的hash值和便利找到的元素的hash值相等，并且key也相等
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}这里不明白，eKey==key不就可以了吗？
if (eKey == key || (e.hash == hash && key.equals(eKey))) {5 containsKey(Object key)
判断是否包含指定的键
@Override public boolean containsKey(Object key) {
//判断是否包含空键
if (key == null) {
return entryForNullKey != null;
}
//根据key计算hash值
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
//这里的遍历方式和之前的getKey(K key)方法一样
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return true;
}
}
return false;
}6 containsValue(Object value)
判断是否包含指定值
@Override public boolean containsValue(Object value) {
HashMapEntry[] tab = table;
int len = tab.length;
//如果指定的值为空
if (value == null) {
//先遍历数组中的元素
for (int i = 0; i < len; i++) {
//再遍历每一横排的元素
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (e.value == null) {
return true;
}
}
}
//如果前面遍历没有找到相应的空值，就返回单独存在的entryForNullKey对应的值。
return entryForNullKey != null && entryForNullKey.value == null;
}
//如果指定的值不为空 和之前的遍历方式一样。
// value is non-null
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (value.equals(e.value)) {
return true;
}
}
}
return entryForNullKey != null && value.equals(entryForNullKey.value);
}7 put(K key, V value)
向HashMap中添加一个元素
@Override public V put(K key, V value) {
//如果键为空，就把单独存在的entryForNullKey节点赋值value
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
//根据key算出的hash值找到某一排的头节点，并根据这个头节点，遍历这一排
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { //根据key得出的hash值和键同时相等，说明找到了这个节点，把这个节点的值替换为value
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// 如果没有找到相应的键 根据index重新创建一个头节点
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}putValueForNullKey(V value)
放一个key=null对应的值
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
addNewEntryForNullKey(value);
size++;
modCount++;
return null;
} else {
preModify(entry);
V oldValue = entry.value;
entry.value = value;
return oldValue;
}
}