测试代码
- public static void main(String[] args) {
- HashMap map=new HashMap();
- map.put("student1","萧炎");
- map.put("student2","林动");
- map.put("student3","牧尘");
- map.put("student4","古尘沙");
- System.out.println(map);
- }
结果
执行流程分析
jdk1.8 中引入红黑树的进一步原因
从继承体系可以看出:
在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作桶。
在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。
当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率。
数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。
- /*
- * 序列化版本号
- */
- private static final long serialVersionUID = 362498820763181265L;
-
- /**
- * HashMap的初始化容量(必须是 2 的 n 次幂)默认的初始容量为16
- */
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
-
- /**
- * 最大的容量为2的30次方
- */
- static final int MAXIMUM_CAPACITY = 1 << 30;
-
- /**
- * 默认的装载因子
- */
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
-
- /**
- * 树化阈值,当一个桶中的元素个数大于等于8时进行树化
- */
- static final int TREEIFY_THRESHOLD = 8;
-
- /**
- * 树降级为链表的阈值,当一个桶中的元素个数小于等于6时把树转化为链表
- */
- static final int UNTREEIFY_THRESHOLD = 6;
-
- /**
- * 当桶的个数达到64的时候才进行树化
- */
- static final int MIN_TREEIFY_CAPACITY = 64;
-
- /**
- * Node数组,又叫作桶(bucket)
- */
- transient Node
[] table; -
- /**
- * 作为entrySet()的缓存
- */
- transient Set
> entrySet; -
- /**
- * 元素的数量
- */
- transient int size;
-
- /**
- * 修改次数,用于在迭代的时候执行快速失败策略
- */
- transient int modCount;
-
- /**
- * 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor
- */
- int threshold;
-
- /**
- * 装载因子
- */
- final float loadFactor;
-
DEFAULT_INITIAL_CAPACITY ---- 集合的初始化容量(必须是 2 的 n 次幂):
- // 默认的初始容量是16 1 << 4 相当于 1*2的4次方
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
举例解释下上面说的,例如,数组长度为 8 的时候,3 & (8 - 1) = 3,2 & (8 - 1) = 2,桶的位置是(数组索引)3和2,不同位置上,不碰撞。
再来看一个数组长度(桶位数)不是2的n次幂的情况:
数组长度为9 hash值为3
00000011 3
00001000 8
————————
00000000 0
数组长度为9 hash值为5
00000101 5
00001000 8
————————
00000000 0
数组长度为9 hash值为6
00000101 5
00001000 8
————————
00000000 0
通过上面举例,发现, 如果数组长度不是2的次幂,通过与运算就容易得到重复的hash值,这会大大增加哈希碰撞的概率,导致性能下降。
因此我们可以得出用2的次幂原因:
了解了为什么系统初始化hashmap时,必须为2的次幂。可是当用户创建hashmap对象,传入的数组长度不是2的次幂,怎么办呢?于是我查看了源代码,如下:
- 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;
- }
这里HashMap会采用一个tableSizeFor()方法,通过这个方法,它会把数组长度设置成最接近用户输入数组长度数量的2的次幂的值。
我们分析下源代码:
int n = cap - 1;为什么要减去1呢?
这是为了防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂,又没有这个减 1 操作,则执行完后面的几条无符号操作之后,返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)。
最后为什么有个 n + 1 的操作呢?
如果 n 这时为 0 了(经过了cap - 1后),则经过后面的几次无符号右移依然是 0,返回0是肯定不行的,所以最后返回n+1最终得到的 capacity 是1。
注意:容量最大也就是 32bit 的正数,因此最后 n |= n >>> 16;最多也就 32 个 1(但是这已经是负数了,在执行 tableSizeFor 之前,对 initialCapacity 做了判断,如果大于MAXIMUM_CAPACITY(2 ^ 30),则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY,会执行位移操作。所以这里面的位移操作之后,最大 30 个 1,不会大于等于 MAXIMUM_CAPACITY。30 个 1,加 1 后得 2 ^ 30)。
说着不好理解,画图说明:
上面说到了 数组长度,下面说红黑树,当桶(bucket)上的结点数大于这个值时会转为红黑树
- // 当桶(bucket)上的结点数大于这个值时会转为红黑树
- static final int TREEIFY_THRESHOLD = 8;
-
当链表长度低于6会从红黑树转化成链表
- // 当桶(bucket)上的结点数小于这个值,树转为链表
- static final int UNTREEIFY_THRESHOLD = 6;
-
MIN_TREEIFY_CAPACITY ---- 当 Map 里面的数量超过这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4*TREEIFY_THRESHOLD(8)
- // 桶中结构转化为红黑树对应的数组长度最小的值
- static final int MIN_TREEIFY_CAPACITY = 64;
-
table ----它是存储元素的数组
- // 存储元素的数组
- transient Node
[] table; -
在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry
entrySet --- 用来放缓存
- // 存放具体元素的集合
- transient Set
> entrySet; -
size ---- HashMap 中存放元素的个数
- // 存放元素的个数,注意这个不等于数组的长度
- transient int size;
size 为是记录HashMap 中 K-V 的实时数量,不是数组 table 的长度。
modCount --- 用来记录 HashMap 的修改次数
- // 每次扩容和更改 map 结构的计数器
- transient int modCount;
-
threshold --- 用来调整大小下一个容量的值计算方式为(容量*负载因子)
- // 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
- int threshold;
-
loadFactor --- 哈希表的负载因子
- // 负载因子
- final float loadFactor;// 0.75f
-
说明:
- /**
- * Initializes or doubles table size. If null, allocates in
- * accord with initial capacity target held in field threshold.
- * Otherwise, because we are using power-of-two expansion, the
- * elements from each bin must either stay at same index, or move
- * with a power of two offset in the new table.
- *
- * @return the table
- */
- final Node
[] resize() { - //把旧的table 赋值个一个变量
- Node
[] oldTab = table; - //获取旧的tabel的长度
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- // 旧的阈值
- int oldThr = threshold;
- int newCap, newThr = 0;
-
- if (oldCap > 0) {
- //判断数组的长度是否大约等于最大值
- if (oldCap >= MAXIMUM_CAPACITY) {
- //如果数组的长度达到了最大值,那么就不在进行扩容,直接返回,不管hash冲突
- threshold = Integer.MAX_VALUE;
- return oldTab;
- //把旧的数组长度左移一位(也就是乘以2),然后判断是否小于最大值,
- // 并且判断旧的数组长度是否大于等于默认的长度16
- }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- oldCap >= DEFAULT_INITIAL_CAPACITY)
- //如果条件成立就把旧的阈值左移一位复制给新的阈值
- newThr = oldThr << 1; // double threshold
- }//如果就的数组长度小于0并且旧的阈值大于0
- else if (oldThr > 0) // initial capacity was placed in threshold
- //就把旧的阈值赋值给新的数组长度(初始化新的数组长度)
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- //使用默认值
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- //如果新的阈值等于0
- 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
[] newTab = (Node[])new Node[newCap]; - table = newTab;
- //已完成新的数组扩容,开始把就的数据移动到新的数组中,通过循环遍历
- if (oldTab != null) {
- for (int j = 0; j < oldCap; ++j) {
- Node
e; - if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- //如果没有子元素那么说明是下面不是一个链表,直接通过
- // hash&(新的数组长度-1)计算出新的位置,把就的数据放入新的位置
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- //如果该节点为红黑树结构,就进行树的操作
- else if (e instanceof TreeNode)
- ((TreeNode
)e).split(this, newTab, j, oldCap); - else { // preserve order
- /* 有多个数据并且不是树那么该节点上放的是链表,这里是java1.8很精妙的地方,如果
- e.hash& 旧的数组长度 如果等于0, 那么该数据的位置没有发生变化,还在原来的索引位置上,
- 如果不等于0 , 那么就在该值就在 (原来的索引位置+旧的数组长度)的位置上,这里重新创建了
- 两个节点 , 在原来位置上的放入loHead中,在新的位置上的放入hiHead 中,最后把这两组数据
- 放入新的数组中即可。(这里的精妙之处是不用重新计算每一个数据的hash,就可以把旧的数据
- 放入新的数组中去)*/
- Node
loHead = null, loTail = null; - Node
hiHead = null, hiTail = null; - Node
next; - do {
- next = e.next;
- if ((e.hash & oldCap) == 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;
- }
Node内部类
Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。
- static class Node
implements Map.Entry { - final int hash;// hash用来存储key计算得来的hash值
- final K key;// 键
- V value;// 值
- Node
next;// 下一个node节点 - Node(int hash, K key, V value, Node
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() {// 调用底层c++ 返回Key/Value的哈希码值,如果此对象为null,则返回0
- return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule
- }
- 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()))
- return true;
- }
- return false;
- }
- }
-
hashmap的构造函数
- // 构造一个映射关系与指定 Map 相同的新 HashMap。
- public HashMap(Map extends K, ? extends V> m) {
- // 负载因子loadFactor变为默认的负载因子0.75
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- putMapEntries(m, false);
- }
-
最后调用了 putMapEntries(),来看一下方法实现:
- final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {
- //获取参数集合的长度
- int s = m.size();
- if (s > 0) {//判断参数集合的长度是否大于0
- if (table == null) { // 判断table是否已经初始化
- // 未初始化,s为m的实际元素个数
- float ft = ((float)s / loadFactor) + 1.0F;// 得到新的扩容阈值
- int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 新的扩容阈值float自动向下转型为int
-
- // 计算得到的t大于阈值,则初始化阈值,将其变为符合要求的2的n次幂数
- if (t > threshold)
- threshold = tableSizeFor(t);
- }
- // 如果table已初始化过了,并且m元素个数大于阈值,进行扩容处理
- else if (s > threshold)
- resize();
- // 将m中的所有元素添加至HashMap中
- for (Map.Entry extends K, ? extends V> e : m.entrySet()) {
- K key = e.getKey();
- V value = e.getValue();
- // 得到的key 和 value 放入 hashmap
- putVal(hash(key), key, value, false, evict);
- }
- }
- }
-
看了上面源码,可能会对这行代码有译文 float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?
(float)s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数(为了效率,应当尽量减少扩容的次数)。所以 + 1.0F 是为了获取更大的容量。
例如:原来集合的元素个数是 6 个,那么 6/0.75 是8,由于8是 2 的n次幂,那么
if (t > threshold) threshold = tableSizeFor(t);执行过后,新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。