秋春招总结|Java集合类型面试最全总结【易错,易问】

前言: 之前有介绍过在reids中的五种常用类型: string hash list set zset 五种数据类型 。今天来介绍一下关于 java中的集合类型。还会进行基础的介绍不同之处。
基础使用
一直都想记录一下也是因为在刷题过程中,也都用用到各种的栈,队列。今日打算痛定思痛记录一番:
栈 Stack 在《算法》(第四版)中对栈的基础函数有以下比较常用的:

方法 介绍
Stack() 创建一个新栈
void push(Item item ) 添加一个新的元素
Item pop() 删除最近添加的元素,将元素从栈顶取出,有返回值
boolean isEmpty() 判断栈是否已经为空
int size() 返回栈的长度
注: 关于栈的使用地方非常的多 例如对于很多的数的操作:数的前序和后序遍历,对于表达式的求解,前缀与后缀表达式都会有相对应的涉及。
队列 Queue 同上:
方法 介绍
Queue () 创建一个空队列
void enqueue(Item item) 添加一个元素到队列中
Item dequeue () 取出队列中 最早添加的元素
boolean isEmpty() 是否为空
int size() 此时队列的长度
注: 虽然对于队列来说,使用的比较少,但是基础的操作,对于树的层序遍历还是会使用到,同时对于判断平衡二叉树时候 也会使用到。
基础面试
说一说 List,Map,Set三者之前的区别
  • List:存储的元素是不唯一的(可以存储一组由多个元素引用相同的对象) ,有序,可以插入时候 插入多条的null值。
  • Set 不允许有重复的元素,不允许有多个元素应用的是相同的对象,只允许有一个null元素。
  • Map: 使用键值对进行存取,Map本身会维护Key与Value之间的关系,在理论上不同的key可以引用相同的对象,但是Key值不能够是重复的。
Array与ArrayList有什么区别
  • Array可以包含基本类型的对象类型,但是ArrayLsit只能包含对象类型的数据类型。
  • Array的大小值是固定的,ArrayList的动态变化的
  • ArrayList 还提供了Array不具有的方法,addAll()removeAll()iterator()
  • 对于基本数据类型,集合有采用自动封箱来减少代码量。但是对于处理固定大小的数据类型时候,处理起来就会比较慢
ArrayList 和LinkedList 的区别
  • 是否保证线程安全: 都不是同步的,也就是说都不能够保证线程的安全性。
  • 底层的数据结构: ArrayList底层使用的是 Object数组; LinkedList 底层使用的是 双向链表来实现
  • 插入元素与删除元素时候是否会受到位置的影响:如前面所说的 Arr底层使用的是数组,所以在查找的效率会比较高,但是对于插入和删除而言,会动用到很多其他的元素。对于LinkedList而言底层采用链表结构 对于查找不是很有利,但是进行插入和删除会比较快。
  • 是否支持随机访问: LinkedList 底层使用链表,不支持随机访问。ArrayList 底层使用Object数组 可以随机访问
  • 空间占用: ArrayList 的空间浪费主要体现在List列表的结尾会预留一定量的空间容量,而LinkedList的空间发费体现在她的每一个元素消耗的空间都比Arr要多(因为对于一个链表的节点,不仅要存取其值,还要存取其前驱节点和后继节点信息。)
什么是迭代器 Iterator 接口中提供了很多对集合元素迭代的方法。每个集合中都有可以返回迭代器对象的方法iterator()。迭代器在迭代的过程中还可以删除底层的元素。
iterator和ListIterator的区别
  • Iterator可以用来遍历SetList,但是ListIterator只能用来遍历List.
  • lterator 只能向前遍历 (next) 。而ListIterator可以向前遍历,也可以向后遍历(previous())
    *ListIterator 实现了Iterator接口
