HashMap是如何解决Hash碰撞的问题的？

首先要知道什么是Hash碰撞，通俗的讲就是当两个key运算出来的hash值与数组长度n-1进行与运算之后发现定位出来的位置是一样的。

这就是Hash碰撞、Hash冲突。

HashMap是通过在两个key计算出的同一个位置上挂一个链表，在这个链表放入多个元素。

让多个key-value对，同时放在数组的同一个位置上。

后面在get的时候，如果发现该位置挂了一个链表，只要遍历这个链表找到自己的key-value就可以了。

这里就会有一个性能问题？假设你的链表随着时间的推移变得很长，在后续遍历的时候，性能就会比较差，时间复杂度是O(n)。

所以HashMap做了一个优化，如果链表达到了一定的长度之后，会将其转换为红黑树，红黑树的好处就是遍历的时候时间间复杂度是O(logn)，性能会比链表高一些。