追溯源码观察HashMap底层原理

引言（Map的重要性）

从事Java的小伙伴，在面试的时候几乎都会被问到Map，Map都被盘包浆了。Map是键值集合，使用的场景有很多比如缓存、数据索引、数据去重等场景，在算法中也经常出现，因为在Map中获取元素的时间复杂度为常数！

底层结构

在JDK1.8中Map的底层结构为数组+链表/红黑树。

 在JDK1.7之前为数组+链表

put方法的流程与源码

流程图

判断Map底层的Table数组是否为空，如果为空进行扩容

计算数组下标值

第一步通过hash函数获取hash值。

 hash函数，对象的hashcode与自己右移16位进行异或操作得到hash值

 第二步，hash值与数组的长度减一进行按位与操作（为什么数组的长度减一进行按位与，下篇文章会说）得到数组的下标。

判断该下标是否为空

如果为空进行赋值

 如果不为空，与下标的元素比较key是否相同，相同则覆盖

如果不相同，判断是否为树节点，是则向树中插入数据，否则向链表中插入数据。是树直接执行树的插入操作（较为复杂，没咋看懂）；是链表的过程会遍历检查链表节点判断是否存在相同的key，相同则覆盖，不相同进行链接。

同时在链表中插入节点的时候如果链表的长度大于等于8会将链表转换为红黑树

数据插入完成后，判断是否超过阈值threshold，超过进行resize（）扩容。

 equals重写，hashcode方法未重写，put现象

未重写hashcode方法

public class User extends abstractDemo{public String name;public String getName() {return name;}public void setName(String name) {this.name = name;}public User(String name) {this.name = name;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;User user = (User) o;return Objects.equals(name, user.name);}//    @Override
//    public int hashCode() {
//        return Objects.hashCode(name);
//    }
}

 只重写equals方法会导致equals相同的对象hashcode不相同，依然会插入到table的数组中（set类似），同时get的时候也获取不到对应的值。