ArrayList 和Vector 有什么区别 都是集成了List 接口 (List接口继承了Collection接口)都是有序的集合,相当于一种动态的数组可以按照位置索引号取出某个元素,并且运行元素是重复的,这是与HashSet最大不同的地方。主要有两个方面的区别:
  • 同步性:
    对于 Vertor是线程安全的,也就是说她的方法是线程同步的,而ArrayList是线程不安全的。如果有一个线程访问集合,最好使用ArrayList,不用考虑线程安全的情况下,效率会更高。对于有多个线程访问时候,使用到Vertor 因为不需要我们自己去考虑编写线程安全的代码。
  • 数据增长:
    对于ArrayList 与 Vertor都有一个初始的容量大小,当数据增长到存储的容量时候,就需要增加空间, 他们的存储空间,每次都会增加一定数量的存储空间,对于Vertor增长的是原来的两倍,而在Arr中源码表示的是增长 1.5倍。Arr与Vertor都可以设置初始的空间大小。Ver还可以设置增长的空间大小,但是Arr没有提供增长空间的方法。
ArrayList,Vertor,LinkedList的存储特性 ArrayListVertor都是使用数组进行存储,相对之下,查找较快,但是插入和删除比较慢,LinkedList使用双向链表与之相反,关于 为什么Vertor的效率较Arr慢,是因为使用了synchronized(线程安全) 所以性能就会较差。
HashMap 和HashTable 的区别 两者都实现了Map接口 主要区别在 安全性 同步性,和速度上。
  1. 是否线程安全: HashMap是线程不安全,对于 Hashtable 内部都经过了synchronized的修饰,线程同步安全。
    2.效率: 由于synchronize的修饰 效率会交HashMap差一点。
  2. 对于 null key 与 null value的支持:对于HashMap 支持null key但是只能有一个key的值为null。对于 value可以有多个的value值为null。
    而在HashTable中 key值是不可以为null的。
  3. 底层数据结构的处理: 对于HashMap 在JDK1.8中增加了红黑树的处理,对于一个数组中的链表长度大于阙值(8)时候 会将链表自动转换为红黑树,以增加效率,但是在 HashTable中 没有这样的处理。
HashMap 与 HashSet的区别
HashMap HashSet
实现了Map接口 实现了Set接口
储存键值对 仅仅储存对象
使用了Key值一系列的计算 来计算hashCode 使用成员对象来计算 hashCode 对于两个对象来说,hashcode可能是相同的,所以使用 equals来判断对象的相等性
HashSet如何检查是否重复 往HashSet中存放一个元素时候 HashSet首先会根据 对象的hashCode值判断当前集合中此hashCode对应的位置有没有值,如果没有就直接添加,若是有就使用equals 来判断两个对象是否相同,相同就不再存储(保证了Set集合的不可重复性)否则就散列到其他位置存储。
Collection和Collections的区别
  • Collection是集合类的上级接口,继承他的接口主要有Set和List
  • Collections 仅是针对集合封装类的一个类,提供一系列的静态方法对各种几何的搜索,排序,线程安全化等操作。在java.util 包下面。
List、Map、Set 三个接口,存取元素时,各有什么特点?
  • 首先,List 与 Set 具有相似性,它们都是单列元素的集合,所以,它们有一个功共同的父接口,叫 Collection。Set 里面不允许有重复的元素,所谓重复,即不能有两个相等(注意,不是仅仅是相同)的对象 ,即假设 Set 集合中有了一个 A 对象,现在我要向 Set 集合再存入一个 B 对象,但 B 对象与 A 对象equals 相等,则 B 对象存储不进去,所以,Set 集合的 add 方法有一个 boolean 的返回值,当集合中没有某个元素,此时 add 方法可成功加入该元素时,则返回 true,当集合含有与某个元素 equals 相等的元素时,此时 add 方法无法加入该元素,返回结果为 false。Set 取元素时,没法说取第几个,只能以 Iterator 接口取得所有的元素,再逐一遍历各个元素。
  • List 表示有先后顺序的集合, 注意,不是那种按年龄、按大小、按价格之类的排序。当我们多次调用 add(Object) 方法时,每次加入的对象就像火车站买票有排队顺序一样,按先来后到的顺序排序。有时候,也可以插队,即调用 add(int index,Obj e) 方法,就可以指定当前对象在集合中的存放位置。一个对象可以被反复存储进 List 中,每调用一次 add 方法,这个对象就被插入进集合中一次,其实,并不是把这个对象本身存储进了集合中,而是在集合中用一个索引变量指向这个对象,当这个对象被 add 多次时,即相当于集合中有多个索引指向了这个对象,如图 x 所示。List 除了可以以 Iterator 接口取得所有的元素,再逐一遍历各个元素之外,还可以调用 get(index i) 来明确说明取第几个。
  • Map 与 List 和 Set 不同,它是双列的集合,其中有 put 方法,定义如下:put(obj key,obj value),每次存储时,要存储一对 key/value,不能存储重复的 key,这个重复的规则也是按 equals 比较相等。取则可以根据 key 获得相应的 value,即 get(Object key) 返回值为 key 所对应的 value。另外,也可以获得所有的 key 的结合,还可以获得所有的 value 的结合,还可以获得 key 和 value 组合成的 Map.Entry 对象的集合。
    List 以特定次序来持有元素,可有重复元素。Set无法拥有重复元素, 内部排序。Map 保存 key-value 值,value 可多值。 HashSet 按照 hashcode 值的某种运算方式进行存储,而不是直接按 hashCode 值的大小进行存储。例如,“abc” —> 78,“def” —> 62,“xyz” —> 65 在 hashSet 中的存储顺序不是 62,65,78,
