HashMap源码分析
2020-04-16 16:13:40来源：博客园 阅读 ()
HashMap源码分析
HashMap源码分析
简介
HashMap是一个底层用数组+链表实现的存储KV键值对数据结构，它允许null键和null值。
原理
HashMap的存储规则是，根据K的hashCode运算得到hash值，然后根据hash值运算得到下标，如果数组中该下标没有值就放入，有值就一个一个比较是否hash值相同并且equals也为true，如果是就用value更新原来的value，如果到达最后都没找到相同的，就新增节点，在jdk1.8中进行了优化，当链表长度达到8时，就把链表变为红黑树
类结构
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap继承了AbstractMap并重写了里面的方法。
HashMap实现了Cloneable接口，可以被克隆。
HashMap实现了Serializable接口，可以被序列化。
属性
//默认初始化容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量为2的30此方法
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转成树的阈值
static final int TREEIFY_THRESHOLD = 8;
//树转换成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//转换成树的最小容量阈值
static final int MIN_TREEIFY_CAPACITY = 64;
//保存节点的数组
transient Node<K,V>[] table;
//保存的所有节点
transient Set<Map.Entry<K,V>> entrySet;
//保存节点个数
transient int size;
//修改次数，用于迭代器的快速失败
transient int modCount;
//扩容的阈值
int threshold;
//加载因子
final float loadFactor;
节点
static class Node<K,V> implements Map.Entry<K,V> {
//key的hash值
final int hash;
final K key;
V value;
//后继节点
Node<K,V> next;
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; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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()))//判断相等的条件是key和value都要相等
return true;
}
return false;
}
}
构造器
//指定初始化容量和增长因子的构造器
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;
//把指定的初始化大小改成近似这个数的2的n次方形式
this.threshold = tableSizeFor(initialCapacity);
}
//通过一定的算法得到2的n次方近似于这个数
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;
}
//指定初始化大小的构造器
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无参构造器
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//使用Map初始化构造器
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
方法
添加节点方法
put(K,V)添加kv键值对
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
//如果key为null，hash为0，否则计算hash的规则是hashCode与（hashCode无符号左移16位）
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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)//如果table还没初始化，或大小为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))))//如果添加节点的hash和计算下标位置节点的hash相等 并且 添加节点的key与计算下标位置节点的key地址相等或逻辑相等
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) // 如果链表长度大于等于TREEIFY_THRESHOLD-1，即添加后链表长度大于等于8，那么那链表转换为树
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);
//如果是替换旧值，并没有修改modCount
return oldValue;
}
}
++modCount;
if (++size > threshold)
//添加了元素大于阈值，进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
//初始化或对数组进行二倍扩容
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) {//如果原容量大于最大值
//阈值设置为Integer的最大值
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) //用原来的阈值初始化数组大小（构造的时候如果指定了初始化大小是使用threshold来保存的）
newCap = oldThr;
else { // 原容量为0并且没有指定初始化容量大小，就使用默认值
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) {//如果数组下标位置存放了元素
//help GC?
oldTab[j] = null;
if (e.next == null)//如果元素没有后继
//e.hash & (newCap - 1) 计算下标位置
//不进行扩容直接添加的计算规则是 hash & (n-1) n就是数组大小
//不管是你自己指定的初始化大小还是默认是初始化大小，都是2的次方（自己指定的如果不是2的次方会被转化为2的次方）而且扩容也是2倍扩容，所以不管新容量还是老容量都是2的次方
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果是红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //是链表
//什么4个节点，对应两条链表
//一条链表上的节点通过hash计算的下标是一样的，而按照hash & （newCapacity-1）规则计算下标，只会得到两个下标，一个是原下标，一个是原下标+oldCapacity
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//精髓 e.hash & oldCap
//假如原容量为16那么新容量就为32，此时2号位置的链表通过原来计算公式为hash&（oldCapacity-1）即：1011011001010001000010
// &
// 0000000000000000001111 15
// 0000000000000000000010
// 即： 2号位置
//扩容之后本来应该的下标为 1011011001010001000010
// & ↑
// 0000000000000000011111 31
// 即 2号位置
//可以看到扩容2倍，由于是&上（capacity-1）所以二进制全为1且比原来多一个1，那么差距就是↑所指那一位是0或1，如果是0那么新下标就是原下标，如果是1那么新下标就是原下标+oldCapacity
//如果使用 e.hash & oldCap 可以更快的计算
// 1011011001010001000010
// &
// 0000000000000000010000
// 0000000000000000000000 为0说明是原下标
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
移除节点方法
public V remove(Object key) {
Node<K,V> e;
//如果移除了返回节点的值，否则没找到返回null
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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) {//数组已经初始化并且大小大于0而且通过hash计算下标位置不空
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//如果hash相等 并且 key地址相等或equals
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);
}
}
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;
else
//是链表元素，修改链
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
但是HashMap为什么要有modCount这个属性呢？既然不是线程安全的，那么快速失败的意义在哪儿呢？而且如果put方法是key已存在，只是将新值替换旧值，modCount并没有改变，难道你在使用迭代器遍历时，其他线程修改了值，不用快速失败吗？
原文链接:https://www.cnblogs.com/moyuduo/p/12716782.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
相关文章
- 你说研究过Spring里面的源码，循环依赖你会么？ 2020-06-09
- 通俗理解spring源码（六）—— 默认标签（import、alias、be 2020-06-07
- HashMap：源代码（构造方法、put、resize、get、remove、rep 2020-06-04
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- HashMap1.7和1.8，红黑树原理！ 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
热门词条
最新资讯
热门关注
热门标签