简介
HashMap是一个比较常用的键值对集合，在开发中常用于映射关系。以下分析是基于Android中API25下的源码
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
HashMap属于map族类，并且默认实现Serializable，可用于网络传输和本地序列化。
基础属性
/**
* HashMap的默认初始容量，必须是2的倍数
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* HashMap的最大容量，必须为2的倍数
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的扩容因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* HashMap为空时候共享的空数组
*/
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
/**
* HashMap里面的存储数组
* 每一个数据都是一个HashMapEntry，而HashMapEntry本质上是一个单项链表
*/
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
/**
* HashMap中键值对的数量
*/
transient int size;
/**
* 临界值决定什么时候进行扩容(当前容量 * 扩容因子)
*/
int threshold;
/**
* 扩容因子，一个比例，相对于当前容量来说
* Android中只会使用0.75，而会忽视其它的数值
*/
final float loadFactor = DEFAULT_LOAD_FACTOR;
这里可以看到HashMap的基础存储结构：
存储结构
后面会详细看到具体的意义。
构造
/**
* 创建一个空的HashMap
*
* @param initialCapacity 初始化容量
* @param loadFactor 扩容因子，在Android中实际上并没有用，还是采用默认的0.75f
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//容量不能小于默认容量和大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;//1 << 30
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;//4
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 实际上每次扩容的时候threshold都会重新计算
threshold = initialCapacity;
init();//默认空实现，子类可以尝试实现这个方法做一些插入之类的操作
}
/**
* 创建一个空的HashMap，容量为4，扩容因子0.75
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 从其它的HashMap上面复制一份
*
* @param m 想要复制的HashMap
*/
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);
}
/**
* 当HashMap为空的时候初始化当前HashMap
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
//下一次扩容的大小为当前容量*扩容因子
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];//构建一个容量大小的数组
}
/**
* 找到一个比number大的2的倍数
*/
private static int roundUpToPowerOf2(int number) {
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
/*稍微拆解一下方便理解
if(number >= MAXIMUM_CAPACITY){
rounded = MAXIMUM_CAPACITY;//不允许超过最大容量
}else{
//首先将number转为2进制表现形式，比方说00100101
//通过highestOneBit则rounded为00100000
//找出最高位的1，其余位朴0
rounded = Integer.highestOneBit(number);
if(rounded != 0){
//如果number的2进制中不止1个1,比方说00100101
//因为highestOneBit其余位朴0，得到rounded为00100000
//所以获得要大于number的2的倍数，需要再乘以2，则rounded左移一位即可
rounded = ((Integer.bitCount(number) > 1) ? rounded << 1 : rounded);
}else{//如果number为0，容量取1即可
rounded = 1;
}
}*/
return rounded;
}
/**
* 将指定map的数据放入当前HashMap中
* @param m 需要添加的数据
*/
private void putAllForCreate(Map<? extends K, ? extends V> m) {
//实际上就是遍历一遍指定map，然后一个个添加到当前HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
/**
* 该方法不会重新进行扩容操作
* 只有在构造的时候复制map之类的场景下才会使用
*/
private void putForCreate(K key, V value) {
//计算key的hash值
int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//计算出当前key在table的下标
int i = indexFor(hash, table.length);
//下标已经计算成功
//在当前table的链表中先查找是否有相同key的元素，有的话直接设置，不新建
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {//遍历单向链表
Object k;
//key的hash值相同
//key是同一个引用或者key的equals相同
//此时直接复写value即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//当前table的链表中没有当前key，在链表当中新建一个节点
createEntry(hash, key, value, i);
}
/**
* 通过key的hash值和当前HashMap的容量
* 计算出当前node在table中的下标
*/
static int indexFor(int h, int length) {
//假设h:0000 1110 length:0000 1000
//0000 1110 h
//0000 0111 length - 1，刚好将前面的所有位朴1
//0000 0110 结果
//结果必然是小于length
//而且从这个计算也知道，length必须是2的倍数
return h & (length-1);
}
/**
* 在指定的链表末尾添加一个节点
* @param hash 当前要添加节点的key的hash值
* @param key 当前要添加的节点的key
* @param value 当前要添加的节点的value
* @param bucketIndex 当前链表在table[]中的下标位置
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];//从table中获取链表
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);//新建一个HashMapEntry并且添加到链表中
size++;//HashMap的大小+1
}
从HashMap的拷贝型构造函数的实现可以看出，为了更快的计算table[]的下标，HashMap中的容量都是2的倍数，每一个table[i]都维持着一个链表。
链表结构
先看一下table[i]中的链表结构
/**
* Android添加的
* 单向链表结构，每一次新建的时候会把节点放在链表的头部
* @hide
* */
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;//当前节点的key
V value;//当前节点的value
HashMapEntry<K,V> next;//当前节点的下一个节点
int hash;//当前节点的key的hash值
/**
* 创建一个新的节点，并且将当前节点放到指定链表的头部
*/
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;//这样实现的效率极高
key = k;
hash = h;
}
//...省略一些
}
HashMapEntry一个单向链表结构，每一次新建的时候直接把当前节点放到指定链表的头部，操作效率极高。
基本操作
/**
* 将指定键值对添加到当前HashMap中
* @param key 键值
* @param value 键值
* @return 如果当前是覆盖操作，返回被覆盖的原来的value，否则为null
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//当前HashMap为空
inflateTable(threshold);//初始化HashMap，此时会构建好table[]、容量和扩容值
}
if (key == null)//HashMap支持null作为key
return putForNullKey(value);
//计算key的hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通过hash值计算出对应table[]下标
int i = indexFor(hash, table.length);
//先尝试复写当前table[]的链表中“相同”的key的value
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//这里可以看到如果hash值直接相等是效率最高的
//否则走equals
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//当前链表中没有指定key的节点，新建一个节点并且添加到链表当中
addEntry(hash, key, value, i);
return null;
}
/**
* 当添加到HashMap中的键值对的key为null的时候
* @param value key为null对应的value
* @return 如果当前是覆盖操作，返回被覆盖的原来的value，否则为null
*/
private V putForNullKey(V value) {
//可以看到key为null的时候，默认hash为0
//先遍历table[0]的链表，看是否需要覆盖
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {//如果当前节点key为null，直接覆盖value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);//否则新建一个节点并且添加到链表当中
return null;
}
/**
* 新建一个节点并且添加到指定的链表的头部
* @param hash 需要添加的key的hash值
* @param key 需要添加的节点的key
* @param value 需要添加的节点的value
* @param bucketIndex 需要添加到table[]的下标
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//先判断是否需要进行扩容操作
if ((size >= threshold) && (null != table[bucketIndex])) {
//当前大小已经到了容量*扩容因子的标准
//以当前容量为基准，直接扩大一倍的方式进行扩容
resize(2 * table.length);
//重新计算hash值
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
//根据最新的table[]的长度计算table[]下标
bucketIndex = indexFor(hash, table.length);
}
//新建节点并放在放在table[bucketIndex]链表的头部，大小+1
createEntry(hash, key, value, bucketIndex);
}
/**
* 扩容操作
* 当HashMap添加数据的时候发现已经到了扩容标准
* 则进行扩容
* @param newCapacity 当前希望的新的容量
*/
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;//记录旧的table[]
int oldCapacity = oldTable.length;//记录旧的容量
if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的容量已经是最大容量，无法进行扩容
threshold = Integer.MAX_VALUE;//修改扩容基准为最大容量
return;
}
//根据当前扩容后的容量新建一个table[]
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;//转换table[]为最新的表
//容量变化，重新计算下一次扩容的基准
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 当进行扩容的时候，需要将旧的table[]数据转移到当前新的table[]上面
* @param newTable 扩容后新建的table[]
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;//扩容后的大小
//遍历旧的table[]，将旧的节点转移到新的table[]中
for (HashMapEntry<K,V> e : table) {
while(null != e) {//遍历当前table[i]链表
HashMapEntry<K,V> next = e.next;
//通过每一个节点的hash值重新计算table[]的下标
int i = indexFor(e.hash, newCapacity);
//将当前节点放到新的table[]的链表的头部
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
/**
* 从HashMap中获得指定key对应的value
* @param key 需要查找的key，支持null
* @return value，没有的话为null
*/
public V get(Object key) {
if (key == null)//key为空，直接查找table[0]即可，相对于getEntry节省了indexFor的开销
return getForNullKey();
Map.Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* 当key为null的时候，获取指定的value
* 如果有key为null的节点，必然位于table[0]的链表且唯一
* @return value，没有的话为null
*/
private V getForNullKey() {
if (size == 0) {//当前HashMap还没有数据
return null;
}
//遍历table[0]，尝试获得key为null的节点的value
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/**
* 根据指定的key获得HashMap中对应的节点的value
*/
final Map.Entry<K,V> getEntry(Object key) {
if (size == 0) {//当前HashMap还没有数据
return null;
}
//计算key的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//先计算hash值对应的table的下标
//然后遍历对应table[]的链表
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//这里可以看到如果hash值直接相等是效率最高的
//否则走equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
* 从HashMap中移除指定key的节点
* @param key 键值对中的key
* @return 被移除的key节点对应的value
*/
public V remove(Object key) {
Map.Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
/**
* 从HashMap中移除指定key的节点
* @param key 键值对中的key
* @return 被移除的key节点
*/
final Map.Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {//当前HashMap还没有数据
return null;
}
//计算key的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通过hash值计算出对应table[]下标
int i = indexFor(hash, table.length);
//记录当前table[]链表的头结点
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
//从头开始遍历当前链表
while (e != null) {
HashMapEntry<K,V> next = e.next;//获得当前节点的下一个节点
Object k;
//这里可以看到如果hash值直接相等是效率最高的
//否则走equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
//删除当前节点
modCount++;
size--;//HashMap大小-1
if (prev == e)//当前需要删除的节点是链表的头结点
table[i] = next;//直接标记当前链表的头结点为下一个节点
else//删除链表非头结点的节点
prev.next = next;//将当前节点的上一个节点直接指向当前节点的下一个节点，从而当前节点从链表中移除
e.recordRemoval(this);
return e;
}
prev = e;//记录当前节点为前置节点
e = next;//继续遍历下一个节点
}
//如果遍历之后没有找到对应的key，此时链表的最后一个节点为null，这里直接返回null即可
return e;
}
/**
* 查找是否包含某一个key的节点
*/
public boolean containsKey(Object key) {
//实际上就是查找一边当前key的节点，如果节点不为空则包含
return getEntry(key) != null;
}
HashMap的核心操作就是put和get，并且支持key为null的情况。
put的时候首先尝试覆盖旧的节点，所以要先计算hash值找到对应链表，然后遍历链表寻找，如果没有，则需要新建，在新建之前要判断是否达到容量*扩容因子的基准，如果达到，首先要进行扩容操作。
扩容会将当前容量增加一倍的大小，然后还需要遍历将旧的table[]链表中的节点转移到新的table[]中，并且这个过程中还需要根据hash重新计算节点位于table[]的下标。
get操作首先计算key对应的hash值，然后获得对应的table[]的节点链表，进而遍历链表查找对应的节点并且返回value。
总结
从上面可以看到，HashMap中会有不少遍历链表的操作，这个其实就说明hash散列的重要性，如果不同的值但是最后放到了同一个table[i]的链表中，会导致某一个链表特别长，这样对于遍历效率来说不是太好。
扩容操作需要转移旧的节点等操作，所以说对于已知初始容量的HashMap来说，最好是指定容量，避免多余的扩容操作。
HashMap并不是线程安全的，如果多个线程对链表进行操作，会造成不可预期问题，此时应该尝试ConcurrentHashMap或者Collections.synchronizedMap()。
网友评论