两个对象值相同 (x.equals(y) == true),但却可有不同的 hash code,这句话对不对? 对。如果对象要保存在 HashSet 或 HashMap 中,它们的 equals 相等,那么,它们的 hashcode 值就必须相等。 如果不是要保存在 HashSet 或 HashMap,则与 hashcode 没有什么关系了,这时候 hashcode 不等是可以的,例如 arrayList 存储的对象就不用实现 hashcode,当
然,我们没有理由不实现,通常都会去实现的。
heap 和stack 有什么区别 Java 的内存分为两类,一类是堆内存,一类是栈内存。栈内存是指程序进入到一个方法时候,会为这个方法单独分配一块私属空间,用于存储这个方法内部的局部变量,当这个方法结束的时候,分配给这个方法的栈会释放,这个栈中的变量也会随之释放。
堆与栈作用于不同的内存,一般用于存放的是不在当前方法栈中的那些数据,例如使用new 创建的对象都是存放在堆上,所以说 不会随着方法的结束而消失。并且在方法中的局部变量使用到了final修饰后,放在堆中(此处使用到了jvm的相关知识)。
LinkedhashMap的实现原理 也是基于HashMap实现的 不同的是它定义了一个Entry header ,这个 header不是存在方Table里面,是额外独立出来的。LinkedHashMap 通过继承 hashMap 中的 Entry, 并添加两个属性 Entry
before,after, 和 header 结合起来组成一个双向链表,来实现按插入顺序或访问顺序排序LinkedHashMap 定义了排序模式 accessOrder,该属性为 boolean 型变量,对于访问顺序,为 true;对于插入顺序,则为 false。一般情况下,不必指定排序模式,其迭代顺序即为默认为插入顺序。
Comparable和Compartor接口是干什么,列出区别 Java 提供了只包含一个conpareTo方法的Comparable接口,这个方法可以给两个对象排序,用来返回 负数,0 和正数,来表示 小于 等于 大于。
对于 Compartor提供了compare() 和 equals() 两个方法。compare和compareTo的使用大概相同,传进去两个参数。equals() 需要一个对象作为参数,用来判断输入的参数是否和compartor相等,只有两者相等时候 返回true;
框架大体
-》 collection
秋春招总结|Java集合类型面试最全总结【易错,易问】
文章图片

List
  • ArrayList : Object 数组,线程不安全的 查询块 增删慢,效率高。
  • Vertor: Object 数组,线程安全,查询块,增删慢,效率较Arr低。
  • LinkedList : 双向链表,线程不安全,查询块,增删慢,效率高。
Set
  • HashSet : HashMap底层存储,无序,唯一
  • LinkedHashSet: 继承自 HashSet ,内部实现其实使用的是 LinkedHashMap
  • TreeSet 有序 唯一 红黑树。
【秋春招总结|Java集合类型面试最全总结【易错,易问】】-》 Map
秋春招总结|Java集合类型面试最全总结【易错,易问】
文章图片

  • HashMap : 使用数组加链表完成,具体实现有具体的文章讲到。
  • TreeMap: 红黑树。
  • LinkedHashMap: 继承自HashMap 所以底层使用 数组+链表/红黑树实现。但是增加了一个双向链表。使得在插入的时候可以保证插入顺序。
  • Hashtable: 数组加链表实现。链表是为了解决Hash冲突问题。

    推荐阅读