面试必备(集合)
Java 中怎么打印数组?
你可以使用 Arrays.toString() 和 Arrays.deepToString() 方法来打印数组。由 于数组没有实现 toString() 方法,所以如果将数组传递给 System.out.println() 方法,将无法打印出数组的内容,但是 Arrays.toString() 可以打印每个元素。
说出几点 Java 中使用 Collections 的最佳实践
这是我在使用 Java 中 Collectionc 类的一些最佳实践:
- 使用正确的集合类,例如,如果不需要同步列表,使用 ArrayList 而不是 Vector。
- 优先使用并发集合,而不是对集合进行同步。并发集合提供更好的可扩展性。
- 使用接口代表和访问集合,如使用 List 存储 ArrayList,使用 Map 存储 HashMap 等等。
- 使用迭代器来循环集合。
- 使用集合的时候使用泛型。
用哪两种方式来实现集合的排序?
你可以使用有序集合,如 TreeSet 或 TreeMap,你也可以使用有顺序的的集合, 如 list,然后通过 Collections.sort() 来排序。
Array 和 ArrayList 有何区别?
- 定义一个 Array 时,必须指定数组的数据类型及数组长度,即数组中存放的元素个数固定并且类型相同。
- ArrayList 是动态数组,长度动态可变,会自动扩容。不使用泛型的时候,可以添加不同类型元素。
Arraylist与LinkedList区别
可以从它们的底层数据结构、效率、开销进行阐述哈
- ArrayList是数组的数据结构,LinkedList是链表的数据结构。
- 随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而ArrayList是基于索引(index)的数据结构,可以直接映射到。
- 插入、删除数据时,LinkedList的效率比较高,因为ArrayList要移动数据。
- LinkedList比ArrayList开销更大,因为LinkedList的节点除了存储数据,还需要存储引用。
List、Map、Set 三个接口存取元素时,各有什么特点?
List 以特定索引来存取元素,可以有重复元素。
Set 不能存放重复元素(用对象的 equals()方法来区分元素是否重复)。
Map 保存键值对(key-value pair)映射, 映射关系可以是一对一或多对一。
Set 和 Map 容器都有基于哈希存储和排序树的 两种实现版本,基于哈希存储的版本理论存取时间复杂度为 O(1),而基于排序树 版本的实现在插入或删除元素时会按照元素或元素的键(key)构成排序树从而达 到排序和去重的效果。
List、Set、Map 是否继承自 Collection 接口?
List、Set 是,Map 不是。
Map 是键值对映射容器,与 List 和 Set 有明显的区别, 而 Set 存储的零散的元素且不允许有重复元素(数学中的集合也是如此),List 是线性结构的容器,适用于按数值索引访问元素的情形。
Collection 和 Collections 的区别?
Collection 是一个接口,它是 Set、List 等容器的父接口;Collections 是个一个 工具类,提供了一系列的静态方法来辅助容器操作,这些方法包括对容器的搜索、 排序、线程安全化等等。
HashMap原理,java8做了什么改变
- HashMap是以键值对存储数据的集合容器
- HashMap是非线性安全的。
- HashMap底层数据结构:数组+(链表、红黑树),jdk8之前是用数组+链表的方式实现,jdk8引进了红黑树
- Hashmap数组的默认初始长度是16,key和value都允许null的存在
- HashMap的内部实现数组是Node[]数组,上面存放的是key-value键值对的节点。HashMap通过put和get方法存储和获取。
- HashMap的put方法,首先计算key的hashcode值,定位到对应的数组索引,然后再在该索引的单向链表上进行循环遍历,用equals比较key是否存在,如果存在则用新的value覆盖原值,如果没有则向后追加。
- jdk8中put方法:先判断Hashmap是否为空,为空就扩容,不为空计算出key的hash值i,然后看table[i]是否为空,为空就直接插入,不为空判断当前位置的key和table[i]是否相同,相同就覆盖,不相同就查看table[i]是否是红黑树节点,如果是的话就用红黑树直接插入键值对,如果不是开始遍历链表插入,如果遇到重复值就覆盖,否则直接插入,如果链表长度大于8,转为红黑树结构,执行完成后看size是否大于阈值threshold,大于就扩容,否则直接结束。
- Hashmap解决hash冲突,使用的是链地址法,即数组+链表的形式来解决。put执行首先判断table[i]位置,如果为空就直接插入,不为空判断和当前值是否相等,相等就覆盖,如果不相等的话,判断是否是红黑树节点,如果不是,就从table[i]位置开始遍历链表,相等覆盖,不相等插入。
- HashMap的get方法就是计算出要获取元素的hash值,去对应位置获取即可。
- HashMap的扩容机制,Hashmap的扩容中主要进行两步,第一步把数组长度变为原来的两倍,第二部把旧数组的元素重新计算hash插入到新数组中,jdk8时,不用重新计算hash,只用看看原来的hash值新增的一位是零还是1,如果是1这个元素在新数组中的位置,是原数组的位置加原数组长度,如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法,采用头插法,把旧数组的元素插入到新数组中。
- HashMap大小为什么是2的幂次方?效率高+空间分布均匀
List 和 Set,Map 的区别
- List 以索引来存取元素,有序的,元素是允许重复的,可以插入多个null。
- Set 不能存放重复元素,无序的,只允许一个null
- Map 保存键值对映射,映射关系可以一对一、多对一
- List 有基于数组、链表实现两种方式
- Set、Map 容器有基于哈希存储和红黑树两种方式实现
- Set 基于 Map 实现,Set 里的元素值就是 Map的键值
poll() 方法和 remove() 方法的区别?
poll() 和 remove() 都是从队列中取出一个元素,但是 poll() 在获取元素失败 的时候会返回空,但是 remove() 失败的时候会抛出异常。
HashMap,HashTable,ConcurrentHash的共同点和区别
HashMap
- 底层由链表+数组+红黑树实现
- 可以存储null键和null值
- 线性不安全
- 初始容量为16,扩容每次都是2的n次幂
- 加载因子为0.75,当Map中元素总数超过Entry数组的0.75,触发扩容操作.
- 并发情况下,HashMap进行put操作会引起死循环,导致CPU利用率接近100%
- HashMap是对Map接口的实现
HashTable
- HashTable的底层也是由链表+数组+红黑树实现。
- 无论key还是value都不能为null
- 它是线性安全的,使用了synchronized关键字。
- HashTable实现了Map接口和Dictionary抽象类
- Hashtable初始容量为11
ConcurrentHashMap
- ConcurrentHashMap的底层是数组+链表+红黑树
- 不能存储null键和值
- ConcurrentHashMap是线程安全的
- ConcurrentHashMap使用锁分段技术确保线性安全
- JDK8为何又放弃分段锁,是因为多个分段锁浪费内存空间,竞争同一个锁的概率非常小,分段锁反而会造成效率低。
写一段代码在遍历 ArrayList 时移除一个元素
因为foreach删除会导致快速失败问题,fori顺序遍历会导致重复元素没删除,所以正确解法如下:
第一种遍历,倒叙遍历删除
1 | for(int i=list.size()-1; i>-1; i--){ |
第二种,迭代器删除
1 | Iterator itr = list.iterator();while(itr.hasNext()) { |
HashMap 的扩容过程
Hashmap的扩容:
- 第一步把数组长度变为原来的两倍,
- 第二步把旧数组的元素重新计算hash插入到新数组中。
- jdk8时,不用重新计算hash,只用看看原来的hash值新增的一位是零还是1,如果是1这个元素在新数组中的位置,是原数组的位置加原数组长度,如果是零就插入到原数组中。扩容过程第二步一个非常重要的方法是transfer方法,采用头插法,把旧数组的元素插入到新数组中。
HashMap 是线程安全的吗,为什么不是线程安全的?死循环问题?
不是线性安全的。
并发的情况下,扩容可能导致死循环问题。
哪些集合类是线程安全的?哪些不安全?
线性安全的
- Vector:比Arraylist多了个同步化机制。
- Hashtable:比Hashmap多了个线程安全。
- ConcurrentHashMap:是一种高效但是线程安全的集合。
- Stack:栈,也是线程安全的,继承于Vector。
线性不安全的
- Hashmap
- Arraylist
- LinkedList
- HashSet
- TreeSet
- TreeMap
Collection与Collections的区别是什么?
- Collection是Java集合框架中的基本接口,如List接口也是继承于它
1 | public interface List<E> extends Collection<E> { |
- Collections是Java集合框架提供的一个工具类,其中包含了大量用于操作或返回集合的静态方法。如下:
1 | public static <T extends Comparable<? super T>> void sort(List<T> list) { |
迭代器 Iterator 是什么?怎么用,有什么特点?
1 | public interface Collection<E> extends Iterable<E> { |
方法如下:
1 | next() 方法获得集合中的下一个元素 |
Iterator 主要是用来遍历集合用的,它的特点是更加安全,因为它可以确保,在当前遍历的集合元素被更改的时候,就会抛出 ConcurrentModificationException 异常。
使用demo如下:[动画表情]
1 | List<String> list = new ArrayList<>(); |
Iterator 和 ListIterator 有什么区别?
- ListIterator 比 Iterator有更多的方法。
- ListIterator只能用于遍历List及其子类,Iterator可用来遍历所有集合,
- ListIterator遍历可以是逆向的,因为有previous()和hasPrevious()方法,而Iterator不可以。
- ListIterator有add()方法,可以向List添加对象,而Iterator却不能。
- ListIterator可以定位当前的索引位置,因为有nextIndex()和previousIndex()方法,而Iterator不可以。
- ListIterator可以实现对象的修改,set()方法可以实现。Iierator仅能遍历,不能修改哦。