一、Hashmap的底层数据结构?
扩展问题
1, 什么是哈希冲突?2, hashmap中的链表转换成红黑树的情况?3, java中的各种树? 二, 说一下hashmap的特点三, 解决hash冲突的办法有哪些?hashmap用的是哪种?四, 当两个对象的hashcode相等时会怎样?五, 什么是哈希碰撞,如何解决hash碰撞?六,hashmap的put方法流程七, hashmap为什么线程不安全?
一、Hashmap的底层数据结构?
jdk1.7之前是数组加链表的结构,数组是hashmap的主体,链表则是为了解决哈希冲突用的;
1.8之后,出现了链表转换成红黑树的情况;
简单来讲,就是多个key通过哈希函数得到的值相同;
2, hashmap中的链表转换成红黑树的情况?当前链表长度超过8并且数组长度超过64才会转红黑树,如果数组长度小于64,那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
3, java中的各种树?二叉查找树:也叫二叉排序树或者二叉搜索树左子树所有节点的值均小于根节点的值,右子树所有节点的值大于或等于根节点的值;左右子树也都是二叉平衡树;
平衡二叉树:平衡二叉树的两个子树的高度差不超过1,并且子树也是平衡二叉树;
红黑树:是二叉查找树和平衡二叉树的升级:①节点是红色或者黑色②根节点是黑色③所有的叶子节点是黑色,叶子是nil节点④任意一条从根到叶子的路径上不能出现两个连续的红色节点⑤任意一条从根到叶子的路径上的黑色节点数都相同
二, 说一下hashmap的特点
1,hashmap的存取是无序的;
2,key不能重复;
3,jdk1.8之前是数组加链表,之后是数组加链表加红黑树
4,扩充阈值:链表的长度大于8并且数组的长度大于64,如果数组长度不超过64,则进行数组扩容
三, 解决hash冲突的办法有哪些?hashmap用的是哪种?
有开放定址法,再哈希法,链地址法,简历公共溢出区,hashmap中采用的是链地址法;
四, 当两个对象的hashcode相等时会怎样?
hashcode相等就是产生了hash碰撞,当发生这种情况时,底层会调用equals方法比较内容是否相等,内容如果相等就会进行覆盖,不等,则会连接到链表后方,链表长度超过8并且数组长度超过64时链表转换成红黑树
五, 什么是哈希碰撞,如何解决hash碰撞?
通过key计算得到的hash码相同就会发生hash碰撞,jdk1.8之前使用链表解决hash碰撞,jdk1.8之后使用链表+红黑树解决
六,hashmap的put方法流程
①首先根据key的值计算hash值,找到该元素在数组中存储的下标
②如果数组是空的,则调用resize方法进行初始化(扩容)
③如果没有hash冲突(碰撞),直接放到对应的数组下标里
④如果冲突了,看key是否已存在,如果已存在就覆盖掉value
⑤如果key不存在,就存入到对应的链表或红黑树结构中
七, hashmap为什么线程不安全?
1.在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。
2.在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况:A线程校验得到不存在hash冲突准备插入数据时吗,时间片耗尽mB线程对该数组位置成功插入了数据,A线程苏醒后,不再进行校验并插入数据,就会造成数据覆盖。
