image-20240307200352512

HashMap底层源码分析

HashMap主要是用来存放键值对的，它基于哈希表的Map接口实现，是常用的Java集合之一，是非线程安全的。

HashMap可以存放null的Key和value，但是null作为键只能有一个，作为value可以有多个

方法名称 说明
V put(K key, V value) 添加元素
V remove(Object key) 根据键删除键值对元素
void clear() 移除所有的键值对元素
boolean containsKey(Object key) 判断集合是否包含指定的键
boolean containsValue(Object value) 判断集合是否包含指定的值
boolean isEmpty() 判断集合是否为空
int size() 集合的长度，也就是集合中键值对的个数

HashMap结构

HashMap内部方法

图标为m表示method

image-20240318161136018

HashMap内部类

图标为c表示class

image-20240318161323108

HashMap内部属性

图标为f表示field

image-20240318161341292

1
static class Node<K,V> implements Map.Entry<K,V> {}

HashMap中每个元素都是一个Entry对象

jdk1.7及之前的底层实现为：数组+链表

jdk1.8之后的底层实现为：数组+链表+红黑树

1
2
3
4
5
6
7
8
9
// 表示数组默认的大小 为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 表示默认的负载因子（加载因子）为0.75
// 当数组元素个数超过0.75*16=12的时候就进行扩容，扩容为原来的2倍空间大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 表示HashMap最大的空间为 1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;

构造方法

空参构造方法只是进行loadFactor进行了初始化

1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap中的Hash值只与键有关系与值无关

1
2
3
4
5
6
7
8
9
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 返回键所对应的哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

>>> 表示无符号右移

扩容机制

调用空参构造的时候，只把属性loadFactor初始化为0.75

剩余的核心源码主要涉及到PUT操作：【put操作首先通过hash值定位到数组下标】

  • 如果当前位置没有值，则直接在数组中添加该键值对，即Node对象
    • 如果数组长度超过其初始长度16*0.75=12的时候，则会进行扩容，扩容成原来的2倍
  • 如果当前位置有值，在判断两者的key是否相等：
    • key一样：
      • 则进行覆盖更新
    • key不一样：
      • 则在其后以链表的形式进行追加。
      • 当链表的长度达到8【TREEIFY_THRESHOLD】的时候，则会调用treeifyBin()方法，此方法会根据HashMap数组长度来判断是否需要转成红黑树。只有当数组长度大于或者等于64【MIN_TREEIFY_CAPACITY】的情况下，才会执行转换红黑树的操作，以减少搜索时间。否则就只执行resize()方法对数组进行扩容。

get操作：

判断是否存在以key为key的键值对映射，如果不存在返回null；如果存在则返回e.value