MAP哈希表

Map接口
1. 说一下的实现原理？
概述：是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变
的数据结构：是一个“散列表”的数据结构，即数组和链表的结合体
基于 Hash 算法实现的：
①当我们往中put元素时，利用key的重新hash计算出当前对象的元素在数组中的下标
②存储时，如果出现hash值相同的key ，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
③获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值
理解了以上过程就不难明白是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
Jdk 1.8中对的实现做了优化，当链表长度大于阈值（默认为8）时，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)
2.的put方法的具体流程？
当我们put的时候，首先计算 key的hash值，这里调用了 hash方法， hash方法实际是让key.()与key.()>>>16进行异或操作，高16bit补0 ，一个数和0异或不变
所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为数组大小是2的幂，计算下标index = (table. - 1) & hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞
设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能
①判断键值对数组table[i]是否为空或为null ，是的话执行()进行扩容
②根据键key计算hash值得到插入的数组索引 i ，如果table[i]==null ，直接新建节点添加，再判断是否扩容，如果table[i]不为空，代表数组中这个位置已经有元素了
③判断table[i]的首个元素是否和key一样，如果相同(以及)直接覆盖value ，若不同则只代表相同，发生哈希冲突
④判断table[i] 是否为，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则考虑插入链表中
⑤遍历table[i] ，判断链表长度是否大于8 ，（数组长度小于64时会首先进行扩容）大于8且数组长度大于64的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可
⑥插入成功后，判断实际存在的键值对数量size是否超过了最大容量，如果超过，进行扩容
3.的扩容操作是怎么实现的？
①在jdk1.8中，方法是在中的键值对大于阀值时或者初始化时，就调用方法进行扩容

文章插图
②每次扩展的时候，都是扩展2倍
③扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。