HashMap算是内容比较多的了,刚开始看3000行左右也是挺蒙蔽的,不过读起来也没那么麻烦。
一、概括
HashMap内部采用数组+链表(树)的方式进行数据的存储与维护,数组的每个位置存放的是一个链表或者树。每次存放数据时候,由Key的Hash值经过一些操作决定存放的数据下标,再经过遍历指定数组位置链表(树),判断V是否相同,相同的话替换,不同的话放在链表的尾部。删除也是类似的流程。(需要注意,在HashMap内部存在着两种数据结构用于存放数据,TreeNode与Node,TreeNode是Node的子类,分别对应于树存储与链表存储)
二、相关源码
(1) Key的Hash计算 (决定了存放的元素在数组中的坐标)
/**
* 计算一个key的hash值,因为在hashMap中,数据的存储是通过
* key决定存储于数组哪个位置中,将高16位与低16位进行亦或运算
* 这样做目的是为了让hash码的散列值分配的更平均
* @param key
* @return
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
(2)HashMap中的字段。
static final int DEFAULT_INITIAL_CAPACITY = 1 <<4;//默认的数组大小
static final int UNTREEIFY_THRESHOLD = 6;//红黑树转变为链表的阈值。
static final int MAXIMUM_CAPACITY = 1 <<30; //默认最大的数组长度
/**
* 当数组中链表过长的时候,达到TREEIFY_THRESHOLD,就会进行数组的重新调整。
* 如果当前数组的长度小于MIN_TREEIFY_CAPACITY的话,先进行扩容。
* 如果超过了MIN_TREEIFY_CAPACITY,那么指定的链表超过8的位置将会转变为
* 红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认装载 因子
/**
* 用于统计修改次数,在多线程情况下
* 用其实现修改数组后快速失败
*/
transient int modCount;
/**
* 记录下一次增长的时机
*/
int threshold;
/**
* 增长因子,loadFactor*当前数组大小就是下一次增长时机
* 也就是说当数据量大于threshold就进行增大,默认是0.75
*/
float loadFactor;
/**
* node数组,数组中每一项都是链表或树
*/
transient SimpleHashMap.Node[] table;
(3)HashMap初始化,需要注意,在初始化的时候不会立即生成数据。而是在添加第一个元素的时候才会生成数组,并且数组的大小都是2的倍数。默认的HashMap初始化时候table为16。但如果使用自定义大小的构造函数,它会找到传入值的最接近的二的倍数作为table大小,HashMap要求table的大小一定为2的倍数。
这里有一个问题了,为什么是2的倍数,这点其实是跟计算数组的下标有关。数组下标的计算方法是计算key的hash值,然后与数组长度n-1相与得到数组下标。那么,怎么才能让这些数更加均匀的分布在数组中呢。最好的方式当然是与它相与的数对应的二进制位1越多了~,如果与它相与的二进制位中1的数很少,就有更大的概率产生两个不同的数产生相同的与的结果,而如果数组的长度是2的倍数,那么减去一就会产生在当前长度范围下最多的一了。不信就写写画画试试。
/**
* 初始化容器,传入初始的容量以及增长因子
* 而这个容量不一定是传入的初始值大小,它需要经过
* tableSizeFor函数找到大于等于它的且是二的倍数作为
* table初始大小
* @param initialCapacity
* @param loadFactor
*/
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);//会找到最近的
}
/**
* 这个函数的目的是让其值变为最近的大于等于输入值的2的倍数
* @param cap
* @return
*/
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;
}
(3)HashMap数据插入。
输入插入的流程。
1、首先判断table是否为空,如果为空,那么先分配内存
2、插入的节点是通过(n - 1) & hash计算是否是指定数组位置的第一个,n为数组的长度,如果是直接插入
3、插入节点不是第一个,那就需要先判断一下当前节点是个是么样子的节点
如果是个treeNode,那么需要进行红黑树的插入
如果是个普通的node,那么会进行遍历查找(链表),并计数,如果发现超过了8,
,这时候就需要进行table数组的调整,这时候可能会变为红黑树。
4、在插入节点的过程中,因为会进行判断是否存在key完全相同的对象(key的hash值与key的内容),如果存在的话,
会返回旧的节点,同时,在onlyIfAbsent为false的时候,才会把key完全相同情况下的值修改为新值
5、插入节点后,s节点数自增,然后达到阈值的话进行尺寸扩大
那么,一个链表何时会变为红黑树?
首先,当插入到数组某个位置的链表长度超过8后,会进行调整。这时候,先判断数组的长度是否超过64,如果未超过,先进行扩容。如果超过,那么相应位置的链表就会转换为红黑树。
/**
* 进行空间调整,当tab大小小于64的时候,先进行数组的扩展,扩展超过64后,再把数组的
* 链表转换为树
*/
final void treeifyBin(HashMap.Node[] tab, int hash) {
int n, index; HashMap.Node e;
//如果tab.length小于64,表示当前的hashMap存放不太均衡,
//重新扩大空间
if (tab == null || (n = tab.length) hd = null, tl = null;
do {
HashMap.TreeNode 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)
hd.treeify(tab);
}
}
(4)HashMap中节点的删除
HashMap中节点删除就没什么难度了,通过hash(Key )&(length-1)求得存储在数组中的位置,然后查找value相同的节点删除。这里需要注意一下,如果是树节点的删除,如果到了蜕化为链表的阈值,将会蜕化为链表。
(5)HashMap中节点的访问
HashMap中通过key查找某个节点的时候,先进行第一个节点的判断,当第一个节点不满足条件的再进行遍历。这样也相当于一种优化,因为当hashMap的节点分布均匀的话,这样获取节点值的性能将接近于数组。
(6)HashMap中的Spliterator
JDK1.8中,增加了Spliterator的各种实现,作用是提升在并发访问下的效率。
ps: 渣渣一枚,如有不对,请大佬指出~