Java集合 HashMap源码分析
简介HashMap主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。内部结构JDK1.8之前JDK1.8之前HashMap底层是数组和链表结合在一起使用也就是链表散列。HashMap通过key的hashCode来计算hash值，当hashCode相同时，通过“拉链法”解决冲突。所谓“拉链法”就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。https://img-blog.csdnimg.cn/20190324101246758.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dlb3JnZUd1b28=,size_16,color_FFFFFF,t_70JDK1.8之后相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。https://img-blog.csdnimg.cn/20190310105731876.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dlb3JnZUd1b28=,size_16,color_FFFFFF,t_70HashMap的属性public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 数组的默认大小是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量（2的30次方）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子（当数组使用达到 数组大小 * 0.75 之后就开始扩容）
// 例如当前数组为16，那么它达到 16 * 0.75 = 12 的时候，就开始扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的节点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小（当数组 >= 64的时候才使用红黑树？）
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，容量是2的n次幂
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
loadFactor填充因子控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。 thresholdthreshold = capacity * loadFactor，当 Size >= threshold 的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。内部Node类源码static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 通过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;
}
// getter setter
public final K getKey() { return key; }
public final V getValue() { return value; }
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;
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;
}
}内部红黑树类源码static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 红黑树父节点
TreeNode<K,V> left; // 左边节点
TreeNode<K,V> right; // 右边节点
TreeNode<K,V> prev; // 删除时需要取消下一个链接
boolean red; // 是否红色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回根节点
*/
final TreeNode<K,V> root() {
// 遍历节点，没有条件，知道父节点为空时才停止（父节点为空时说明是根节点）
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
// .......................
}HashMap put()方法的运行过程
[*]首先计算出key的hash值，然后再计算下标
[*]如果当前下标为空（没有碰撞），直接储存
[*]如果碰撞了，以链表的形式链接到后面
[*]如果链表长度超过阈值（TREEIFY_THRESHOLD == 8），就把链表转成红黑树
[*]如果节点已经存在就替换旧值
[*]如果桶满了（容量 * 加载因子），就需要resize
例如下面这个例子：public class HashMapTest {
public static void main(String[] args) {
Map map = new HashMap<String,Object>();
map.put("name", "任缥缈");
}
}当我们想HashMap添加一个元素的时候，它首先得找到一个位置去存放这个元素，那么这个时候，他就得初始化一个数组（默认大小16）去存放这个元素，在put方法里面我们可以看到，它在内部调用了一个putVal方法put方法源码 public V put(K key, V value) {
// hash(key) 通过这个方法来计算元素在数组的位置，得到一个（0~15）之间的整数
return putVal(hash(key), key, value, false, true);
}hash() 方法 通过这个方法来计算元素在数组的位置，得到一个（0~15）之间的整数，他是通过Object的hashCode()方法的值，将高16位和低16位通过异或运算得到数组的下标的。任何一个对象都可以调用hashCode()方法来获取一个32位的整形数据。https://img-blog.csdnimg.cn/20190310120939776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dlb3JnZUd1b28=,size_16,color_FFFFFF,t_70putVal方法源码上面我们已经获取了元素的下标位置，那么在putVal方法里面进行数组的初始化/**
* @Param hash 键的哈希
* @param key 键的值
* @param value 键对应的值的值
* @param onlyIfAbsent 如果为true，则不更改现有值
* @param evict 如果为false，则表处于创建模式
* @Return 返回前一个值，如果没有，则为空
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab：数组，p：节点，n：数组大小，i：数组下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 在这里判断Node节点的数组是否为空，或者长度是否为0 （将table赋值给tab，然后判断tab是否为空，然后将tab.length赋给n，判断n是否为0）
// 如果是，就通过resize()进行初始化（将数组赋给tab，然后将长度返回给 n）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 数组已经创建了，计算Node节点的位置，创建一个节点将 key、value等这些信息保存
// 然后将Node保存到数组
// 当节点的数量超过8个的时候，就会转位红黑树结构，
// 当节点的数量少于6个的时候，就会由红黑树转为链表结构
// 判断这个下标是够为空（获取该下标的节点，保存到p，判断p是否为空），如果是空的就在这个位置存放节点
// (n - 1) & hash===>(16 - 1) & hash 这里计算出Node节点的位置（使用 &（与运算）更快）
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
// 如果该下标的节点不为空，那么有3种情况
// 1. key相同，替换值
// 2. key不相同，如果是红黑树的结构，则使用红黑树的结构储存
// 3. key不相同，往后面插入，形成链表的方式
else {
// e：保存当前下标节点信息，k：保存key的信息
Node<K,V> e; K k;
// 1. key相同，替换值
// 判断hash是否相同，并且判断该下标的节点的key是否和传进的key是否相同，两个条件满足则替换掉
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 将第一个元素赋值给e，用e来记录
// 2. key不相同，如果是红黑树的结构，则使用红黑树的结构储存
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3. key不相同，往后面插入，形成链表的方式
else {
// 循环，没有条件，直到插入为止
for (int binCount = 0; ; ++binCount) {
// 判断当前下标的节点的next是否为空，如果是空的，说明到达了链表的尾部
if ((e = p.next) == null) {
// 在尾部插入新节点
p.next = newNode(hash, key, value, null);
// 节点数量达到阈值，转化为红黑树
// 比如说原来是7个，现在我要插入了一个马上成了8个了（但是这个时候binCount=7）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);// 转为红黑树结构
break;
}
// 如果链表中节点的key值与插入的元素的key值一样，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) { // existing mapping for key
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// size默认值是0，每次添加完之后，进行一次++
// 同时判断是否超过了数组大小的阈值，是则扩容
++modCount;
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}(n - 1) & hash为什用异或运算呢，因为通过异或运算可以让散列更均匀https://img-blog.csdnimg.cn/20190310163001568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dlb3JnZUd1b28=,size_16,color_FFFFFF,t_70resize()函数进行双倍扩容（保证数组的大小是2的n次幂），会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。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) {
// 超过最大值（2的30次方）就不再扩充了，就只好随你碰撞去吧
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
}
// 如果初始的threshold临界值大于0，将初始容量被设置为阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果旧表的长度为0（是空的），那么说明我们要初始化表，初始化的表使用默认值16
else {
newCap = DEFAULT_INITIAL_CAPACITY;
// (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) ==> 16 * 0.75
// 这里计算扩展因子，当数组到达这个数值的时候，就需要扩展了
// 因为数组的空间始终要用完的，用完了再去扩容不可持续发展，我们得走持续发展之路
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
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;
table = newTab;
if (oldTab != null) {
// 数组扩容之后，将旧数组的数据迁移到新数组上
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e; // 保存老数组储存的节点
// 获取老数组当前下标的元素，并保存到e，判断如果当前下标不为空，才进行迁移
if ((e = oldTab) != null) {
// 清空老数组对应的下标
oldTab = null;
// 如果是红黑树结构的，通过split方法打散，打散之后重新赋值
if (e.next == null)
newTab = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 如果是链表，
else {
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) {
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);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab = hiHead;
}
}
}
}
}
return newTab;
}get方法public V get(Object key) {
Node<K,V> e;
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;
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) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
这个解释的更详细： https://segmentfault.com/a/1190000024536712 HashMap源码是真的苦涩难懂
可以看看
页:
[1]