java面试笔记四:集合框架Map集合
发布日期:2021-05-28 16:44:44 浏览次数:10 分类:技术文章

本文共 4389 字,大约阅读时间需要 14 分钟。

1. java面试笔记四:集合框架Map集合

文章目录

1.1. 常用的map实现类

1、HashMap

2、Hashtable

3、LinkedHashMap

4、TreeMap

5、ConcurrentHashMap

1.2. HashMap和Hashtable的区别

  1. HashMap

底层是基于数组+链表,非线程安全,默认容量是16,允许有空的键和值。

  1. HashTable:

基于哈希表实现,线程安全(加了Synchronized),默认容量是11,不允许有null的键和值

  1. hashCode()和equals(),的使用场景

hashCode():顶级类Object里面的方法,所有的类都是继承Object,返回是一个int 类型的数,根据一定的hash规则(存储地址,字段,长度等),映射成一个数组。

elquals:顶级类Object里面的方法,所有的类都是继承Object,返回一个boolean类型,根据自定义的匹配规则,用于匹配两个规则是否一样,一般逻辑:

1、判断地址是否一样。

2、非空判断和Class类型判断

3、强转

4、对象里面的字段–匹配。

使用场景:对象比较,或者集合容器里面排重,比较,排序。

  1. 编写一个User对象,重写里面的hashCode和equals()方法。
