正文 

当前位置： 首页 > 代码 > java教程

java集合面试题总结

z啵唧啵唧 z啵唧啵唧     2022-12-02     270

关键词：

文章目录

集合类常见面试题总结

1、Java中常见的集合

  • Java中常见的集合主要是由Collection和Map这两个接口派生出来的，其中Conllection又派生出三个子接口分别是Set、List、Queue。Java中所有的集合都是Set、List、Queue、Map这四个接口下面的实现类，这四个接口将集合分成了四大类。
  • Set表示无序、元素不可重复的集合
  • List表示有序，元素可以重复的集合
  • Queue表示先进先出的队列
  • Map表示具有映射关系的(key-value)集合

2、容器中那些那些是线程安全的，那些不是线程安全的

线程不安全
  • java.util下面的集合类大部分都不是线程安全我们常用的HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap这些都不是线程安全的，但是他们性能更好。
线程安全
  • Vector和Hashtable，这些集合是线程安全的，也比较古老，他们虽然线程安全但是他们的效率很低，即便想要使用线程安全的集合类，也建议采用集合的工具类中的方法，将集合包装成为线程安全的类，不建议采用古老的线程安全的集合。
  • 从java5开始，Java.util.concurrent包下就支持了大量的支持高并发的集合类，他们既有不错的性能，又能够实现线程安全。

3、Map接口的实现类

  • Map接口有很多实现类，其中比较常见的有HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。
  • 在不需要排序的场景下，我们优先使用HashMap，因为它的性能最好，如果要保证线程安全，可以使用ConcurrentHashMap，它的性能远好于HashTable，因为他在put的时候采用的是分段锁/CAS,而不是像HashTable那样无论是get/put都做了同步处理
  • 对于需要排序的场景我们可以使用LinkedHashMap，LinkedHashMap插入的元素输出顺序和插入顺序一致，但是HashMap的插入顺序和输出顺序不一定一致，如果需要让插入的顺序按照(Key)大小顺序排列输出，我们可以采用TreeMap(),注意TreeMap()传入的类型一定是可以排序的类型(实现了Comparator，或者Comparable接口的类型)

4、Map的put过程(源码分析)

以HashMap为例

  • 1、首次扩容：先判断数组是否为空，如果数组为空则对数组进行第一次扩容

  • 2、索引计算，通过Hash算法，计算键值再数组当中的位置

  • 3、插入数据：

    • 如果当前位置元素为空，则直接插入元素
    • 如果当前元素非空，表示key已经存在，将新添加进来的value值覆盖到原先的value上
    • 如果当前元素非空，且key不存在，则将数据添加到链表末端
    • 如果链表长度达到了8，则将链表转换，判断数组的长度是否大于64。大于的话就将链表转换成为红黑树
    • 再次扩容，如果数组中元素的个数，超过了threshold，则再次进行扩容操作

  • HashMap的put<K key,V value> 方法详解

    • 起始插入第一个元素，判断数组是否为空，如果为空，先对数组进行扩容，jdk默认HashMap初始化大小为16，也就是扩容成16大小，然后根据键值Key通过hash值算法计算出hash值找到在数组中的索引i


    • 扩容的方法resize()

    • 数组在索引i处是否为空，如果为空直接插入

    • 如果不为空，如果不为空说明i位置处有元素，会发生hash碰撞，形成链表

    • p.hash是原本tab[i]处的hash，hash是我传入和hash，如果他俩相等，并且tab[i]处的key和我传入的key相等的，则直接覆盖掉原先位置处的元素，(因为只要key相等，通过同样的hash计算法一定会找到同样的i位置)

    • key不存在，判断是否是tab[i]是否是treeNoe类型，如果是直接将其插入到红黑树中(此时链表转换成为红黑树条件为：链表长度>,并且数组长度大于64)

    • 如果tab[i]不是树，开始遍历链表，当链表长度大于8，调用treeifBin方法，预备将链表转换成为红黑树，如果在8之前找到了key存在的位置，也就直接插进去了。

    • treeifBin方法

    • 当元素添加进去之后，最后还要判断一下，当这个元素添加进去之后，判断一下size的值是否大于扩容阈值，进行扩容。

    • put方法流程图

