导图社区 HashMap
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
Java是一门面向对象编程语言,不仅吸收了C++语言的各种优点,还摒弃了C++里难以理解的多继承、指针等概念,因此Java语言具有功能强大和简单易用两个特征。本思维导图是对java基础知识总结,比较全面,干货,实际开发总慢慢的总结的,花费了大量的时间,希望对你有帮助!适用于java面试,软件开发,架构师,Java,互联网,程序,程序员,阿里面试的朋友。
下列思维导图分支内容包括:数据库,数据库考试,数据库面试,计算机。
社区模板帮助中心,点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
HashMap
基础知识
位运算
https://blog.csdn.net/xiaopihaierletian/article/details/78162863
类型
与运算&
简介
两个操作数都为1,结果为1,否则为0
实例
0&0=0,0&1=0,1&1=1
异或^
两个值不同为1,相同为0
0^0=0,0^1=1,1^0=1
或运算|
两个数只要有一个为1,结果就为1,否则为0
0|1=1,0|0=0,1|1=1
取反运算~
按二进制取反
~1=0,~0=1
左位移<<
num<<value,num转为2进制向左位移value位,乘上2^n
<<
num<<1
1010
10100
右位移>>
num>>value,num转为2进制向右位移value位,带符号右移,正数高位补零,负数补1
>>
num>>1
0101
>>>
无符号右移,忽略符号位,右移后左边空出来的位用0填充,移出右边的丢弃
-14 >>>2
11111111 11111111 1111111111110010
00111111 11111111 1111111111111100
哈希码 hashCode
hashCode 默认为JDK根据对象生成的地址
区别
hashCode 相同,对象的值不一定相同
equal 相同,对象的值一定相同
先比较 hashCode,不相同肯定不相同,再比较 equal ,相同则一定相同
思考
a="a" ACI 为 97
Integer b = new Integer(97)
a.hashCode b.hashCode
实现
1.7是数组+链表
1.8是数组+链表+红黑树
节点>=8转化为红黑树
节点<6转化为链表
红黑树
特征
比平衡二叉树多了颜色
每个节点不是红色就是黑色
根节点都是黑色
新增节点默认红色,如果产生红色相连,变色或者旋转
变换规则
为什么不用其他树
二叉搜索树
没有平衡值,第一次添加的节点作为根节点,如果接下来添加的节点都比根节点大,会形成链表
AVL缺点
查询快,插入删除慢
阈(yu)值
作用
扩容,节点数量>阈值(加载因子*数组长度)(12>=16*0.75)
数值
0.75
综合时间复杂度和空间复杂度
<0.75
内存充足,空间换时间
>1
空间利用率高,哈希碰撞多,时间换空间
数组初始化大小
必须是2^n
因为必须保证 2^n-1为01111
如果为14,在做 & 运算的时候,hashCode 的最后一位,不管是 0 还是1,&0 都为 0,易造成冲突
所以必须让结果取决于 hashCode 的二进制,所以必须是2^n
hashCode 01101
2^n-1 01110
扩容
容量扩为原来两倍,对每个节点重新计算index值
JDK7
数组+链表
头插法
死循环Bug
JDK8
数组+链表+红黑树
尾插法
Node 封装键值对
长度大于8转化为红黑树,时间复杂度为logn
优化
哈希冲突
开放地址法
发生冲突时,如果 hash 表未被装满,所以还有坑位,那就可以把 key 放到冲突位置后面的空位上面,缺点是查找和扩容。
发生冲突,地址+1
再哈希法
冲突时,再计算另一个 hash 值,直到冲突不发生,增加了计算时间,如果不考虑时间成本,对查询元素的要求极高,就可以考虑。
链地址法
HashMap 采取的方法,用一个链表存储相同 hash 值的数据。
获取元素
链表
扩容优化
提前设置初始容量 (初始容量 = 预知数据量/加载因子)减少resize操作,提高效率。
扩容 16*0.75 = 12 初始容量 = 预知数据量/加载因子 16 = 12/0.75
技巧
(n-1)&num
n对num取模,n为2^n
1>>4=16
问题
1、HashMap 的初始容量是多少?
答:16,底层是 1<< 4,左移 4 位,表示 2 的 4 次方。
2、HashMap 底层如何解决 Hash 冲突问题?
答:1.7 使用链表,1.8 使用链表 + 红黑树
3、HashMap 是否线程安全
答:不是线程安全
4、HashMap 是否支持 key 为空对象?
答:支持,放在数组为 0 的位置或者第一个链表。 HahTable 对象的 key、value 值都不可为null。
5、HashMap 1.7 扩容存在哪些问题?
1、在 JDK7,链表使用头插法,在多线程情况下,存在死循环问题。每次在数组扩容的时候,数组长度发生了变化,需要重新计算 index。把原来的table复制到新的table里面,因为 table是全局的,多线程情况下,会产生两个 new Table,赋值的时候,修改了原来 table 的共享的next,T1 线程扩容完后,改变原来 table B.next =A,A.next =B。JDK1.8 已经解决该问题。
2、线程不安全问题。
3、链表过长导致效率过低。
6、加载因子为什么为 0.75 不是其他
加载因子越大,index 下标冲突越大,但是空间利用很高; 加载因子越小,index 下标冲突越小,空间利用率不是很高; 下标冲突大,查询成本高,反之非常低; 所以必须在时间和空间之间做一个均衡。
7、put 方法如何实现?
1.对 key 求 hash 值,然后再计算下标 2.如果没有碰撞,直接放入数组中 3.如果碰撞了,放到链表中 4.如果节点已经存在,就替换旧值 5.如果链表长度超过阈值,转换成红黑树 6.如果同满了(容量*加载因子),就resize
8、index 冲突和 hash 冲突区别?
index:对象不同,底层二进制运算产生相同 index,h&(length-1)必须是奇数 ; hash:对象不同,hashCode 相同
9、HashMap 链表是单向还是双向
答:单向
10、链表长度过长会有什么问题
答:效率降低,时间复杂度为O(N)
11、HashMap 扩容多少倍
2倍