简介
HashMap 在 Android 开发中还算是使用频率较高的，而且面试中面试官也常常会问 HashMap 的原理，无论是从技术上还是面试上都得应该好好捋顺 HashMap。HashMap 在 JDK 1.7 版本与 JDK 1.8 版本的实现上差异还是比较大，主要差异可以查看这篇文章 HashMap 在 JDK 1.8 与 JDK 1.7 上实现的差异比较，这一篇是基于 JDK 1.7 版本的源码进行分析。
- 类定义如下：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
结合源码可以得知 HashMap ：
- 实现了 Map 接口，进而提供了 Map 接口中的通用操作方法。
- 实现了 Cloneable 接口，即可进行拷贝，不过注意的是如果没有拷贝对象进行处理，默认实现的浅层次拷贝。
- 实现了 Serializable 接口，即可实现序列化。
- 允许键 / 值 为 null，但是最多只允许一条记录的键(key)为 null，而允许多条记录的值(value)为 null 。
- 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致甚至造成死锁，可以通过 Collections.synchronizedMap 获得线程安全的 HashMap，或者使用 ConcurrentHashMap 。
- 不保证有序（如插入顺序），也不保证不随时间变化。
存储结构
HashMap 使用哈希表也叫散列表来存储数据的，哈希表为解决冲突，可以采用开放地址法、链地址法等来解决问题，Java 中 HashMap 采用了链地址法，即+
的形式，如下图所示（通过 key 查找 value）：
HashMap 中有个 Entry 类，就是上图中的绿色的数组元素 & 链表节点：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
// 指向下一个节点
Entry<K,V> next;
final int hash;
// 构造函数。
// 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
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;
}
// 判断两个Entry是否相等
// 若两个Entry的“key”和“value”都相等，则返回true。
// 否则，返回false
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
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()
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
// 当向HashMap中添加元素时，绘调用recordAccess()。
// 这里不做任何处理
void recordAccess(HashMap<K,V> m) {
}
// 当从HashMap中删除元素时，绘调用recordRemoval()。
// 这里不做任何处理
void recordRemoval(HashMap<K,V> m) {
}
}
Entry 类实现了 Map,Entry 接口，本质上就是一个映射。
HashMap 中的重要术语
- 容量（capacity）: HashMap中数组的长度，必须是 2 的整数次幂，初始容量是 16，最大容量是 2 的 30 次方，如果我们传入的初始容量不是 2 的整数次幂，HashMap 会自动校正为 2 的整数次幂，代码如下：
// 找出“大于initialCapacity”的最小的2的幂
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
// 设置“加载因子”
this.loadFactor = loadFactor;
// 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
threshold = (int)(capacity * loadFactor);
// 创建Entry数组，用来保存数据
table = new Entry[capacity];
- 加载因子（load factor），HashMap 在扩容前达到的多满的一种尺度，加载因子越大，填满的元素就越多，带来的结果是空间利用率高，冲突的机会加大，进而使查找效率变低（链表长）；反之，加载因子越小，填满的元素越小，带来的结果是空间利用率小、冲突机会减小，查找效率高（链表短）。默认的加载因子是 0.75，一般是不需要修改这个值，这是一个衡量了时间与空间效率之后的选择。除非在特殊的情况下，比如说内存空间很多而又对时间效率要求很高的时候，可以降低加载因子的值；而如果内存空间非常紧张而对时间效率不高，可以增加加载因子的值，这个值可以大于 1 。
- 键值对数量（size），即往 HashMap 插入条目的数量。
- 扩容阈值（threshold），当 HashMap 的键值对数量（size）大于等于扩容阈值时，就会执行扩容机制（resize），从而使哈希表具有两倍的桶数。扩容阈值（threshold）= 容量（capacity）x 加载因子（load factory）。
功能实现
1. 确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。由于 HashMap 的数据结构是数组加链表的形式，理想的情况是元素分布均匀，每个位置上的元素数量只有一个，这样当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素是我们要的，不用遍历链表，极大地提高了查询的效率。JDK 1.7 的实现如下：
第一步：
//将键 key 转换成 哈希码（hash 值）操作 = 使用 hashCode() + 4次位运算 + 5次异或运算（9次扰动），
//加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少 Hash 冲突。
static final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4)
}
第二步：
// 将对哈希码扰动处理后的结果与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
static int indexFor(int h, int length) {
return h & (length-1);
}
总的来说，就是 取 key 的 hashCode 值、高位运算、取模运算。
对于任意给定的对象，只要它的 hashCode() 方法返回值相同，那么程序调用第一步所计算得到的 Hash 值总是相同的，由于直接取模操作（）消耗还是比较大的，HashMap 实现上采用了一个比较巧妙的方法，h & (table.length -1)，由于 HashMap 底层数组的长度总是 2 的 n 次方，h & (table.length -1) 等价于对 length 取模（h % table.length），但是效率大大提升了。
2. HashMap 的 put 方法
HashMap 中的一个核心方法就是 put 方法了，代码如下:
// 将“key-value”添加到HashMap中
public V put(K key, V value) {
// 若“key为null”，则将该键值对添加到table[0]中。
if (key == null)
return putForNullKey(value);
// 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 若“该key”对应的键值对不存在，则将“key-value”添加到table中
modCount++;
addEntry(hash, key, value, i);
return null;
}
这里再将大概流程串一下：
- ① 判断 key 值是否为 null，如果为 null ，则执行 putForNullKey() 方法将其对应的值添加到 table[0] 位置。
- ② 根据键值 key 计算得到插入到数组的索引 i ，遍历索引 i 对应的单链表，如果该 key 对应的键值对已经存在，则用新值替代旧值，并返回旧值。
- ③ 如果 key 值对应的键值对不存在，则调用 addEntry() 方法将键值对添加到 HashMap 中。
addEntry() 方法源码如下：
// 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 保存“bucketIndex”位置的值到“e”中
Entry<K,V> e = table[bucketIndex];
// 设置“bucketIndex”位置的元素为“新Entry”，
// 设置“e”为“新Entry的下一个节点”
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 若HashMap的实际大小不小于 “阈值”，则调整HashMap的大小
if (size++ >= threshold)
resize(2 * table.length);
}
结合 Entry 的构造方法，我们知道这里以单链表头插法形式添加键值对。同时，判断HashMap 当前的 size 是否大于 threshold，如果是的话则进行扩容。
3. 扩容机制
扩容（resize）就是重新计算容量，向 HashMap 对象里不停地添加元素，而 HashMap 内部的元素大于等于扩容阈值（threshold）时，则会扩大 HashMap 内部数组的长度，以便装入更多的元素。当然 Java 里面的数组是无法进行扩容的，方法是使用一个新的数组代替已有的容量小的数组。resize() 方法源码如下：
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的 Entry 数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到（2^30）了
threshold = Integer.MAX_VALUE; //修改阈值为 int 的最大值（2^31-1），这样以后都不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的 Entry 数组
transfer(newTable); //用来将原先table的元素全部移到newTable里面
table = newTable; //再将newTable赋值给table
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
transfer() 方法使用一个容量更大的数组来代替已有的容量小的数组，源码如下：
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
newTable[i] 的引用赋给了 e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，这样先放在一个索引上的元素会放到 Entry 链的尾部（如果发生了 hash 冲突的话），在旧数组中同一条 Entry 链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。
transfer 过程中，假设重新计算后链表上的元素对应在 table 中的索引也一样，则会出现链表逆序的情况，即
扩容前 a->b->c ; 扩容后 c->b->a
此时如果并发执行 put() 方法，一旦出现扩容情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环，即死锁的状态。
4. HashMap 的 get 方法
HashMap 的另一个核心是 get() 方法，源码如下：
// 获取key对应的value
public V get(Object key) {
if (key == null)
return getForNullKey();
// 获取key的hash值
int hash = hash(key.hashCode());
// 在“该hash值对应的链表”上查找“键值等于key”的元素
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
// 获取“key为null”的元素的值
// HashMap将“key为null”的元素存储在table[0]位置！
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
在理解了上面 put() 方法的原理，get() 就非常好理解了，即：
- ① 判断 key 值是否为 null，如果是 null 的话，调用 getForNullKey() 方法到 table[0] 为头结点的链表中寻找 key == null 的对应的值并返回。
- ② 计算 hash 码和在 table 数组中的索引，同 put() 方法一样。
- ③ 遍历以该索引的数组元素为头结点的链表，如果 key 的 hash 码相等且 key 的equals() 方法相等，则返回 key 对应的 值。
拓展
1.为什么说 HashMap 是线程不安全的？如果在迭代器中并发改变 HashMap 数据会怎样？
因为 HashMap 中进行数据操作时并没有进行同步操作，而且多线程下并发执行 put() 方法触发扩容机制时，会导致形成环形链表，造成死循环。
如果使用迭代器的过程中有其他线程修改了 map，则会抛出 ，这就是所谓的 fail-fast 策略，其原理是通过 modCount 域，modCount 顾名思义就是修改次数，对 HashMap 内容（当然不仅仅是 HashMap 才会有，其他例如 ArrayList 也有）的修改都将增加这个值，在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount，修改数据时，判断 modCount 和 expectedModCount，如果不相等，则表示有其他线程修改了 HashMap，即抛出异常；反之相等的话，则表示没有其他线程修改 HashMap。
2. 为什么String, Interger 这样的wrapper（包装类）类适合作为键？
因为 String 是不可变的，即是 final 的，而且已经有重写了 equals() 方法和 hashCode() 方法了，其他 Wrapper 类也有这个特点。不可变性是必要的，因为为了计算 hashCode ，就要防止键值改变，如果键值在放入时和获取时返回不同的 hahCode 的话，那么就不能从 HashMap 中找到想要的对象。不可变性还有其他的优点如线程安全。
3. HashMap 中的 key若 Object类型， 则需实现哪些方法？
HashCode() 方法和 equals() 方法。
总结
至此，基于 JDK 1.7 的 HashMap 的分析已经结束，相信大家对 HashMap 原理有一个大致把握，想要看看 JDK 1.8 上做了哪些变更，可以查看这篇文章 HashMap 在 JDK 1.8 与 JDK 1.7 上实现的差异比较。
此外，当数据量不大时，Android 上更推荐使用 SparseArray 或者 ArrayMap，有兴趣可以点击以下链接：
网友评论