5、得到一个线程安全的Map的方法

  • 使用HashTable代替HashMap进行使用，但是HashTable性能太差了不建议使用。
  • 使用Collections集合工具类这个包下的SynchronizedMap来将我们线程不安全的map进行包装，将其编程线程安全的map
  • 用java.util.concurrent包下的map，比如ConcurrentHashMap

6、HashMap的特点

  • 非线程安全、性能好、效率高
  • HashMap的key和value都可以为空，但是只能有一个key为null

7、Jdk7和jdk8中HashMap的区别

  • 在jdk7中HashMap是基于数组+链表实现的，但是在jdk8中HashMap是基于数组+链表+红黑树进行实现的
  • 在jdk7中的HashMap没有树化的操作，这样就会导致，当发生hash冲突的时候很严重的时候，在这个桶上形成的链表会越来越长，这样在查询的时候效率就会越来越低，其时间复杂度为O(n)
  • 所谓hash冲突就是两个对象计算出来的hash值相同，但是我们需要注意的是，处于hashMap中同一个链表上的元素，只是他们的数组下标i(i=(n-1)&hash),n是数组的长度)，这个i是相同的，但是他们的hash值不一定相同。详情解释看大佬博客：(187条消息) HashMap的同一链表中对象的hashcode真的一样吗？_Royal_lr的博客-CSDN博客_hashmap同一个链表里的hash值
  • jdk8中，当调用put方法的时候，如果发现链表的长度大于8的时候，就会调用treeifBin方法，然后进入treeifBin方法后，先判断数组的长度，若数组的长度为0，或者数组的长度大于等于最小树化阈值(64)就会将链表转化为红黑树，当这个链表的长度小于6的时候就会将红黑树用转变为链表进行存储元素,这样就可以大大提高查询的效率，链表为O(n),而红黑树是O(logn),大大提高查询效率。

8、HashMap的扩容机制

  • HashMap再没有指定其大小初始化的时候，他的数组容量和扩容阈值都为0，当添加第一个元素的时候，容量设置为HashMap的默认初始化容量：16，然后设置他的扩容阈值：0.75*16=12(0.75)是负载因子
  • 当不是第一次添加元素的时候，他就会判断当前数组的长度和扩容阈值的大小，如果大于了这个扩容阈值就调用扩容方法，将新的数组容量变为老的数组容量的二倍，且新的扩容阈值变为老的扩容阈值的2倍。

9、HashMap中循环链表的产生

  • 产生循环链表主要是因为HashMap它是非线程安全的，产生循环链表就是因为HashMap再多线程的情况下，当重新调整HashMap的大小的时候，会存在条件竞争，因为当两个线程都发现HashMap需要调整大小的时候，他们会同时试着调整HashMap的大小，再调整大小的过程中，存储在链表中的元素，次序会反过来，因为移动到新的桶的位置的时候，HashMap并不会将元素放在链表的尾部，而是放在了链表的头部，所以为了避免尾部遍历。
  • 这也是HashMap非线程安全的原因，HashMap在高并发的put操作时，可能就会形成循环链表，从而引起死循环。

10、如何将HashMap实现线程安全呢？

  • 使用HashTable来替代HashMap(不推荐)
  • java.util.collection下面的synchronizedMap()，将我们的HashMap进行包装使之成为线程安全的map，但是synchronizedMap()底层还是使用了synchronized关键字实现的线程同步，也会导致效率大大降低。
  • 使用java.util.concurrent包下面的这个ConcurrentHashMap，它不仅性能好，而且也能实现线程安全，ConcurrentHashMap的实现细节是比较复杂的，他不是简单的使用了synchronized全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞和冲的，来实现线程安全。

11、HashMap和ConcurrentHashMap的区别

  • HashMap是非线程安全的，这意味着不应该在多线程中对HashMap进行操作，否则容易产生数据不一致的问题，还可能因为并发导致链表成环发生死循环的情况和数据覆盖的情况。
  • Conllections工具类可以将一个Map转换成为线程安全的实现，其实也就是通过一个包装类，然后把所有功能都委托给传入的Map，而包装类是基于synchronized关键字来保证线程安全俺的，底层是互斥锁，性能和吞吐量较低
  • ConcurrentHashMap的实现细节远远没有这么简单，他虽然是线程安全的，但是他的性能也是很可观的，他没有使用一个全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞与冲突，而且ConcurrentHashMap的检索操作是不需要锁的。

