一)解决哈希冲突的方法有哪些？

哈希冲突指的是在哈希表中，不同的键值映射到了相同的哈希桶，也就是数组索引，导致键值对的冲突

1)设立合适的哈希函数:通过哈希函数计算出来的地址要均匀的分布在整个空间中

2)负载因子调节:

2.1)开放地址法:

1)当发生哈希冲突时，如果哈希表中没有装满，说明哈希表中一定还有空余位置，那么可以把key放到冲突位置的下一个空位置去，从发生冲突的位置开始，依次次向后探测，直到找到下一个空位置为止

2)当插入数据的时候：先通过哈希函数计算到待插入元素在哈希表中的位置，如果该位置中没有元素就直接插入新元素，如果该位置中有元素就使用线性探测找到下一个空位置，直接插入元素,从冲突的位置开始，向后进行探测，把元素放进去

3)但是他会容易把冲突的元素会放在一起，还不可以随意地删除元素，例如把4删掉，44查起来，44进行查询需要依赖于4下标会受到影响，需要加上一个标志位flag，没删除是0，删除了是1，所以说在我们进行闭散列来进行处理哈希冲突的时候，不可以随便删除哈希表中原有的元素，若删除此元素会影响其他元素的查找

2.2)二次探测:

1)线性探测的缺点是将产生冲突的元素放到了一起，堆积到了一块，这与其和找下一个空位置有关系，但是二次探测为了解决该问题，找下一个空位置的方法发生了变化

2)放的位置在H(i)=(H(0)+i^2)%m，保证放的数据不会紧挨着，i代表第几次冲突，空间利用率比较低，更加均匀的分配了元素

2.3)链式地址法:

2.4)再哈希法:当发生哈希冲突的时候再次使用另一个哈希函数计算出一个新的哈希值，然后将元素插入到对应的位置

二)HashMap底层是如何进行实现的？

Hashmap集合在jdk1.7的版本(采用头插法)，底层是通过数组加链表实现的，在jdk1.8的版本底层是中是通过数组+链表+红黑树实现的，为什么要引入红黑树呢，因为链表的查询效率太低，例如在老版本中通过key算出的index(不同的数据通过哈希函数算出的index相同)得知发生冲突的情况下，会存放到同一个链表中，查询效率非常低，因为会从头查到尾，时间复杂度就是O（n),所以在jdk1.8(采用尾插法)中引入了红黑树，当数组长度大于64况且链表长度大于8时，就会直接将链表转化成红黑树

HashMap的数据结构在jdk1.8之前是数组+链表，为了解决数据量过大、链表过长是查询效率会降低的问题变成了数组+链表+红黑树的结构，利用的是红黑树自平衡的特点。

链表的平均查找时间复杂度是O(n)，红黑树是O(log(n))

三)为什么HashMap一定要使用红黑树？

1)AVL树，因为AVL树和插入和删除节点，整体的性能不如红黑树，在AVL树中，每一个节点的平衡因子是左子树高度和右子树高度的差值，平衡因子只能是-1，1和0，当插入和删除元素的时候，任何节点的平衡因子超过了这个范围，就要通过左旋，右旋，左右双旋右左双旋这样的操作来让AVL树保持平衡，但是红黑树相对来说比较宽松，插入和删除操作会导致比较少的旋转操作，因此在频繁的插入和删除的条件下，红黑树的性能可能要高于AVL树

2)二叉搜索树:左右节点极其不平衡，可能会退化成链表

四)什么是负载因子？

负载因子也叫做扩容因子，本质上是一个用于HashMap何时进行扩容的参数，计算方法就是存入表中的元素的个数/表的大小，当HashMap存储的键值对数量超过了HashMap总容量乘以负载因子的时候，就会发生扩容操作

五)为什么HashMap的负载因子是0.75

1)当负载因子比较大的时候，那么就意味着发生扩容的时间比较晚，此时哈希表中存储更多的元素才会发生扩容，空间利用率就会比较高，但是发生哈希冲突碰撞的概率就会比较大，增删查改一个元素的时间就会变长；

2)当负载因子比较小的时候，那么扩容会比较早，此时哈希表数组中存储的元素比较少的时候就发生哈希冲突从而进行扩容了，哈希冲突发生的概率比较低，插入的时间会变快，但是空间利用率就会变得非常的低，增删改查的效率会比较高；

六)说一下hashcode和equals的区别

1)hashcode是指定当前引用类型当前元素，当需要将一个引用类型放到散列表中，就需要重写hashcode生成在数组中的下标

2)equals方法是需要在hashcode定义的数组下标中，遍历链表，判断哪个key是和当前的key是相同的，比较引用类型所指向的对象中的具体内容

衍生问题:

一)如果两个数据的hashcode相同，equals一定相同吗？

不一定，但是这两个数据一定哈希到了同一个位置

二)如果两个数据的hashcode不同，equals不一定相同吗?

一定不相同，在数组中的位置都不一样； 如果两个数据的equals相同，那么内容一定相同，此时的hashcode也是相同的；

三)如果newhashMap(19)，那么哈希表的数组有多大？

当指定大小的时候，哈希表的数组容量一定是2的多少次幂，所以找超过指定容量的2的多少次幂最靠近19，2的5次幂是32；

四)hashmap什么时候开辟bucket数组，占用内存？

当第一次put元素的时候，默认容量是16；

五)hashmap什么时候会进行扩容？

当负载因子超过0.75的时候

六)Hashmap链表长度为8时转换成红黑树，你知道为什么是8吗?

1)当链表长度大于或等于8的时候，如果同时还满足容量大于或等于64的时候，就会把链表转换为红黑树，同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态；

2)每次遍历一个链表，平均查找的时间复杂度是O(n)，n 是链表的长度，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在log(n)

3)最初链表还不是很长，所以可能 O(n) 和 O(log(n)) 的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。

4)通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。

5)个人觉得是数据量较少时，红黑树会频繁的发生左旋或者右旋，浪费cpu性能，所以加入了链表，单个 TreeNode 需要占用的空间大约是普通链表Node 的两倍，而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间，如果要性能就需要牺牲空间，要空间就要牺牲性能；