1、手写实现HashMap
2、解析代码并阐述HashMap1.7到1.8的变化
3、HashMap的遍历方式
4、HashMap与HashSet,Hashtable,ConcurrentHashMap 的区别
一、手写实现HashMap
接口类:
实现类:
测试类:
二、解析代码并阐述HashMap1.7到1.8的变化
1、数据结构
HashMap(1.7):数组 + 单链表
HashMap(1.8):数组 + 单链表 + 红黑树
数组:查找效率高
单链表:解决hash冲突。(单链表能解决的,就不要双链表啦~不然会需要更大的存储空间呢)
红黑树:解决链表查询深度问题,减少搜索时间(插入效率比平衡二叉树高,查询效率比普通二叉树高(存在层次较深的线性结构))
2、defaultLoader:需要扩容的加载因子,即负载因子,默认值为0.75(不建议修改)。
反映HashMap桶数组的使用情况,通过调节负载因子可以平衡HashMap时间和空间的复杂度。
负载因子高:HashMap容纳的键值对多,空间利用率高,碰撞率高,链表长,效率低
负载因子低:HashMap容纳的键值对少,扩容后(扩容条件:超过阈值(桶数组长度 * 负载因子)),碰撞少,链表短,效率高。
3、put过程:
①、对key求hash值(取模),得出数组下标值
②、如果没有碰撞,直接放入数组桶中
③、如果碰撞(hash值相同),以链表方式链接到后面(jdk1.8后,链表长度大于8转红黑树,反之,转为链表结构)
④、如果key已经存在,就覆盖旧值
⑤、如果桶满(超过阈值)就扩容重排
4、get过程:
①、对key求hash值(取模),得出数组下标值
②、hash值和键值相等时,获取值对象
5、多线程条件下:
方式一:Collections.synchronizeMap(hashMap);
方式二:使用线程安全的ConcurrentHashMap
三、HashMap的遍历方式
四、HashMap与HashSet,Hashtable,ConcurrentHashMap 的区别
hashSet:简化版的HashMap,内部实现就是HashMap(不同的key,相同的value)
ConcurrentHashMap
1、数据结构
ConcurrentHashMap(1.7):Segment数组+HashEntry数组+链表(分段锁)
ConcurrentHashMap(1.8):数组+链表+红黑树(CAS+synchronized)【结构同HashMap1.8,图参考HashMap1.8】
2、演变史
3、区别
喜欢也可关注公众号(程序媛的非程序人生)~