南昌淘宝网站制作公司,好用的网页编辑器,个人做商机网站如何盈利,单页网站程序Java集合面试(上)
集合概述
Java 集合#xff0c;也叫作容器#xff0c;主要是由两大接口派生而来#xff1a;一个是 Collection接口#xff0c;主要用于存放单一元素#xff1b;另一个是 Map 接口#xff0c;主要用于存放键值对
说说List#xff0c;Set,Queue#…Java集合面试(上)
集合概述
Java 集合也叫作容器主要是由两大接口派生而来一个是 Collection接口主要用于存放单一元素另一个是 Map 接口主要用于存放键值对
说说ListSet,QueueMap的区别
List:存储的元素是有序的可重复Set:存的元素不可重复Queue:按照特定的规则排序可重复Map:存键值对key和value无序key不可重复
集合框架底层数据结构
List
ArrayList:Object[] 数组VectorObject[] 数组。LinkedList双向链表
Set
HashSet:基于 HashMap 实现的LinkedHashSet:LinkedHashMap 来实现的TreeSet红黑树
queue
PriorityQueue: Object[] 数组来实现小顶堆DelayQueue:PriorityQueueArrayDeque: 可扩容动态双向数组。
Map
LinkedHashMap:基于拉链式散列结构即由数组和链表或红黑树组成Hashtable数组链表组成的TreeMap红黑树HashMapJDK1.8 之前 HashMap 由数组链表组成的数组是 HashMap 的主体链表则是主要为了解决哈希冲突而存在的
怎么选用集合
我们需要根据键值获取到元素值时就选用 Map 接口下的集合需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。我们只需要存放元素值时就选择实现Collection 接口的集合需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList然后再根据实现这些接口的集合的特点来选用
为什么要使用集合
Java 集合的优势在于它们的大小可变、支持泛型、具有内建算法等
List
ArrayList和Array(数组)的区别
集合可以进行动态扩容或者缩容数组被创建就不能改变了集合可以用泛型来保证类型安全数组不行集合只能存对象基本类型只能存对应包装类数组可以存对象和基本数据类型集合支持插入删除遍历等操作还有很多api但是数组只能通过下标访问元素不具备动态添加删除元素的能力集合创建不需要指定大小而数组需要
ArrayList可以添加null值吗
ArrayList 中可以存储任何类型的对象包括 null 值
ArrayList插入和删除元素的时间复杂度?
插入:
头部插入O(n),因为所有元素向后移动一个位置尾部插入:没到容量时是O(1),到了是O(n)执行一次O(n)操作复制到新数组在执行O(1)指定位置插入:需要将目标位置之后的所有元素都向后移动一个位置然后再把新元素放入指定位置O(n)
删除:
头部删除由于需要将所有元素依次向前移动一个位置因此时间复杂度是 O(n)。尾部删除当删除的元素位于列表末尾时时间复杂度为 O(1)。指定位置删除需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置因此需要移动平均 n/2 个元素时间复杂度为 O(n)。
LinkedList为什么不能实现RandomAccess接口?
RandomAccess 是一个标记接口用来表明实现该接口的类支持随机访问即可以通过索引快速访问元素但是它底层数据结构是链表内存地址不连续只能通过指针来定位不支持随机快速访问
ArrayList和LinkedList的区别
都不保证线程安全数据结构:一个数组一个双向链表插入和删除受元素位置影响是否支持快速随机访问:ArrayList支持内存空间占用:ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间因为要存放直接后继和直接前驱以及数据。
我们在项目中一般是不会使用到 LinkedList 的需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替并且性能通常会更好
ArrayList扩容机制
Set
Comparable 接口和 Comparator区别
Comparable 接口用于定义对象自身的比较逻辑。当一个类实现了 Comparable 接口它就表明该类的对象能够自然地相互比较并且这种比较是基于对象本身的属性Comparator 接口用于定义外部比较逻辑即一个类的对象可以通过外部比较器来决定排序顺序。这使得即使是在不修改对象自身的情况下也可以根据不同的标准对对象进行排序。
无序性和不可重复性
无序性:不是随机性只是没有按照数组索引顺序去添加而是根据哈希值决定不可重复性:就是equals返回false
HashSet和LinkedHasSet和TreeSet的区别?
三者线程不安全底层数据结构不同应用场景不同。HashSet用在不用保证顺序的场景LinkedHashSet(链表哈希表)保证了FIFO(先进先出)TreeSet用于自定义顺序
Queue
Queue和Deque的区别
Queue 是单端队列只能从一端插入元素另一端删除元素实现上一般遵循 先进先出FIFO 规则。
Queue 扩展了 Collection 的接口根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常另一种则会返回特殊值。
Queue 接口抛出异常返回特殊值插入队尾add(E e)offer(E e)删除队首remove()poll()查询队首元素element()peek()
Deque 是双端队列在队列的两端均可以插入或删除元素。
Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法同样根据失败后处理方式的不同分为两类
Deque 接口抛出异常返回特殊值插入队首addFirst(E e)offerFirst(E e)插入队尾addLast(E e)offerLast(E e)删除队首removeFirst()pollFirst()删除队尾removeLast()pollLast()查询队首元素getFirst()peekFirst()查询队尾元素getLast()peekLast()
ArrayDeque和LinkedList的区别
两者都实现了Deque接口具有队列的功能 底层结构:ArrayDeque是可变长数组加双指针另外一个是链表 ArrayDeque 不支持存储 NULL 数据但 LinkedList 支持。 ArrayDeque 是在 JDK1.6 才被引入的而LinkedList 早在 JDK1.2 时就已经存在。 ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容但是每次插入数据时均需要申请新的堆空间均摊性能相比更慢。
从性能的角度上选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外ArrayDeque 也可以用于实现栈。
PriorityQueue
PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的即总是优先级最高的元素先出队。
这里列举其相关的一些要点
PriorityQueue 利用了二叉堆的数据结构来实现的底层使用可变长的数组来存储数据PriorityQueue 通过堆元素的上浮和下沉实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。PriorityQueue 是非线程安全的且不支持存储 NULL 和 non-comparable 的对象。PriorityQueue 默认是小顶堆但可以接收一个 Comparator 作为构造参数从而来自定义元素优先级的先后。
什么是BlockingQueue
BlockingQueue 阻塞队列是一个接口继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞直到有元素还支持如果队列已满一直等到队列可以放入新元素时再放入。
BlockingQueue 常用于生产者-消费者模型中生产者线程会向队列中添加数据而消费者线程会从队列中取出数据进行处理。
ArrayBlockingQueue和LinkedBlockingQueue区别 底层实现ArrayBlockingQueue 基于数组实现而 LinkedBlockingQueue 基于链表实现 是否有界ArrayBlockingQueue 是有界队列必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小默认是Integer.MAX_VALUE也就是无界的。但也可以指定队列大小从而成为有界的。 锁是否分离 ArrayBlockingQueue中的锁是没有分离的即生产和消费用的是同一个锁LinkedBlockingQueue中的锁是分离的即生产用的是putLock消费是takeLock这样可以防止生产者和消费者线程之间的锁争夺。 内存占用ArrayBlockingQueue 需要提前分配数组内存而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着ArrayBlockingQueue 在创建时就会占用一定的内存空间且往往申请的内存比实际所用的内存更大而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间
