宋子宪博客

Szx

java面试题:集合相关的面试题
说一下数据结构中的什么是数组?什么是链表?所谓数组,是相同数据类型的元素按一定顺序排列的集合数组:存储区间是连续的...
扫描右侧二维码阅读全文
13
2019/03

java面试题:集合相关的面试题

图片1.png

说一下数据结构中的什么是数组?什么是链表?

所谓数组,是相同数据类型的元素按一定顺序排列的集合
数组:存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;
所谓链表,链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表:链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

说一下什么是哈希表

那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表。哈希表((Hash table)既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。
  哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:
图片2.png
图片3.png

说一下ArrayList底层实现方式?

①ArrayList通过数组实现,一旦我们实例化ArrayList无参数构造函数默认为数组初始化长度为10
②add方法底层实现如果增加的元素个数超过了10个,那么ArrayList底层会新生成一个数组,长度为原数组的1.5倍+1,然后将原数组的内容复制到新数组当中,并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时,重复该过程。是一旦数组超出长度,就开始扩容数组。扩容数组调用的方法 Arrays.copyOf(objArr, objArr.length + 1);
说一下LinkedList底层实现方式?
LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:
图片4.png
既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:
图片5.png

说一下HashMap底层实现方式?

HashMap是由数组+链表组成
put方法底层实现:
通过key的hash值%Entry[].length得到该存储的下标位置,如果多个key的hash值%Entry[].length 值相同话就就会存储到该链表的后面。

ArrayList 和 Vector 的区别

这两个类都实现了 List 接口(List 接口继承了Collection 接口),他们都是有序集合,即存储在这两个集合中的元素的位置都是有顺序的,相当于一种动态的数组,我们以后可以按位置索引号取出某个元素,并且其中的数据是允许重复的,
ArrayList 与 Vector 的区别,这主要包括两个方面:.
(1)同步性:
Vector 是线程安全的,也就是说是它的方法之间是线程同步的,而 ArrayList 是线程序不安全的,它的方法之间是线程不同步的。如果只有一个线程会访问到集合,那最好是使用 ArrayList,因为它不考虑线程安全,效率会高些;如果有多个线程会访问到集合,那最好是使用 Vector,因为不需要我们自己再去考虑和编写线程安全的代码。
(2)数据增长:
ArrayList 与 Vector 都有一个初始的容量大小,当存储进它们里面的元素的个数超过了容量时,就需要增加 ArrayList 与 Vector 的存储空间,每次要增加存储空间时,不是只增加一个存储单元,而是增加多个存储单元,每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡。Vector 默认增长为原来两倍,而 ArrayList 的增长策略在文档中没有明确规定(从源代码看到的是增长为原来的1.5倍)。
ArrayList 与 Vector 都可以设置初始的空间大小,Vector 还可以设置增长的空间大小,而 ArrayList 没有提供设置增长空间的方法。

HashMap 和 Hashtable 的区别

Image 1.png

List 和Set、Map 区别?

Java中的集合包括三大类,它们是Set、List和Map,它们都处于java.util包中,Set、List和Map都是接口,它们有各自的实现类。Set的实现类主要有HashSet和TreeSet,List的实现类主要有ArrayList,Map的实现类主要有HashMap和TreeMap。
  Set中的对象不按特定方式排序,并且没有重复对象。但它的有些实现类能对集合中的对象按特定方式排序,例如TreeSet类,它可以按照默认排序,也可以通过实现java.util.Comparator接口来自定义排序方式。
  List中的对象按照索引位置排序,可以有重复对象,允许按照对象在集合中的索引位置检索对象,如通过list.get(i)方式来获得List集合中的元素。
Map中的每一个元素包含一个键对象和值对象,它们成对出现。键对象不能重复,值对象可以重复。

List、Map、Set 三个接口,存取元素时,各有什么特点?

list:存储: 有序的 可重复的
访问:可以for循环,foreach循环,iterator迭代器 迭代。
set:存储:无序的 不重复的
访问:可以foreach循环,iterator迭代器 迭代
map:存储:存储的是一对一对的映射 ”key=value“,key值 是无序,不重复的。value值可重复
访问:可以map中key值转为为set存储,然后迭代这个set,用map.get(key)获取value
也可以 转换为entry对象 用迭代器迭代

说出 ArrayList,Vector, LinkedList 的存储性能和特性 

ArrayList和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector由于使用了synchronized方法(线程安全),通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。

去掉一个 Vector 集合中重复的元素
通过Vector.contains()方法判断是否包含该元素,如果没有包含就添加到新的集合当中,适用于数据较小的情况下。

Collection 和 Collections 的区别。

Collection是集合类的上级接口,继承于它的接口主要有Set和List。 Collections是针对集合类的一个帮助类,它提供了一系列静态方法实现了对各种集合的排序,搜索和线程安全等操作。

Set 里的元素是不能重复的,那么用什么方法来区分重复与否呢?是用==还是equals()?它们有何区别?

set里的元素是不能重复的,用iterator()方法来区分重复与否。
equals 方法(是String类从它的超类Object中继承的)被用来检测两个对象是否相等,即两个对象的内容是否相等。
==用于比较引用和比较基本数据类型时具有不同的功能:
比较基本数据类型,如果两个值相同,则结果为true
而在比较引用时,如果引用指向内存中的同一对象,结果为true

Last modification:June 26th, 2019 at 01:17 am
如果觉得这篇技术文章对您有帮助,可以请博主喝一杯饮料

Leave a Comment