JDK源码分析-HashMap
2019-12-27 16:01:31来源：博客园 阅读 ()
JDK源码分析-HashMap
一.HashMap的内部属性
1.1 成员变量
1.1.1 size：
HashMap包含的KV键值对的数量，也就是我们通常调用Map.size()方法的返回值
public int size() {
return size;
}
1.1.2 modCount
HashMap的结构被修改的次数（包括KV映射数量和内部结构rehash次数），用于判断迭代器梳理中不一致的快速失败。
abstract class HashIterator {
...
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;
}
...
}
1.1.3 threshold
下一次扩容时的阈值，达到阈值便会触发扩容机制resize（阈值 threshold = 容器容量 capacity * 负载因子 load factor）。也就是说，在容器定义好容量之后，负载因子越大，所能容纳的键值对元素个数就越多。计算方法如下：
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;
}
1.1.4 loadFactor
负载因子，默认是0.75
1.1.5 Node<K,V>[] table
底层数组，充当哈希表的作用，用于存储对应hash位置的元素，数组长度总是2的N次幂
1.2 内部类
1.2.1 Node<K,V>
/**
* 定义HashMap存储元素结点的底层实现
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//元素的哈希值 由final修饰可知，当hash的值确定后，就不能再修改
final K key;// 键，由final修饰可知，当key的值确定后，就不能再修改
V value; // 值
Node<K,V> next; // 记录下一个元素结点(单链表结构，用于解决hash冲突)
/**
* 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; }
public final String toString() { return key + "=" + value; }
/**
* 为Node重写hashCode方法，值为：key的hashCode 异或 value的hashCode
* 运算作用就是将2个hashCode的二进制中，同一位置相同的值为0，不同的为1。
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 修改某一元素的值
*/
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* 为Node重写equals方法
*/
public final boolean equals(Object o) {
if (o == this)
return true;
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;
}
}
1.2.2 TreeNode<K,V>
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//与left、right联合使用实现树结构
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
// needed to unlink next upon deletion
TreeNode<K,V> prev;
//记录树节点颜色
boolean red;
/**
* 操作方法
* 包括：树化、链栈化、增删查节点、根节点变更、树旋转、插入/删除节点后平衡红黑树
*/
...
}
1.3 Key的hash算法
Key的hash算法源码如下：
static final int hash(Object key) {
int h;
///key.hashCode()为哈希算法，返回初始哈希值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
因为HashMap中是允许key 为null的键值对，所以先判断了key == null。当key 不为null的时候，hash算法是先通过key.hashCode()计算出一个hash值再与改hash值的高16位做异或运算（有关异或运算请移步：java运算符 与（&）、非（~）、或（|）、异或（^）） 上面的key.hashCode()已经计算出来了一个hash散列值，可以直接拿来用了，为何还要做一个异或运算？ 是为了对key的hashCode进行扰动计算（），防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响
二. HashMap的初始化
HashMap的初始化有以下四种方法：
- HashMap()
- HashMap(int initialCapacity)
- HashMap(int initialCapacity, float loadFactor)
- HashMap(Map<? extends K, ? extends V> m)
方法1的源码如下：
public HashMap() {
//使用默认的DEFAULT_LOAD_FACTOR = 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
其中的方法2本质上都是调用了方法3。initialCapacity是初始化HashMap的容量，loadFactor是在1.1.4中提到的负载因子。 方法3的源码注释如下：
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源码注释如下：
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor
*
* @param m 要初始化的map
* @param evict 初始化构造map时为false，其他情况为true
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
//判断当前m容量
if (s > 0) {
// 初始化
if (table == null) {
//ft按照默认加载因子计算ft=s/0.75 +1计算出来
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)
//s大于threshlod，需要扩容
resize();
//遍历m，并通过putVal初始化数据
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
三. put过程
3.1 put的正常调用过程
put方法是HashMap的增加KV对的入口，putVal方法是具体实现，整个过程的大致流程如下：
- 对key的hashCode()做hash，然后再计算index;
- 如果没碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity)，就要resize
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
3.2 put过程剖析
putVal方法的源码解析如下：
/**
* Implements Map.put and related methods
*
* @param hash key的hash值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent 为true不修改已经存在的值
* @param evict 为false表示创建
* @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;
//table为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据hash值计算出index,并校验当前tab中index的值是否存在
if ((p = tab[i = (n - 1) & hash]) == null)
//当前tab中index的值为空，则直接插入到tab中
tab[i] = newNode(hash, key, value, null);
else {
//当前tab节点已经存在hash相同的值
Node<K,V> e; K k;
//分别比较hash值和key值相等，就直接替换现有的节点
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;
//判断是否需要resize扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
四. 扩容
4.1 什么条件下会扩容
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于threshold阈值（即当前数组的长度乘以加载因子的值的时候），就要自动扩容了。
4.2 如何扩容
HashMap的扩容是调用了resize方法（初始化的时候也会调用），扩容是按照两倍的大小进行的，源码如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//取出tabble的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//当map不为空的时候
if (oldCap > 0) {
//map已经大于最大MAXIMUM_CAPACITY = 1 << 30
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//向左位移1，扩大两倍
newThr = oldThr << 1; // double threshold
}
//也就是HashMap初始化是调用了HashMap(initialCapacity)或者HashMap(initialCapacity,loadFactor)构造方法
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//使用的是HashMap()构造方法
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) {
//当map不为空，需要赋值原有map中的数据到新table中
...
}
return newTab;
}
从源码中可以看出，resize扩容是一个非常消耗性能的操作，所以在我们可以预知HashMap大小的情况下，预设的大小能够避免resize，也就能有效的提高HashMap的性能。
五. 树化与链表化
5.1 什么条件下会树化
当binCount达到阈值TREEIFY_THRESHOLD - 1的时候就会发生树化（TREEIFY_THRESHOLD = 8），也就是binCount>=7的时候就会进入到treeifyBin方法，但只有当大于MIN_TREEIFY_CAPACITY（= 64）才会触发treeify树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
5.2 树化算法
算法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 通过hash求出bucket的位置
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 将Node节点包装成TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 对TreeNode链表进行树化
hd.treeify(tab);
}
}
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//遍历TreeNode
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//next向前
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//当根节点为空，就赋值
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
//root存在，就自顶向下遍历
...
}
moveRootToFront(tab, root);
}
六. get过程
get方法相对于put要简单一些，源码如下：
public V get(Object key) {
Node<K,V> e;
//根据key取hash，算法与put中一样
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//1. 判断table不为空
//2. table长度大于0
//3. 与put方法一样计算tab的索引，并判断是否为空
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//比较第一个节点的hash和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 {
//链表：通过.next() 循环获取
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
六. 常见问题
5.1 并发常见下CPU100%问题
Hash并非是线程安全的，在并发场景下，错误的使用HashMap可能会出现CPU100%的问题 曾今有人在JDK1.4版本中的HashMap中提出过这样一个bug，官方也给出了答复“并非java或jvm的bug，而是使用不当”，当时所提出的地址是：JDK-6423457 : (coll) High cpu usage in HashMap.get() 左耳朵耗子前辈也做过分享：疫苗：JAVA HASHMAP的死循环
5.2 ConcurrentModificationException
https://blog.csdn.net/u010527630/article/details/69917063
原文链接:https://www.cnblogs.com/qizhelongdeyang/p/12107020.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- jdk各个版本下载 2020-06-11
- 你说研究过Spring里面的源码，循环依赖你会么？ 2020-06-09
- 通俗理解spring源码（六）—— 默认标签（import、alias、be 2020-06-07
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- JDK8的JVM内存模型小结 2020-06-03
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
