文档章节

JDK8 HashMap面试

姜小北
 姜小北
发布于 2018/05/23 10:16
字数 412
阅读 10
收藏 0

1 HashMap的原理,内部数据结构?

    底层使用哈希表(数组+链表),当链表过长会将链表转为 红黑树以实现O(logn)时间复杂度内查找

2 讲一下HashMap中put方法过程?

a 对key求Hash值,然后计算下标

b 如果没有碰撞,直接放入桶中

c 如果碰撞了,以链表的方式链接到后面

d 如果链表长度超过阀值(TREEIFY_THRESHOLD==8),把链表转为红黑树

e 如果节点已存在就替换旧值

f 如果桶满了(容量*加载因子),就需要resize

3 HashMap中hash函数是怎么实现的?还有那些hash实现方式?

a 高16bit不变,低16bit和高16bit做了一个异或

扩展https://www.zhihu.com/question/20733617/answer/111577937

b (n-1)&hash 得到下标

c 还有哪些hash实现方式

4 HashMap 怎样解决冲突,讲一下扩容机制,假如一个值在原数组中,现在移动到了新数组,位置肯定变了,那是什么定位到这个值在新数组中的位置

将新节点加到链表后

容量扩充为原来的两倍,然后对每个节点重新计算哈希值

这个值只可能在两个地方,一种是原下标的位置,另一种是在下标 原下标+原容量 的位置

扩展 https://blog.csdn.net/mgl934973491/article/details/60466487

5 抛开HashMap,hash冲突有哪些解决办法

开放定址 链地址法

6 针对HashMap中某个Entry链太长,查找的时间复杂度可能达到O(n),怎么优化?

链表转为红黑树

 

 

 

 

 

 

© 著作权归作者所有

姜小北
粉丝 15
博文 36
码字总数 19712
作品 2
济南
程序员
私信 提问
面试必问-几种线程安全的Map解析

HashMap线程安全的吗? Java中平时用的最多的Map集合就是HashMap了,它是线程不安全的。 看下面两个场景: 1、当用在方法内的局部变量时,局部变量属于当前线程级别的变量,其他线程访问不了...

java技术栈
2017/08/13
0
0
JDK7 和 JDK8 HashMap效率分析

JDK源码深揪,JDK1.7版本 和 JDK1.8版本比较。 以前写过JDK1.8 HashMap源码解析,这次就看看以前JDK1.7 HashMap的实现 以及 JDK7和JDK8的HashMap效率方面的比较,JDK8 HashMap效率真的比JDK...

荧光牧人
2018/01/07
0
0
JDK8 HashMap的实现原理

一、HashMap结构图 1、JDK7及之前 2、JKD8及之后 由上面结构图可知,在JDK7及之前,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中...

Lienson
03/27
0
0
HashMap(JDK8)知识汇总

其实刚开始接触HashMap的时候看别人博客以及源码是真的一头雾水,最后还是决定找视频入下门比较合适 https://www.bilibili.com/video/av24032788 关于HashMap的面试题这两篇讲的不错: https:/...

codingcoge
03/30
0
0
JDK7与JDK8中HashMap的实现

JDK7中的HashMap HashMap底层维护一个数组,数组中的每一项都是一个Entry transient Entry<K,V>[] table; 我们向 HashMap 中所放置的对象实际上是存储在该数组当中; 而Map中的key,value则以...

Hosee
2016/02/22
9.4K
5

没有更多内容

加载失败,请刷新页面

加载更多

Spring Aware 到底是什么?

通过如下前序两篇文章: Spring Bean 生命周期之“我从哪里来”? Spring Bean 生命周期之“我要到哪里去”? 我们了解了 Spring Bean 的生命周期核心内容,bean 是如何被初始化变为 Ready fo...

tan日拱一兵
36分钟前
4
0
Android 调用第三方浏览器打开网址或下载文件

/** * 调用第三方浏览器打开 * @param context * @param url 要浏览的资源地址 */ public static void openBrowser(Context context,String url){ final Intent intent = new Intent(); int......

丁佳辉
41分钟前
2
0
PostgreSQL系统表及其TOAST是如何定义的

本文只是讲PG怎样定义系统表,而不是修改系统表甚至是定义自己的系统表。 PG系统表,比如:pg_class、pg_attribute、pg_type 等等 这几个表相互关联,后两者要在pg_class记录自己的表定义,而...

有理想的猪
50分钟前
4
0
总结无线AP与AC之间的各种问题

无线网络搭建中,都说AP+AC的组网模式最现在最先进的,但是在使用过程中还是存在一些问题,下面这些有没有大家碰到的呢? 无线网络搭建中,都说AP+AC的组网模式最现在最先进的,但是在使用过程...

xiangyunyan
54分钟前
3
0
IT兄弟连 Java语法教程 流程控制语句 循环结构语句4

do-while循环 Java还有一种循环是do-while。与for、while这些在循环顶部判断条件表达式的语句不同,do-while是在循环底部进行条件表达式的检查。这意味着do-while循环至少要执行一次循环体。...

老码农的一亩三分地
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部