HashMap 应该是开发中最常用的数据结构之一了，理解其原理能让我们在合适的时机用正确的方式使用它。
目录
一、结构
- 内部类及成员变量
- 构造方法
- 图解
二、调用原理
- put
- get
- remove
- 迭代
三、总结
一、结构
1. 内部类及成员变量
Node 内部类：单链表数据结构，是理解 HashMap 结构的关键，内部存储：hash（对 key 的 hashCode值的高低位异或，后面有解释）、key（传进来的键）、value（传进来的值）、next（指向下一个 Node 节点）。
TreeNode 内部类：红黑树数据结构，这里对红黑树做一个简单的解释，它是一种平衡二叉搜索树，二叉搜索树即是每个节点的左子节点的值小于父节点的值，右子节点的值大于父节点的值，平衡的意义在于二叉树插入的数据如果一直是最小或最大的值，那么其实他会退化成链表，因此需要插入的时候做一些调整，尽量能达到左右子树的平衡。说了这么多，为什么要转换成红黑树？因为完全二叉树的查找效率是 O(logn), 比链表的查找效率 O(n) 快太多了，所以一旦碰撞变多，散列表的单链表查找效率就会变慢。红黑树非常复杂，若是对其有兴趣可以专门去研究下，不建议在看 HashMap 的时候去理解它。。本文讲解会对这块内容跳过。
table：散列表，用 Node<K,V>[] 声明，表示一个数组，我们把每个条目称作 bucket 桶，把桶内单链表 node 的每个元素称之为节点。
size：所有键值对的数量，即节点的个数。
modCount：散列表内修改次数，用来判断 HashMap 是否被多线程修改中，如果是则要抛出异常。
threshold：阈值 = capacity（容量） * loadFactor（装载因子），当数组中元素数量超过这个值说明该扩容了，初始容量默认是 16，要根据自己的业务场景设置一个适合的容量大小，太大会造成内存消耗以及迭代耗时，太小会造成多次扩容。
loadFactor：装载因子，由它决定阈值，默认是0.75。loadFactor 也要适合自己业务场景来自定义，一般情况用默认的没问题。
2. 构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
如果不指定此构造方法的两个参数，那么就是使用默认的 capacity = 16 和 loadFactor = 0.75, 这段代码判断了初始容量的合法性以及保存装载因子，tableSizeFor 这个方法主要是调整下初始容量，HashMap 强制容量是2的幂次方，如果给了 13 的初始容量，那么这个方法就会调整为 16。
3. 图解
下图能比较清晰的看到 HashMap 的结构：
HashMap
蓝色矩阵代表 Node 单链表, 蓝色圆形代表 TreeNode 红黑树。正常情况下都会是单链表，当单链表节点的数量超过 8 个的时候会转换成红黑树的结构（这个只是随便画的。。），红黑树虽说定义是平衡二叉树，但他不一定是完全二叉树，只是相对来说保持平衡。
二、调用原理
1. put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
直接调用了 putVal 去做真正的存储工作，在此之前先看下 hash(key) 方法。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个 hash 函数可以说是极其精美了，获取了 key 的 hashCode 将其高16位与低16位异或得到最终的 hash 值。对高低位异或的原因是，key 的散列值最终需要对数组长度取模，这个时候如果很多 key 的散列值低位都相同咋办？因此和高位异或就能让高位也参与计算，会降低碰撞的概率。而这么做并不是说让碰撞的概率很小，只是这样能大大降低概率而且计算还非常简洁，不会耗费性能。如果碰撞多了，那就用红黑树来解决。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果散列表是空的，表示这是第一次调用 put 那就创建一个散列表， resize 方法后面解释
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 对 hash 值取模，找到散列表中对应的索引，如果此索引下没有元素，
// 那么新建一个 Node 节点将hash、key、value保存进去
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 每个数组对应索引的元素都是一个单链表或红黑树，
// 根据 hash 值和 key 判断 put 进来的 key 是否已存在，若存在则替换 value。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 红黑树结构的插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 数组的 Node 节点是存在的，并且单链表的头结点并不是要插入的节点，
// 那么遍历这个单链表，如果找到相同点则替换，没找到就插入到尾部
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果单链表的节点数达到 8 个，就将单链表转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到相同 key 的节点，那么就替换原来的值，
// onlyIfAbsent可以控制不替换原来的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 空实现，只有在LinkedHashMap会用到，因此不用管
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 若达到阈值，则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
代码中的注释已经对每个关键的部分做了解释。 put 可以简单分为三个阶段：
- 首次 put 创建散列表。
- 插入的节点若存在则替换原有节点的值，否则插到单链表的尾部或红黑树中。
- 若超出阈值则扩容。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 之前散列表已经被创建
if (oldCap > 0) {
// 大于最大容量，就永远不扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新容量是老容量的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 表示散列表还未被创建，新容量就等于用户设置的初始容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 散列表未被创建，用户又没有设置初始容量，那就用默认的
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 单链表节点只有一个，那就直接重新计算 bucket 索引 index 并移交到新散列表
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 红黑树移到新散列表，暂不深究
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 单链表loHead从老散列表移到新散列表中 index 不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 单链表hiHead从老散列表移到新散列表中 index + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 即使索引变化也是有规律的
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize 扩容方法主要做两件事：
- 新容量扩充为老容量的2倍，阈值也增大两倍。若是首次创建则新容量为初始容量。然后通过新容量创建新散列表。
- 将老散列表的元素移到新散列表中。这里有个规律：由于容量是2倍增长，因此元素的 hash 值取模要么结果不变，要么 索引 = 原索引 + 老容量大小。
以下是扩容图解：
resize
蓝色矩阵表示早已添加到散列表的节点，黄色矩阵表示刚插入的一个节点。
假定 HashMap 的初始容量 capacity 是 4, loadFactor 是 0.75 , 此时插入一个节点，那么容量就超出阈值（4 * 0.75 = 3），于是就发生扩容了。图上的 hash 那一列表示 key 的 hashCode 后四位（hashCode本来是32位，为了节省空间只写后4位），可以看到根据 hash & (capacity - 1), 就可以知道各个节点索引位置，如 0001 & 0011 = 0001 即 index 为 1 这个位置。因此当容量增加两倍后 (capacity - 1) = 0111, 可以发现和老容量的差别就在于右数第三位从 0 变成了1, 所以 key 的 hashCode & (capacity - 1) 其他位都是一样的，只是右数第三位要么是 0 要么是 1, 如果 hashCode 的右数第三位是 1 代表索引在原来的基础上增加原来容量的大小即 + 4, 如果是 0 那么还是在原来的索引上，直接放到新散列表的对应位置，这个操作只会遍历数组长度，而不会对单链表的每个节点重新计算索引，节省了时间，对性能有提高。
2. get
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 散列表不为空并且通过 hash 找到对应 bucket 的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 单链表头节点就是要找的目标节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 已经转换成红黑树了
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表内遍历查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
同样代码做了清晰的注释。调用 get 方法后会计算出 key 的 hash 值并调用 getNode 方法，getNode 里面做的事情也非常清楚，找到对应 bucket 下是否有节点，如果有则从单链表内遍历查找或在红黑树内查找。
3. remove
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 以下部分与 get 查找基本一样，找到要删除的节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到 key 对应的节点，还要看看 value 的情况。
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 红黑树删除
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 要删除的节点处在单链表的头节点
else if (node == p)
tab[index] = node.next;
// 前驱节点指向目标节点的后一个节点，这个操作表示移除了 node 节点
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
remove 做了两件事：
- 前半部分代码和 get 方法很类似，其实本质上就是找到想要移除的节点，p 节点是 node 节点的前驱节点。
- 根据找到的目标节点 node，如果用户使用 remove 时传入了 key 和 value，那么还需要匹配 value 才行，匹配成功后用 p 节点指向 node 节点的后一个节点即可，这样 node 节点就会被删除。红黑树删除源码不深究。
4. 迭代
Map<String, String> map = new HashMap<>();
// foreach 遍历 entries
for(Map.Entry<String,String> entry: map.entrySet()) {
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
// foreach 遍历 keys
for(String key: map.keySet()) {
System.out.println("key = " + key);
}
// foreach 遍历 values
for(String value: map.values()) {
System.out.println("value = " + value);
}
// iterator 遍历 entries
Iterator<Map.Entry<String,String>> iterator = map.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry<String,String> entry = iterator.next();
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
// iterator 遍历 keys
Iterator<String> iteratorKey = map.keySet().iterator();
while(iteratorKey.hasNext()) {
String key= iteratorKey.next();
System.out.println("key = " + key);
}
// iterator 遍历 values
Iterator<String> iteratorValue = map.values().iterator();
while(iteratorValue.hasNext()) {
String value= iteratorValue.next();
System.out.println("value = " + value);
}
HashMap 提供了多种迭代方式，这里只分析一种迭代方式。
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
直接创建一个 EntrySet 对象，看看是啥东西:
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// Android-changed: Detect changes to modCount early.
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
关键就两个方法，一个是 foreach 迭代，从示例上看是非常简洁的，但性能貌似比 iterator 慢一些。HashMap 是不同步的，迭代的过程中是不允许多线程操作，这个时候 modCount 变量就排上用场了，如果发现 modCount 在迭代完后和迭代前不相等就会抛出 ConcurrentModificationException 异常。
iterator 返回一个 EntryIterator 对象：
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
}
调用 next 方法实际上是调用了这里的 nextNode 方法，如果下一个条目不为 null, 那么直接返回对应的节点即可，如果下个节点为空，则需要循环遍历直到找到不为 null 的节点附给 next, 保证下次返回节点的正确性。
三、总结
用问答的形式来总结下本文的内容以及 HashMap 常见的问题。
- 装载因子的作用是什么？ loadFactor 用于计算 HashMap 的阈值，当散列表内的节点个数超过阈值时，散列表就会进行扩容。
- 碰撞过多怎么办/扩容的原理？当节点数超过阈值，内部会新建一个比原来散列表大小大两倍的新散列表，然后将老散列表内的节点重新散列到新散列表中。
- 当散列表一个 bucket 桶上的单链表过长导致查询效率过低怎么办？jdk1.8 加入了红黑树解决此问题，当单链表长度超过 8 的时候会转换成红黑树，红黑树的查询效率是O(logn)，但由于红黑树结构更消耗内存，因此单链表超过 8 个节点才会转成红黑树。
- HashMap 和 HashTable 的区别？HashMap 相对 HashTable 的区别就在于不同步以及可以用null键。但为什么一般不用HashTable呢，因为HashTable用的是 synchronized 关键字，特别耗时，所以一般同步也就会用 concurrentHashMap。而且 HashMap 真的想同步的话，也可以用 Collections.synchronizedMap(new HashMap) 。
- 存储键值对的流程是怎样的？调用 put 方法，如果散列表为空则创建，首先根据 key 计算得出 hash 值，又根据 hash 得出对应的桶的位置，若这个桶上还没有节点，那么直接添加到桶中，如果有节点则遍历单链表或红黑树，发现有相同 hash 值和相同 key 的节点，直接替换它的 value，如果没有找到相同节点就加入到单链表的尾部。最后如果节点数量超过阈值，那么扩容。
- hash 函数为什么高低位异或？数组的长度一般来说都不大，如果直接拿 key 的 hashCode 来取模，那么都是拿二进制的低位进行与运算，会有很大几率产生碰撞，高16位和低16位异或就会让高位也参与计算，此时碰撞概率会大大减少。
- 初始容量是否有必要设置？有必要，在大概知道数据量的前提下，尽量设置对应的容量，减少扩容次数，扩容耗费性能。
- HashMap 的工作原理？HashMap 是一个键值对存储的数据结构，其内部结构是一个散列表。当执行 put 操作时，会根据 key 计算得出 hash 值，又根据 hash 得出对应的桶的位置，若这个桶上还没有节点，那么直接添加到桶中，如果有节点则遍历单链表或红黑树，发现有相同 hash 值和相同 key 的节点，直接替换它的 value，如果没有找到相同节点就加入到单链表的尾部（红黑树）。最后如果节点数量超过阈值即 loadFactor * capacity，那么扩容两倍。当执行 get 获取时，会计算出 key 的 hash 值，找到对应 bucket 桶的 index，如果该索引下没有节点则直接返回null，如果有节点则在单链表内遍历查找或在红黑树内查找。
暂时就想到这些问题了。
网友评论