导图社区 HashMap源码解析
鉴于面试中必问到的hashmap底层实现,特根据源码简化分析而出的一份思维导图。
编辑于2020-12-22 15:01:44HashMap<K,V>
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
初始化容量(必须是二的n次幂)默认16
static final int MAXIMUM_CAPACITY = 1 << 30;
集合最大容量(必须是二的幂)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
负载因子,默认的0.75
static final int TREEIFY_THRESHOLD = 8;
当链表的值超过8则会转红黑树(1.8新增)
static final int UNTREEIFY_THRESHOLD = 6;
当链表的值小于6则会从红黑树转回链表
static final int MIN_TREEIFY_CAPACITY = 64;
当Map里面的数量超过这个值时,表中的桶才能进行树形化 ,否则桶内元素太多时会扩容,而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
transient Node<K,V>[] table;
HashMap中的数组
table初始化(必须是二的n次幂)
transient Set<Map.Entry<K,V>> entrySet;
保存缓存的entrySet
transient int size;
HashMap中存储的数量
transient int modCount;
用来记录HashMap的修改次数
int threshold;
用来调整大小计算下一个容量的值,计算方式为(容量*负载因子)capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容),扩容后的 HashMap 容量是之前容量的两倍
final float loadFactor;
加载因子,用来衡量 HashMap 满的程度,计算HashMap的实时加载因子的方法为:size/capacity,而不是占用桶的数量去除以capacity。capacity 是桶的数量,也就是 table 的长度length。
public HashMap(...) {...}
构造一个 HashMap ,默认初始容量(16)和默认负载因子(0.75)
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); }
HashMap是支持Key为空的,而HashTable是直接用过Key来获取HashCode所以key为空会抛异常
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) n = (tab = resize()).length;//--1-- if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);//--2-- else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//--3-- else if (p instanceof TreeNode)//--4-- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {//--5-- for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) {//--6-- p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);//--7-- break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e;//--8-- } } if (e != null) { // existing mapping for key //--8-- V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount;//--记录修改次数-- if (++size > threshold)//--判断当前元素数量是否大于threshold,是则扩容-- resize(); afterNodeInsertion(evict); return null; }
hash key的hash值 key 原始Key value 要存放的值 onlyIfAbsent 如果true代表不更改现有的值 evict 如果为false表示table为创建状态
判断数组是否为空或者长度等于0,是则初始化
对hash码进行取模运算获得值位置,如果为null则新增
不为空则判断key值是否存在,存在则替换value
key不存在则判断是否红黑树,是则新增插入红黑树
否则是链表,遍历链表
遍历到最后节点为null(说明没重复)插入
判断节点是否大于红黑树阈值,是则转为红黑树
遍历链表中重复则结束遍历
重复则直接替换
结束
Serializable
Cloneable
Map<K,V>
AbstractMap<K,V>