一、快速入门

  1. HashMap的常用方法

过于简单，略

  1. HashMap的几个重要知识点

HashMap是无序且线程不安全的数据结构
HashMap 是以key–value对的形式存储的，key值是唯一的（可以为null），一个key只能对应着一个value，但是value是可以重复的。
HashMap如果再次添加相同的key值，它会覆盖key值所对应的内容，这也是与HashSet不同的一点，Set通过add添加相同的对象，不会在添加到Set中去。
HashMap 提供了get方法，通过key值取对应的value值，但是HashSet只能通过迭代器Iterator来遍历数据，找对象。

二、JDK7与JDK8的HashMap区别

既然讲HashMap，那就不得不说一下JDK7与JDK8（及jdk8以后）的HashMap有什么区别：
jdk8中添加了红黑树，当链表长度大于等于8的时候链表会变成红黑树
链表新节点插入链表的顺序不同（jdk7是插入头结点，jdk8因为要把链表变为红 黑树所以采用插入尾节点）—>防止成环状列表,1.8避免，依旧避免不了节点丢失的问题。
hash算法简化 ( jdk8 )—>实质将高16位与低16位进行异或运算
resize的逻辑修改（jdk7会出现死循环，jdk8不会）—>计算新位置并没有跟1.7一样重新尽心hash运算，而是用了原位置+原数组长度一种很巧妙的方式，而这个结果与hash运算得到的结果是一致的，只是会更快。

三、HashMap的容量与扩容机制

  1. HashMap的默认负载因子

0.75f
会确保容量的值永远都是2的幂，为了保证负载因子*容量是一个整数，0.75相对较为合理
理论上讲，负载因子越大，导致hash冲突的概率越大，负载因子越小，扩容相对较为频繁->费的空间也就越大。
故0.75相对较为合理的

  1. HashMap的扩容机制

每次put数据之后可能会触发扩容，当写完数据之后的size达到扩容阈值的话，它就会触发扩容的操作。
阈值(threshold)=负载因子(loadFactor)x容量(capacity)；
当HashMap中table数组(也称为桶)长度>=阈值(threshold)就会自动进行扩容，扩容的规则是这样的，因为table数组长度必须是2的次方数，扩容其实每次都是按照上一次tableSize位运算得到的就是做一次左移1位运算;也就是说扩容后的容量是当前容量的两倍，但记住HashMap的扩容是采用当前容量向左位移一（newtableSize=tableSize<<1），得到的扩容后容量，而不是当前容量x2的概念。
采用位运算cpu可以直接进行处理，简介高效。

  1. HashMap中散列表数组初始长度

1<<4=16
创建hashMap时可以设置初始化容量和设置负载因子，但hashMap会自动优化设置的初始化容量参数，确保初始化容量始终为2的幂
为何非要是16？
首先我们看hashMap的源码可知当新put一个数据时会进行计算位于table数组(也称为桶)中的下标：
int index =key.hashCode()&(length-1);
每次扩容都是以 2的整数次幂进行扩容,因为是将二进制进行按位于，(16-1) 是 1111,末位是1，这样也能保证计算后的index既可以是奇数也可以是偶数，并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，这样也就减少了hash的碰撞以及hashMap的查询效率。

四、HashMap的结构

JDK7与JDK8及以后的HashMap结构与存储原理有所不同：
Jdk1.7：数组 + 链表 ( 当数组下标相同，则会在该下标下使用链表)
Jdk1.8：数组 + 链表 + 红黑树 (预值为8 如果链表长度 >=8则会把链表变成红黑树 )
Jdk1.7中链表新元素添加到链表的头结点,先加到链表的头节点,再移到数组下标位置
Jdk1.8中链表新元素添加到链表的尾结点
(数组通过下标索引查询，所以查询效率非常高，链表只能挨个遍历，效率非常低。jdk1.8及以
上版本引入了红黑树，当链表的长度大于或等于8的时候则会把链表变成红黑树，以提高查询效率)

五、HashMap存储原理与存储流程

  1. HashMap存储原理

首先计算出key的hashCode为h，然后与无条件右移16位后的二进制进行异或最终得到hash的值
判断table是否为空？初始化=>resize方法只是初始化并没有分配空间
获取下标：i = (table.length - 1) & ((h = key.hashCode()) ^ (h >>> 16))
把传过来的key和value存到该数组下标当中。
如该数组下标下以及有值了，则使用链表，jdk7是把新增元素添加到头部节点 jdk8则添加到尾部节点。

  1. HashMap存储流程

前面寻址算法都是一样的，根据key的hashcode经过高低位异或之后的值，再按位与 &(table.length - 1),得到一个数组下标，然后根据这个数组下标内的状况，状况不同，然后情况也不同，大概分为了4种状态：

  1. 该数组下标的内容为空
  2. 该数组下标的内容不为空，但node未链化
  3. 该数组下标的内容已链化，但未转红黑树
  4. 冲突很严重，链表已转为红黑树了

    六、jdk8中HashMap为什么要引入红黑树？

    其实主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题，因为链表结构的查询效率是非常低的，他不像数组，能通过索引快速找到想要的值，链表只能挨个遍历，当hash冲突非常严重的时候，链表过长的情况下，就会严重影响查询性能，本身散列列表最理想的查询效率为O(1)，当时链化后链化特别严重，他就会导致查询退化为O(n)为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题，当链表长度>=8的时候链表就会变成红黑树，红黑树其实就是一颗特殊的二叉排序树嘛，这个时间复杂…反正就是要比列表强很多。

    七、扩容后的新table数组，那老数组中的这个数据怎么迁移呢

    迁移其实就是挨个桶位推进迁移，就是一个桶位一个桶位的处理，主要还是看当前处理桶位的数据状态把，这里也是分了大概四种状态：
  • 该数组下标的内容为空
  • 该数组下标的内容不为空，但node未链化
  • 该数组下标的内容已链化，但未转红黑树
  • 冲突很严重，链表已转为红黑树了