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中。