12、LinkedHashMap

  • 他是继承于HashMap，他在HashMap的基础上，通过维护了一条双向链表，解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。在实现上LenkedHashMap很多的方法都直接继承于HashMap，仅为维护双向链表重写了部分方法。

13、TreeMap

  • TreeMap基于红黑树实现，映射根据其键的自然顺序排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。TreeMap的基本操作，containsKey、get、put、remove，他的时间复杂度是(logN)。
  • TreeMap包含几个重要的成员变量，root、size、comparator。其中root是红黑树的根节点。他是Entry类型，Entyr是红黑树的节点，它包含了红黑树的6个基本组成：key、value、left、right、parent和color。Entry节点根据key进行排序，包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。

14、ArrayList和LinkedList

ArrayList
  • ArrayList的底层是用数组来实现的，默认第一次插入元素时创建一个大小为10的数组，超出限制时会增加50%的容量，并且数据以System.arraycopy()复制到新的数组。
  • ArrayList按照下标访问元素的性能很高，这是数组的基本优势，直接在数组的末尾添加元素的性能很高，但是如果按照下标添加元素，删除元素，要使用System。arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。
LinkedList
两者的区别
  • ArrayList的底层是一个数组，LinkedList底层是一个双向的链表
  • 对于随机访问ArrayList要优于LinkedList，ArrayList可以根据下标以O(1)的时间复杂度对元素进行访问，而LinkedList的每一个元素都依靠的是地址指针将每个元素连接起来，查找某个元素需要从链表的头部一致遍历到查询位置才能访问到，他的时间复杂度是O(n)。
  • 对于删除、插入元素操作，LinkedList优于ArrayList，因为当元素添加到LinkedList任意位置的时候，不需要像ArrayList那样要将元素整体进行一个大的移动，LinkedList只需要改变引用的指向即可。
  • LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储元素，还存储了两个引用，一个指向前驱节点、一个指向后继节点。

15、那些List是线程安全的

  • Vector
  • Conllections.SynchronizedList
  • CopyOnWriteArrayLsit

16、HahsSet底层接结构

  • HashSet是基于HashMap实现的，默认构造函数是一个初始容量为16，负载因子为0.75的HashMap。它封装了一个HashMap对象来存储所有的集合元素，所有放入HashSet集合中的元素实际上是由HashMap的Key来保存的，而HashMap的Value存储的是一个PRESENT，他是一个静态的保护对象。

17、TreeSet和HashSet的区别

二者共同点
  • 首先TreeSet和HashSet中的元素都是不能够重复的，并且都不是线程安全的
二者区别
  • HashSet中的元素可以是null，但是TreeSet的元素不能够是null
  • HashSet不能保证元素的排序顺序，而TreeSet支持自然排序、定制排序两种方式
  • HashSet底层是采用哈希表来实现的，而TreeSet底层是红黑树

java相关面试题总结+答案(代码片段)

...哪些？19.Collection和Collections有什么区别？Collection是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如List、Set等。Collections是一个包装类，包含了很多静态方法，不能被实例化，就... 查看详情

java基础+集合+多线程+jvm面试题总结(代码片段)

大家好，我是脚丫先生(o^^o)最近系统的总结了前辈们的各种面试题，站在巨人们的肩膀上真是看得远，我想只有对前辈们的知识进行自我的优化与吸收，才能形成适合自己的一份笔记。文章目录一、Java基础1.1面向... 查看详情

java面试题(代码片段)

1.总结，lsit集合，set集合特性。List　　List集合代表一个元素有序、可以重复的集合，集合中每个元素都有对应的顺序索引。List集合允许加入重复的元素是因为它是通过索引访问指定的集合元素。List元素默认按元素... 查看详情

java集合容器篇面试题（上）-王者笔记《收藏版》(代码片段)

...ff08;上）Java基础知识学习总结（下）目录一、集合容器概述1.1什么是集合1.2集合的特点1.3集合和数组的区别  1.4使用集合框架的好处1.5常用的集合类有哪些？1.6List，Set，Map三者的区别和特点？1.7集合... 查看详情

java面试题⭐多线程篇⭐(万字总结，带答案，面试官问烂，跳槽必备，建议收藏)(代码片段)

