面试题--HashMap和TreeMap的区别和应用场景有啥区别?

简介: 然后底层调用key的hashCode()方法得出hash值;过哈希表哈希算法,将hash值转换成数组的下标(注1),下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有值。此时,就会拿着key和链表上每个节点的key进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖,如果最终长度大于8就会转成红黑树,红黑树插入;

HashMap TreeMap
存储方式 K-V(无序) K-V(有序)
底层实现 基于数组+链表+红黑树 基于红黑树
时间复杂度 链表长度<8and冲突较少,时间复杂度O(1);链表长度>8—>转红黑,时间复杂度为O(logn);链表冲突较多时,时间复杂度O(n);综上所述:平均时间复杂度为O(1); 因为它是基于红黑树的,所以时间复杂度为O(logn);
应用场景 常用于缓存、消息中间件等 常用于排序
效率 HashMap>TreeMap
HashMap的put()和get()的实现原理:

Put()方法:
首先将key,value封装到Node节点对象当中;
然后底层调用key的hashCode()方法得出hash值;
过哈希表哈希算法,将hash值转换成数组的下标(注1),下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有值。此时,就会拿着key和链表上每个节点的key进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖,如果最终长度大于8就会转成红黑树,红黑树插入;
Get()方法:
先调用key的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标;
通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有,则返回null;
如果这个位置上有单向链表,那么它就会拿着key和单向链表上的每一个节点的key进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的key和参数key进行equals返回true,那么此时该节点的value就是我们要找的value了
注1:hash值和数组长度取模就能得到下标的值,同时a%b = (b-1)&a;当b为2的指数的时候等式成立;(与运算两者同为1的时候就为1),(数组长度-1)&hash快捷资讯

Jdk8中对寻址算法和哈希算法如何优化的?
哈希算法:
我们来看一下java源码中是如何对哈希算法进行优化的

我们可以看到hash算法里面并没有直接使用hashCode的值,而是先将哈希code的值向右移16位然后再与hashCode值进行异或运算(相同为0,不同为1), 通过哈希算法的优化,一定程度避免了hash冲突,让数据更加散列

相关文章
|
1天前
|
存储 Java 程序员
Java面试题:请解释Java中的永久代(PermGen)和元空间(Metaspace)的区别
Java面试题:请解释Java中的永久代(PermGen)和元空间(Metaspace)的区别
26 11
|
1天前
|
存储 安全 Java
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
12 3
|
1天前
|
Java 编译器 程序员
Java面试题:解释Java中的异常处理机制,包括checked异常和unchecked异常的区别。
Java面试题:解释Java中的异常处理机制,包括checked异常和unchecked异常的区别。
9 0
|
1天前
|
监控 网络协议 Java
Java面试题:解释Java NIO与BIO的区别,以及NIO的优势和应用场景。如何在高并发应用中实现NIO?
Java面试题:解释Java NIO与BIO的区别,以及NIO的优势和应用场景。如何在高并发应用中实现NIO?
6 0
|
1天前
|
网络协议 Java
Java面试题:什么是Java中的接口?与抽象类有什么区别?
Java面试题:什么是Java中的接口?与抽象类有什么区别?
7 0
|
2天前
|
存储 安全 Java
Java面试题:请解释Java内存模型,并说明如何在多线程环境下使用synchronized关键字实现同步,阐述ConcurrentHashMap与HashMap的区别,以及它如何在并发环境中提高性能
Java面试题:请解释Java内存模型,并说明如何在多线程环境下使用synchronized关键字实现同步,阐述ConcurrentHashMap与HashMap的区别,以及它如何在并发环境中提高性能
6 0
|
6天前
|
存储 算法 Java
Java面试之SpringCloud篇
Java面试之SpringCloud篇
27 1
|
6天前
|
缓存 NoSQL Redis
Java面试之redis篇
Java面试之redis篇
22 0
|
6天前
|
SQL 关系型数据库 MySQL
java面试之MySQL数据库篇
java面试之MySQL数据库篇
14 0
java面试之MySQL数据库篇
|
6天前
|
存储 缓存 前端开发
Java八股文面试之多线程篇
Java八股文面试之多线程篇
19 0
Java八股文面试之多线程篇