HashMap

基本知识点
  • hahsMap 负载由于默以为0.75,作用是用于决议什么时分扩容、
  • 默许数组巨细为16,而且数组巨细永远为2的倍数,即使咱们实例化时分传入非2的倍数,map内部也会找一个最接近的2的倍数巨细代替它使用
  • 每次扩容都是2的倍数,由于数组下标是有key的hash和数组长度-1做与运算得到的。关于2的倍数-1的16进制,低位都是1,1&1=0,1&0=0,这样能够确保hash每一位都参加核算,使得愈加散列。假如非2的倍数,呈现了0,那么0和任何数与都是0,那么有些下标永远核算不到。
  • 当数组长度大于64时,且链表长度大于8,那么会转化链表为红黑树,当链表长度小于6时分,会再讲红黑树转为链表。转化只会在put元素时分触发
简介概括原理
  1. HashMap内部保护了一个Node目标数组,留意的是:实例化hashMap目标时分,并不会给内部保护的数组table初始化,仅仅是在hashMap目标中保存一下传入的默许数组巨细和负载因子。数组第一次初始化是在put时分。
  2. 每次put值的时分,会先对Key进行hash散列运算,并和数组长度-1做与运算,得到其在数组中的下标。
  3. 首要判别数组是否现已初始化过,假如没初始化过,会调用resize()调整数组长度并进行初始化操作。
  4. 依据下标找到对应的Node目标,假如目标为Null,那么就实例化一个Node目标,保存key和value。假如目标不为Null,那么判别其目标是否是TreeNode,假如目标类型是TreeNode,那么阐明当时存储的红黑树,假如不为TreeNode类型,那么阐明存储的是链表式结构。
  5. 假如是红黑树,那么经过红黑树的排序性质(二叉排序树)来查找节点,假如找不到节点,则依据value巨细在红黑树合适的方位来刺进Node。刺进结束,依据需求来平衡红黑树。
  6. 假如是链表,那么顺次遍历比对key查找节点,查找到后替换值,没找到则在后续刺进新目标Node。
  7. 刺进结束后,会判别元素个数和数组长度乘负载因子的巨细,然后决议是否扩容
  8. 获取元素时分,直接查找元素获取目标
  9. 移除元素时分,先查找到对应元素,然后再移除,移除时分并不会触发resize办法,然后也不会转化链表和红黑树结构。

HashMap原理.png

关于数组扩容,resize办法+tableSizeFor办法
  • capcity

    HahsMap中实际没有专门界说这个变量,只要一个默许值16,这个变量的含义是指map中数组的长度巨细,是咱们能够在实例化map时分传入的。咱们实例化目标时分传入的数组长度,假如不是2的倍数,那么map中会找到最接近其的2的倍数作为数组长度。这儿找到最接近其2的倍数使用的办法便是tableSizeFor。

    每次数组假如判别需求扩容时分,那么都会调用resize办法进行处理,这儿包含数组的第一次初始化。

  • resize办法做的工作
  1. 将原数组长度乘2算出新的数组长度。
  2. 依据负载因子和当时数组长度核算出新的数组最大元素约束,保存到map中。
  3. 生成新的Node数组
  4. 遍历当时的table,将每个元素都放到新数组中的对应方位中。
  • 什么时分会触发扩容调用resize办法呢?

    从源码流程中能够看到,在put元素时分,假如元素个数大于数组长度乘以负载因子,那么就会触发扩容

  • 什么时分红黑树转为链表呢?

    在每次扩容办法resize被调用后,在扩容办法里会判别假如是红黑树,那么会调用其spilt办法判别是否Node个数小于等于6,假如是则转为链表结构。

所以在删除元素时分并不会触发红黑树转为链表

依据key查找下标的办法
  1. 调用key的hashCode办法,得到hash值
  2. 取hash的高16位和其低16位做异或得到新的hash值作为key的最终hash值,记为hash1
  3. 拿hash1和数组长度-1做与,得到数组下标。
  • 高16和地16做异或原因

数组长度一般不会特别大,将hash高16和低16做一次异或运算,确保key的hash悉数参加数组下标的核算,添加散列度。

  • 和数组长度-1做与原因

避免下标越界。

hashMap key能够为Null吗

能够,关于key为null,那么会将数组保存到数组的第一位,即数组下标永远为0

为什么HashMap的默许负载因子是0.75呢?而不是其他呢?

设计者经过各种核算得出的最优扩容。

jdk1.7和jdk1.8 HashMap 的差异
  1. jdk1.7不存在红黑树,1.8存在红黑树,1.7结构是数组+链表,1.8是数组+链表+红黑树
  2. 1.7将数据刺进到链表头部,1.8刺进数据到链表尾部
  3. 1.7在元素刺进前查看扩容,1.8是在刺进后查看扩容
为什么HashMap线程安全
  • 关于jdk1.8

    咱们刺进数据时分,假如数组下标当时是null,那么会直接生成一个新的Node目标刺进数组,多线程中,这儿可能呈现同时刺进一个新数据,后边数据将前边数据掩盖的状况。

  • 关于jdk1.7

    1.7链表中刺进Node是刺进到头部,所以每次扩容后,原链表相当于倒置的刺进到了新的数组中。他会从旧数组的链表头部开端遍历,查找其在新数组的下标,然后刺进,假如存在A和B,在旧数组中链表方位为A->B,扩容后,他两正好还在同一个数组下标,那么有以下流程。

多线程扩容时分:

  1. 线程1,扩容时分会循环遍历链表,首要拿出A,赋给暂时遍历E,
  2. 此时线程2现已履行完扩容,数组现状是对应下标为B->A
  3. 接着线程1继续履行,将E的next指向新数组下标的元素,此时新数组下标的元素现已是B了,所以A->B->A,接着,死循环就开端了。
putMapEntries办法什么用,做什么事

关于咱们实例化时分传入的map调集,该办法用于遍历传入的map,将其内部数据顺次传入到当时的map中。