import java.sql.Date;import java.util.Objects;public class User {
private int age; private String name; private Date time; public int getAge() {
return age; } public void setAge(int age) {
this.age = age; } public String getName() {
return name; } public void setName(String name) {
this.name = name; } public Date getTime() {
return time; } public void setTime(Date time) {
this.time = time; } @Override public int hashCode() {
// TODO Auto-generated method stub return Objects.hash(age,name,time); } @Override public boolean equals(Object obj) {
// TODO Auto-generated method stub //本类对象的地址与传参是否相等 if(this==obj) return true; //判断对象类型是否相同 if(obj==null||getClass()!=obj.getClass()) return false; User user =(User) obj; return age==user.age && Objects.equals(name,user.name)&&Objects.equals(time, user.time); }}

1.3. HashMap和TreeMap应该如何选择

  1. hashMap

hashMap:散列桶(数组+链表),可以实现快速的存储和检索,但是确实包含无序的元素,适用于在map中插入,删除和定位元素。

  1. treeMap

使用存储结构是一个平衡二叉树–》红黑树,可以自定义排序规则,要实现Comparator接口。能便捷实现内部元素的各种排序,但是一般性能比HashMap差。适用于安装自然排序和自定义排序规则,微信支付里面有个加密规则需要按照字典排序。

  1. Set和Map的关系

核心就是不保存重复的元素,存储一组唯一的对象,set的每一种实现都是对应map的一种封装。HashSet对应的就是HashMap ,TreeSet对应的就是TreeMap(看源码)

  1. 常见Map的排序规则

按照添加顺序使用LinkedHashMap,按照自然排序使用TreeMap,按照自定义排序用TreeMap(Comparetor c)

1.4. 线程安全且效率高的Map集合

  1. 线程安全且效率高的Map集合

1、多线程环境下,可以用Concurrent包下的ConcurrentHashMap

2、使用Collections.synchronizedMap()

  1. ConcurrentHashMap

ConcurrentHashMap,:虽然线程安全,但是他的效率比HashMap高很多。

  1. Collections.synchronizedMap()

Collections.SynchronizedMap():使用的是Synchronized加的锁。线程安全。效率低一些。

  1. 介绍一下你了解的HashMap

HashMap底层采用(数组+链表+红黑树 jdk8才有红黑树)当链表中的节点大于8的时候才会使用红黑树。数组中每一项都是一个链表,实现了数组+链表的结构。hash值相同就放在同一个链表里面。

HashMap是用Node<k,v>[]实现的,Node继承Entry元素,其中table是数组。Entry元素是一个k,v的键值对,它持有一个向下的Entry的引用,table数组的每个首个Entry元素,同时也作为当前Entry链表的首节点,也指向了链表的下个Entry元素。

jdk1.8中,链表的长度大于8,链表会转换成红黑树。

HashMap数据结构

  1. 能否解决一些Hash碰撞,常见的解决办法有哪些?hashMap采用哪种办法?

hash碰撞:不同的key计算得到的hash值相同,需要放到同个bucket中,

常见的解决办法有:链表法,开放地址法,再哈希法等,

HashMap采用的是链表法。

红黑树:jdk8采用红黑树来替代超过8个节点的链表,主要是查询性能的提升,从原来的o(n)到o(logn).随着链表长度增长,查询就会非常耗时,用红黑树进行查询,效率显著提升。

  1. 为什么使用红黑树而不用其他树,比如二叉树,为啥不一直开始就用红黑树,而是到8的长度后才变换。

二叉树查找在特殊情况下也会变成一条线性结构,和原来的链表存在一样的深度遍历问题,查找性能就会变慢。

红黑树是平衡二叉树的一种,插入新数据通过左旋,右旋,变色,等操作来保持平衡,解决单链表查询深度的问题。

此外红黑树保持平衡二叉树,消耗资源,所以前期数据少的时候,采用线性表,数据大的时候采用红黑树。

  1. 说一下hashmap的put和get的核心思想

1、put函数,首先计算hash()值,命中到那个数组桶里面?

2、判断数组是否为空?或者长度是否为0、如果为空,就扩容。

3、如果不为空,就判断节点是否有对应的值?并判断该下标对应的数组里面是否有值,没有就直接将值插进去。

4、如果不为null,说明hash冲突了,看key是否存在,如果存在就直接覆盖。如果不存在,就判断节点是否为树节点,如果是树节点,就遍历插入值,如果不是树节点(是一个链表),就要循环遍历,进行插入。

5、插入后要看链表长度是否大于等于8,如果是,就要将链表转为红黑树。

6、判断是否需要扩容,如果需要,就进行扩容操作。

HashMap的put流程

  1. hashMap中get的思想

1、先获取首节点,因为hash碰撞概率小。没必要进行循环遍历。

2、如果不止一个节点,就要循环遍历,存在多个hash碰撞。

3、先判断是链表还是红黑树

4、如果是链表结构,就循环遍历获取数据。

5、如果是树,就调用树的查找。

1.5. 了解ConcurrentHashMap吗?为什么性能比Hashtable高?说下原理?

  1. ConcurrentHashMap

ConcurrentHashMap是线程安全的,hashtable类基本上所有的方法都是采用synchronized进行线程安全控制的,高并发情况下效率就降低了。

ConcurrentHashMap是采用了分段锁的思想提高性能,锁粒度更细化。

  1. jdk1.7和1.8里面的ConcurrentHashMap实现的区别

jdk8之前,ConcurrentHashMap使用锁分段技术,将数据分成一段一段存储,每个数据段配置一把锁,即segment类,这个类继承ReentrantLock来保证线程安全。

技术方案:Segment+HashEntry

但是jdk8之后改了。取消了分段锁方案,采用了Node<k,v> table,数组+链表+红黑树。从而实现对每一段数据进行加锁,也减少了并发冲突的概率。CAS(读)+Synchronized(写)

计算方案:Node+CAS+Synchronized

  1. 说一下ConcurrentHashMap的put的核心逻辑

1、调用put函数,直接将key,value传进去,和HashMap有点不同。

2、拿到key的hashCode()再次进行hash计算,重hash,为例减少碰撞。spread(key.hashCode())

3、通过tabAt(i)获取table中索引为i的Node元素。

4、casTabAt(i)利用CAS操作,获取table中索引为i的Node元素。与上面的不同,在于无所插入时,就会跳出死循环,结束。

5、如果需要扩容,就会进入扩容程序。

6、进行链表插入,或者红黑树插入数据。

ConcurrentHashMap的流程总结

1、key进行重hash

2、对当前的table进行无条件循环

3、如果没有初始化table,则用initTable进行初始化。

4、如果没有hash冲突,则直接用CAS插入节点,成功后需要判断是否需要扩容,然后结束。

5、(fh=f.hash)==MOVED 如果是这个状态则是扩容操作,先进行扩容。p

6、如果存在hash冲突,就利用Synchronized(f)加锁,保证线程安全

7、如果是链表,则直接遍历插入。如果数量大于8,则需要转换成红黑树。

8、如果是红黑树则按照红黑树规则插入。

9、 最后检查是否需要扩容addCount()

转载地址:https://blog.csdn.net/qq_33322074/article/details/104832890 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:java面试笔记五:线程、进程、以及协程,java多线程实现方式,java线程常见状态
下一篇:java面试基础三:集合框架List面试题

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年02月10日 14时25分55秒