如果我在介绍集合的时候不介绍HashMap我相信一定会有人觉得我是个奇葩。毕竟是这么这么重要的类嘛。本篇开始进入Map阶段，相应地会提到HashMap,ConcurrentHashMap,TreeMap等。作为实习以及平时日常使用的出现频率最高的集合工具类，他被使用的场景我已经无须再描述了。因为其的重要性，在本篇我们将关注它的任何一个细枝末节。
==因为HashMap在JDK1.7和1.8的实现中变化比较大，所以我们先介绍1.7中的HashMap==
源码分析
注释导读
- 允许null的key和null的value
- 不保证遍历顺序，多次遍历顺序可能不一致
- 提供常量的时间复杂度，希望在合适时候设置初始容量(不宜过大或者过小)
- 0.75的factor一般情况不希望改变
- 能避免就尽量避免rehash
- 不是线程安全，如果要求线程安全可以使用Collections.synchronizedMap()
- 遍历过程一旦改变元素就立马抛出错误
类定义
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
对于AbstractMap如果现在介绍的话到后面可能会忘记，所以就在HashMap引用父类相关方法的时候在分别介绍。
map.JPG
Map接口的所有内容都在上图，上层接口提供的都是一些通用的方法，重点是这个Entry类。
Entry接口其实作为一个<K,V>的对出现，代表了这一对pair的组合,它有定义自己的getKey()和getValue()方法，同时也有自己的equals和hashCode方法的复写。在Map类内部对于数据的操作都要借助于Entry来进行，它才是Map类内部真正核心的局部容器。
基本属性
/**
* 初始容量，一定是2的N次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的因子.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 承载Entry数据的核心数组
*/
transient Entry<K,V>[] table;
/**
* Map中元素的数量
*/
transient int size;
/**
* 需要进行扩容的阈值
*/
int threshold;
/**
* 实际容器的因子(不提供的话就用DEFAULT_LOAD_FACTOR)
*/
final float loadFactor;
/**
* 结构内容更新的次数(遍历时候使用)
*/
transient int modCount;
/**
* 系统默认的扩容阈值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* 如果这个值为true，就使用另外一个hash算法来减少碰撞
*/
transient boolean useAltHashing;
/**
* 为hash算法提供一个种子
*/
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
/**
* 为获得Entry提供一种方便的操作结构
*/
private transient Set<Map.Entry<K,V>> entrySet = null;
核心内部类
//核心静态内部类Entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
//因为HashMap是采用链表法处理哈希冲突的，所以Entry需要有一个指向下一个节点的指针
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//final修饰主要为了防止子类覆盖
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o; //这个步骤上面一定要有instanceof判断，否则出现ClassCastException
Object k1 = getKey();
Object k2 = e.getKey();
//这里值得学习的地方就是时刻保持对Null的警惕
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
//hashCode的计算就是要保证key和value全部相等(要考虑null的情况)
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* 在put操作调用的时候如果存在相同的key就触发下面的操作
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 当entry被移除的时候触发下面操作
*/
void recordRemoval(HashMap<K,V> m) {
}
}
//内部抽象类HashIterator
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // 下一个返回的entry
int expectedModCount; // 为了快速失败
int index; // 当前的slot位置
Entry<K,V> current; // 当前的entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
//定位到第一个位置不为null的slot,我们知道HashMap内部的容器是一个数组，数组的实体为Entry，而每一个Entry又相当于LinkedList 的Node节点一样，
//它后面可能跟了很多Entry(链表法)，所以在遍历的时候肯定需要定位到第一个不为空的slot
//图解见下
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
//遍历过程如果进行结构改变将直接抛出错误
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
//如果当前节点是最后一个节点
if ((next = e.next) == null) {
Entry[] t = table;
//继续将index定位到下一个不为null的slot
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null) //多次remove同一对象就报错
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null; //help GC
//这个remove操作我们后面讲
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
//这三个方法完全是基于上面的抽象类
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();//KeySet->KeyIterator->HashIterator
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
无论是key还是value的单独操作，都是依赖于Entry接口的，提供这些其他的接口就是为了方便我们单独处理key或者value，因为我们再使用map的时候一般不会直接使用Entry
HashMap.JPG
所以通过Iterator进行遍历的时候顺序就是先遍历slot:0里面的每一个entry，然后遍历slot:2里面的对象然后依次进行。
构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//loadFactory要合法
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 找到一个最小的2的N次幂使其大于等于 initialCapacity
// 例如: initialCapacity = 2 -> capacity = 2
// 例如: initialCapacity = 3 -> capacity = 4
// 例如: initialCapacity = 15 -> capacity = 16
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
//当现在的容量超过了ALTERNATIVE_HASHING_THRESHOLD值后就采用不同的Hash策略
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init(); //空方法，供子类扩展
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 默认就是16,0.75f的组合
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
//m.size() / DEFAULT_LOAD_FACTOR) + 1:在不进行扩容的前提下的最小的阈值
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m); //后面统一看这些插入操作
}
常用方法
说道常用方法我就忍不住要先说put和get这两个高频出现的方法了。哈哈哈哈
public V put(K key, V value) {
if (key == null) //允许null的key和null的value
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;
//保证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);
return null;
}
//统一把所有的key为Null的值放在slot:0的位置
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { //初始化的时候已经初始化过table了所以不用担心e = null导致NPE
V oldValue = e.value;
e.value = value;
e.recordAccess(this);//没有实现，留给子类实现
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
//bucketIndex及我所说的slot
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果超过了阈值并且要插入的位置已经有元素存在就扩容(我们在日常使用中应在进行避免扩容，能指定尽量指定HashMap的初始容量)
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //扩容为原来的2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length); //重新定位到目标bucketIndex
}
//前面都是定位扩容操作，最后就是将节点连接到table数组中
createEntry(hash, key, value, bucketIndex);
}
//在增加Entry的时候直接进行连接
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//原容量已经最大了就不进行扩容了,但是阈值调整为Integer的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//如果两个值一样rehash=false, 不一样的话rehash=true
//rehash是否进行根据现阶段的调整策略
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash); //将原来的元素移到新的table中
table = newTable;
//table都整体增长了所以阈值也要进行调整
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) { //在每一个slot上进行遍历取到所有元素
Entry<K,V> next = e.next;
if (rehash) { //根据参数重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}//算出要进行添加的slot位置
int i = indexFor(e.hash, newCapacity);
//将新元素作为头结点进行添加，不作为尾节点添加的原因是这样简单，而且不用考虑空元素
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
//哈希散列算法(有人可能会问，Object对象都有自己的hashCode()方法了问什么还再实现一个，这个Hash算法是为了是元素分布更在均衡，减少碰撞。)
final int hash(Object k) {
int h = 0;
if (useAltHashing) { //加入JVM自己的实现
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
//对以下具体hash算法的原理实现不太了解
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 根据Hash值取得其在table中应该插入的位置，这里实现极为巧妙，也解释了为什么要求table的长度一定是2的n次方
* 初始化capacity = 16,转换为二级制就是10000,假设目前一个元素的hash值为80，也就是1010000.
* 现在 16 & 80 = 0001111 & 1010000 = 0000000 = 0(十进制) 所以插入位置就是0 这种巧妙就是利用了数组长度-1后的所有二级制为全是1的特性，巧妙实现了取余的算法。
* 因为硬件内部底层是支持&运算的(数字电路)，所以这样操作效率比%高。
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
=======================================================
put操作相关的方法都在上面进行了介绍，下面让我们看看另外一个高频使用方法get吧。
public V get(Object key) {
if (key == null)
return getForNullKey(); // null key
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
//在上面的介绍中我们知道null key全部放在table[0]的位置
for (Entry<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) {
int hash = (key == null) ? 0 : hash(key);
//第一步定位slot
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//注意这里的判断，hash相等是必要条件(Entry的hash已经被复写过，我们在插入元素的使用，Entry的hash值即为其key的hash值)，key相等或者满足equals都可以
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
因为get方法不包括扩容等操作，也不会改变现在的结构，所以比较简单。
我们再来看看最后一个高频方法contains
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
//这里没有什么技巧，只不过我觉得tab应该用final修饰一下会更好
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
//把上面的方法最后的比较从equals换成了 == null 而已
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> 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; //这里e仍然可能保留了指向后面元素的指针，我觉得应该加e.next = null
}
prev = e;
e = next;
}
return e;
}
public void clear() {
modCount++; //这里可不是modCount变了很多噢
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}
//这个克隆是浅克隆(Entry还是原来的Entry，指针是一样的)
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
result.table = new Entry[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
//上面有介绍过这个方法
result.putAllForCreate(this);
return result;
}
到这里，JDK1.7的HashMap已经全部都介绍完了。我们从源码中看不到任何关于同步的操作，所以多线程环境下使用的话还是需要多点注意的。下一篇我会讲讲JDK1.8中的HashMap，敬请期待.