...1Java基础篇（点击跳转）java面试宝典-基础篇2Java集合框架篇（点击跳转）java面试宝典-集合框架篇3J 查看详情

java面试题⭐多线程篇⭐(万字总结，带答案，面试官问烂，跳槽必备，建议收藏)(代码片段)

...1Java基础篇（点击跳转）java面试宝典-基础篇2Java集合框架篇（点击跳转）java面试宝典-集合框架篇3J 查看详情

5千字长文，深度总结hashmap底层实现&面试题收藏(代码片段)

...！！！今天的主题：HashMap反观整个Java的集合框架，我们讲了ArrayList、LinkedList、Stack、Queue、Deque、PriorityQueue等等集合，以及它们背后所对应的数据结构，今天我们来看一下java集合中，最为重要的&#x... 查看详情

java面试题及答案，2020年最新面试题集合

...gCloud、RabbitMQ、Kafka、Linux等技术栈，一共有上百个面试题集合，资源难得，而且还是近一年的真实面试题； 由于面试题答案太多我已经整理成文档，都上传到网盘了； 面试题 查看详情

java开发面试题：spring面试题总结

今天分享的java实习生常见面试题，是spring专场，主要是针对spring总结的面试题，有需要的小伙伴可以收入囊中了！1、SpringFramework中有多少个模块，它们分别是什么？Spring核心容器–该层基本上是SpringFramework的核心。它包含以下... 查看详情

java八股文面试题(重点)

...0版）JAVA面试八股文Java八股文2021互联网大厂面试问题集合《剑指offer》Java版全系列题解（2021版，持续更新！）2020最新-精选基础算法100题（面试必备）Java基础知识面试题（2020最新版）2017年-应... 查看详情

java八股文面试题(重点)

...0版）JAVA面试八股文Java八股文2021互联网大厂面试问题集合《剑指offer》Java版全系列题解（2021版，持续更新！）2020最新-精选基础算法100题（面试必备）Java基础知识面试题（2020最新版）2017年-应... 查看详情

面试总结目录

​​面试总结(一)​​​​​​面试总结(二)​​​​​​面试总结(三)​​​​网易面试总结​​​​​​记录面试问题)​​​​​​Java面试题全集（中)​​​​​​Java面试题全集（下）​​​​​​Java面试题全集（上）​... 查看详情

java经典面试题总结

Java经典面试题总结继续更新，有需要的小伙伴可以路过不要错过了！看上一篇面试题总结的反响还是很不错的，就继续更新了，也非常感谢各位小伙伴的持续关注……这次更偏基础一些！1、String和StringBuffer的区别?答：JAVA平台... 查看详情

java面试题全集（上）(中)（下）（转）+自己总结

Java面试题自己总总结https://www.cnblogs.com/songanwei/p/9366427.htmlJava面试题全集（上）https://blog.csdn.net/jackfrued/article/details/44921941 Java面试题全集（中）https://blog.csdn.net/jackfrued/article/details/449311 查看详情

java开发基础面试题，java研发工程师年终总结

Spring面试高频问题SpringMVC面试高频问题MyBatis面试高频问题SpringBoot面试高频题SpringCloud面试高频问题Redis高级面试题Dubbo高频常问面试问题Java虚拟机（JVM）MySQL数据库高频面试问题Java高频面试专题合集解析：当然在这还... 查看详情

java/计算机网络/操作系统面试题总结（未完待续）(代码片段)

...nal异步/同步堵塞/非堵塞设计模式1.单例模式2.观察者模式集合ArrayListHashMap网络IO1.BIO2.NIOJava异常处理深拷⻉vs浅 查看详情

java经典面试题总结

上一次更新的java面试题，很多小伙伴反应很简单，其实上一期更新的就是更偏基础的面试题，但这并不意味着，面试就这么简单，在java的学习中，有从Java基础、框架、设计模式等等都是重点学习的点。在本文的面试题分享中，... 查看详情

java集合以及面试题

1，集合的框架体系图? 2，java集合可分为Collection和Map两种体系2.1  Collection接口：包括set和listSet:元素是无序的、不可重复的集合。List：元素是有序的、可以重复2.2  Map具有映射关系“key-vlue”的集合3，首先我们... 查看详情