首先说明,文章中出现的源码都是基于JDK1.8.
HashMap
简介
HashMap是JDK1.2中引入的.HashMap不是线程安全的,如果需要线程安全或者不允许key和value为null,可以使用HashTable代替Hashmap,Oracle官网是这样描述它们的区别:The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls
mapping
一对key和value的组合在概念层面叫mapping.在代码层面对应Map.Entry类,参考java Map及Map.Entry详解及用途
碰撞(collision)
当2个key通过equals()方法比较不相等,但是通过hashCode()方法计算得到的hashcode相同时就发生了碰撞(collision).碰撞的key-value组合都对应一个bucket,可以说碰撞是同一个bucket内部的事情.关于碰撞参考How does a Java HashMap handle different objects with the same hash code?和What happens if two different objects have the same hashcode.关于碰撞的过程有一张演示图:
hashmap-collision-in-java-768x342.png
hashmap和数组
hashmap中有一个数组,数组的一个位置(index)对应一个bucket,因此网上很多文章也会把这个数组叫作bucket数组.该数组的定义为transient Node<K,V>[] table;,可见是一个Node数组.Node是HashMap中的一个内部类,实现了Map.Entry接口:static class Node<K,V> implements Map.Entry<K,V>.因此,网络上很多文章把这个数组叫作Entry数组也是可以理解的.
bucket
bucket是一个抽象概念,实际对应数组中的一个位置,具体的实现一般是linkedlist.在JDK8中当一个bucket中发生碰撞的mapping超过8个时,bucket的实现会从linkedlist转换为红黑树.注意,linkedlist或者红黑树中存储的节点都是Node.
容量(capacity)
容量是HashMap中bucket的数量,也就是Node[]数组的长度.使用默认的构造方法时容量是16,也可以使用其它的构造器指定容量HashMap(int initialCapacity).注意,不管指定的初始容量是不是2的倍数(power of 2),最后的实际容量一定是2的倍数.假设指定的值是32,那么就是32,如果指定的是30,最后实际容量会是32.关于为什么必须是2的倍数参考Java HashMap工作原理及实现
容量极限
HashMap虽然可以扩容,但是也有容量极限.查阅HashMap源码,这个极限定义是:
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
也就是2的30次方,对应值为10 7374 1824.为什么是2的30次方?因为数组下标的计算方法为(n-1) & hash,hash值就是hashCode()方法计算得到的值,这个值是int类型,也就是32位.如果n对应的二进制小于等于32位,(n-1) & hash计算得到的位数和n一致;如果n大于hash,也就是超出了32位,那么(n-1) & hash计算得到的值和hash位数保持一致,不可能超过32位.但是为什么是30位而不是32位呢?可能是因为安全原因,去掉了2位作为最大容量.
看下resize()中部分代码:
final Node<K,V>[] resize() {
//table是原来的数组
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;
}
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;
可以看到大于等于最大容量以后会直接返回之前的数组,不再扩容.
load factor
使用默认构造器时load factor是0.75.当HashMap中已存在的mapping和capacity的比值大于加载因子(load factor)时会触发自动扩容操作.扩容的原则是2倍扩容.扩容过程中会发生rehash.关于为什么是2倍扩容参考Java HashMap工作原理及实现
线程安全问题
HashMap不是线程安全的,多线程操作HashMap有可能导致某个bucket形成首尾相连的环形链表,当调用map.get("a")这样的方法时会陷入无限循环,参考美团点评技术团队的文章Java 8系列之重新认识HashMap
和TreeMap、LinkedHashMap的区别
区别如下:
- HashMap: key/value对完全是无序的
- TreeMap: 按照key的自然顺序(Natural Ordering)排序,遍历的时候也是按照这个顺序排序的.key需要实现Comparable接口,自然顺序指的是Comparable接口的compareTo方法所定义的顺序.有些需要对key排序遍历的场景适合使用TreeMap.
- LinkedHashMap: key/value的顺序是插入的先后顺序.
更多区别参考Difference between HashMap, LinkedHashMap and TreeMap Ask
mapping存储
hashcode值,hash值和index值
使用key的hashcode()方法计算得到的是key的hashcode值.再对hashcode值进行低位运算得到的值是hash值:即高16位不变,低16位和高16位做异或运算,相关代码为:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
最后对hash值做位运算得到的值是index值,相关代码为:
(n-1) & hash
这行代码来源于HashMap源码的putVal方法第2个if判断的条件,这里的n指的是Node[]数组的长度.关于为什么要采用这个算法可以参考Java HashMap工作原理及实现
put
核心流程如下:
-
对key计算hashcode,根据hashcode计算hash
-
根据上一步得到的hash值和Node[]数组长度计算得到该key-value对在数组中的index
-
如果超出原有Node[]数组容量,需要先扩容(resize)为之前的2倍.
-
如果该index不存在Node,直接插入
-
如果该index存在Node,如果使用key的equals方法比较也相同,则直接覆盖旧的值.如果使用key的equals方法比较不同,则把该Node添加到原有Node组成的链表的最前面,然后把该Node插入到数组.注意:如果碰撞的Node个数超过默认值8,需要先把链表转换为红黑树.
理解了核心流程,再来看看具体的实现.这里只看put和putVal方法的源代码,先看put:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里先调用了上一小节中介绍的hash方法计算key的hash,然后调用putVal保存.再看putVal:
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
注意putVal中第二个if判断的条件:(p = tab[i = (n - 1) & hash]) == null,这里通过tab[i = (n - 1) & hash]完成了key在hashmap数组对应index计算.这里的tab被赋值为hashmap中bucket数组属性:transient Node<K,V>[] table;
get
核心流程如下:
-
对key计算hashcode,根据hashcode计算hash
-
根据上一步得到的hash值和Node[]数组长度计算得到该key-value对在数组中的index
-
取出该index对应的第一个节点(first),使用key的equals方法比较,如果相等,说明是要找的节点,直接返回
-
如果上一步没找到,判断节点类型是不是红黑树专用的TreeNode,如果是,使用红黑树专用的查找方法并返回.
-
如果上一步没有,说明是链表,使用do{}while()循环遍历链表查找并返回.
理解了核心流程,再来看看具体的实现.主要看get和getNode方法.先看get:
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
再看getNode:
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
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) {
//如果是红黑树,使用getTreeNode获取节点并返回
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;
}
我在源码部分加了部分注释,方便查看.可以看到在第一个if判断里也使用了tab[(n - 1) & hash]这种方法计算key-value在Node[]数组对应的index值,这个和put方法中的用法是一样的.
网友评论