本章属于持续学习、长期更修。
HashMap
特征
- HashMap 允许
null键和null值，null键哈西值为0. - HashMap 并不是有序的存放。在使用
iterate迭代的时候，并不能得到存放顺序。 - HashMap使用它的内部类Node <K，V>来存储映射。
- HashMap将
entries存储到多个单链表中，称为存储桶或存储桶。默认的箱数为16，默认负载因子0.75，它的扩展系数为2，当键值对数量大于阈值，则容量扩容到原来的2倍。 - HashMap不是线程安全的，对于多线程环境，您应该使用ConcurrentHashMap类或使用
Collections.synchronizedMap()方法获取同步映射。 - 底层实现是链表，但是jdk1.8后添加了红黑谁的转换。
- HashMap的Key用存放，所以key默认不允许重复的，如果想重复就重写key的hashcode和equals方法。
- 查找方法，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
源码分析
HashMap中的常量以及变量
// 未指定容量大小的情况下，默认初始化16。容量都是2的幂。第一次扩容大概率情况下是64。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 容量最大长个数。
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子，
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// HashMap使用单链表来存储元素，这些元素称为bin或buckets。当我们调用put方法时，key的hashCode用于确定将用于存储映射的存储区。
// 链表转换红黑树的阀值。当某个bin\buckets的长度大于8的时候进行转换。
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换链表的阀值。当某个bin\buckets的长度小于8的时候进行转换。
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中bin最小hash容量，如果大于这个值会进行resize扩容操作，此值至少是TREEIFY_THRESHOLD的4倍
static final int MIN_TREEIFY_CAPACITY = 64;
// 被transient修饰的变量不回被序列化。
// HashMap内部类实现了Map的内部类Entry,用于存储K,V，第一次使用的时候被创建，根据需要可以进行resize。分配长度为2的冥次方
transient Node<K,V>[] table;
// 当被调用entrySet时被赋值。通过keySet()方法可以得到map key的集合，通过values方法可以得到map value的集合
transient Set<Map.Entry<K,V>> entrySet;
// size表示HashMap中存放KV的数量（为链表和树中的KV的总和）。
transient int size;
// 操作次数，通常用过fail-fast。每次扩容和更改map结构的计数器
transient int modCount;
// threshold=capacity*loadFactor threshold表示当HashMap的size大于threshold时会执行resize操作。
int threshold;
// Load Factor用于确定何时重新散列HashMap并增加存储桶大小。存储桶或容量的默认值为16，负载系数为0.75。通过乘以容量和负载因子来计算重新散列的阈值
final float loadFactor;
Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // node哈希值
final K key;
V value;
Node<K,V> next; // 下一个node的地址
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
// 这里重写方法，所以map.toString()不是内存地址。
public final String toString() { return key + "=" + value; }
// 这里重写了hashCode()方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 这里重写了equals()方法
public final boolean equals(Object o) {
if (o == this)
return true;
//Map.Entry 相等的条件：键相等、值相等、个数相等、顺序相等
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
@Test
public void testConstructor(){
log.info("Map test");
// 1
Map m = new HashMap();
// 2
Map m1 = new HashMap(10);
// 3
Map m2 = new HashMap(10,0.75f);
// 4
Map m3 = new HashMap(map1);
// put
HashMap map = new HashMap<String,Object>();
map.put("1","1");
map.put("2","2");
map.put("3","3");
map.put("4","4");
log.info("map {}",map);
map.put("1",3);
log.info("map {}",map);
map.put("1",null);
log.info("map {}",map);
map.put(null,null);
log.info("map {}",map);
Set<String> keySet = map.keySet();
log.info("keySet {}",keySet);
Collection<String> list = map.values();
log.info("list {}",list);
log.info("map.get {}",map.get("1"));
}
16:16:25.020 [main] INFO cn.z201.java.test.map.HashMapTest - map {1=1, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - map {1=3, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - map {1=null, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - map {null=null, 1=null, 2=2, 3=3, 4=4}
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - keySet [null, 1, 2, 3, 4]
16:16:25.023 [main] INFO cn.z201.java.test.map.HashMapTest - list [null, null, 2, 3, 4]
12:37:27.533 [main] INFO cn.z201.java.test.map.HashMapTest - map.get null
源码方法跟踪
- HashMap 源码中三个重要方法：查询、新增和数据扩容。
// 1 构造方法为空，loadFactor 将取默认系数。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 2 构造方法一个参数, 将指定Capacity的大小。其实调用的是另外的一个构造方法。但是指定了默认的负载因子。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 3 构造方法两个参数, 将指定Capacity的大小，和负载因子。
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);
}
// 4 创建一个与指定Map具有相同映射并且指定负载因子系数为0.75的Map
public HashMap(Map<? extends K, ? extends V> m) {
// 直接指定默认的负载因子。
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
// tableSizeFor(int) 来根据指定的容量设置阈值，这个方法经过若干次无符号右移、求异运算，得出最接近指定参数 cap 的 2 的 N 次方容量。假如你传入的是 5，返回的初始容量为 8 。
static final int tableSizeFor(int cap) {
// 其实我没看懂这段位移 😄
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 将目标map的桶插入当前map中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获得bin（桶）的长度。
int s = m.size();
// 如果桶长度大0则进行复制，否则什么都不做。
if (s > 0) {
// 如果当前位数的痛数组为空。也就是未初始化
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果 则指定的容量设置阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
//数组不为空，桶数量超过阈值就扩容
else if (s > threshold)
resize();
// 增强循环为当前的table赋值。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 和put调用的是一个方法。//先经过 hash() 计算位置，然后复制指定 map 的内容
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* 插入数据
* 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) {
// 声明临时变量 table 数组 p链表
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果当前的桶是null，长度为0。就扩容一次。
if ((tab = table) == null || (n = tab.length) == 0)
// 则n 指向最后一个桶的位置
n = (tab = resize()).length;
// 计算插入的位置有没有node， (n - 1) &hash得到的是key所在的桶的头结点，如果节点不在这个桶。
if ((p = tab[i = (n - 1) & hash]) == null)
// 此时的i = 0 , 新建个节点并放进去
tab[i] = newNode(hash, key, value, null);
else {
//如果插入的位置有元素,就是p != null 被找到了。开始替换value流程。
// 临时变量 e 被替换的元素
Node<K,V> e; K k;
//p 指向要插入的桶第一个 元素的位置，如果 p 的哈希值、键、值和要添加的一样。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// e 指向 p
e = p;
// //如果key hash不一样，判断是否红黑树
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);
//当这个桶内链表个数大于等于 8，就要红黑树树形化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果找到要替换的节点，就停止，此时 e 已经指向要被替换的节点
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;
}
/**
* 扩容
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 获取当前的table
Node<K,V>[] oldTab = table;
// 获取当前table的容量大小。
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取当前table的扩展阀值
int oldThr = threshold;
// 临时变量 新的容量、阀值。
int newCap, newThr = 0;
// 原容量大于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)
//如果旧容量小于等于 16，新的阈值就是旧阈值的两倍
newThr = oldThr << 1; // double threshold
}
// //如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化容量等于阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果此时新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 覆盖当前扩展阀值
threshold = newThr;
// 创建新链表数组，容量是原来的两倍。newCap上面已经被赋值了。
@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;
// 如果桶里面只有一个元素，next没有得情况下。
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
// 如果桶里面有元素。保留旧哈希表桶中链表的顺序
// 链表复制，JDK 1.8 扩容优化部分
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//do-while 循环赋值给新哈希表
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + 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;
}
// 将原索引 + oldCap 放到哈希桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
// 查询
public V get(Object key) {
Node<K,V> e;
// 对 key 进行哈希操作
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 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;
// tab = table) != null 数组桶不为null ，并赋值给临时桶数组 tab。
// (n = tab.length) > 0 桶的长度大于0 ，并赋值给临时桶长度 n。
// (first = tab[(n - 1) & hash]) != null 第一个桶里面有元素。
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果桶里面第一个元素key满足匹配条件。则直接返回
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 while // 非树结构，循环节点判断 循环便利桶所有的key hash 找到则返回。
do {
// hash 相等并且 key 相同，则返回此节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 没找到。
return null;
}