put操作

HashMap在存数据时候,会算出key的hash值,然后到数组里中寻址,找到一个位置,给key-value对放到数组的这个位置,但是会出现两个key计算出来的hash值是一样的,这样定位到数组的位置就是一样的了. 这就是hash碰撞.

这就会给这个位置挂一个链表,这个链表里面就会放入多个元素,让多个key-value对同时放在数组的一个位置里面.

get操作

HashMap通过key的hash值计算出数组的位置,然后找到数组的位置去取出对应的值,但是发现数组对应的位置是一个链表,此时会遍历这个链表,从里面找到自己要找的那个key- value对儿就可以了.

假设链表很长,会导致后续找的时候遍历链表性能会很差, O(n),最差的情况下就是给链表遍历一遍.后来做了个优化就是如果链表长度达到一定的长度之后会给链表转换成红黑树. 如果是用红黑树的好处就是你遍历一颗红黑树去找元素此时的时间复杂度是O(logn),所以红黑树的性能会比链表高一些.

为解决 hash 冲突，大概有哪些办法

答：1：好的 hash 算法，细问的话复述一下上题的 hash 算法;
2：自动扩容，当数组大小快满的时候，采取自动扩容，可以减少 hash 冲突;
3：hash 冲突发生时，采用链表来解决;
4：hash 冲突严重时，链表会自动转化成红黑树，提高遍历速度。

hash 冲突时怎么办

答：hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况。
如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；
如果桶中元素已经是链表，并且链表个数大于等于 8 时，此时有两种情况：
1. 如果此时数组大小小于 64，数组再次扩容，链表不会转化成红黑树;
2. 如果数组大小大于 64 时，链表就会转化成红黑树。
这里不仅仅判断链表个数大于等于 8，还判断了数组大小，数组容量小于 64 没有立即转化的原
因，猜测主要是因为红黑树占用的空间比链表大很多，转化也比较耗时，所以数组容量小的情况
下冲突严重，我们可以先尝试扩容，看看能否通过扩容来解决冲突的问题。

HashMap检测到hash冲突后，将元素插入在链表的末尾还是开头？

1、JDK 1.7 采用头插法来添加链表元素，存在链表成环的问题，1.8 中做了优化，采用尾插法来添加链表元素

1、JDK 1.7及之前，为什么采用头插法

缓存的时间局部性原则，最近访问过的数据下次大概率会再次访问，把刚访问过的元素放在链表最前面可以直接被查询到，减少查找次数

2、既然头插法有链表成环的问题，为什么直到 1.8 才采用尾插法来替代头插法

只有在并发情况下，头插法才会出现链表成环的问题，多线程情况下，HashMap 本就非线程安全，这就相当于你在它的规则之外出了问题，那能怪谁？

1.8 采用尾插，是对 1.7 的优化

3、既然 1.8 没有链表成环的问题，那是不是说明可以把 1.8 中的 HashMap 用在多线程中

链表成环只是并发问题中的一种，1.8 虽然解决了此问题，但是还是会有很多其他的并发问题，比如：上秒 put 的值，下秒 get 的时候却不是刚 put 的值；因为操作都没有加锁，不是线程安全的