网站导航菜单设计,怎么自己做网站的优化,高端网站设计欣赏,巢湖网站设计前言
本篇主要总结JAVA面试中关于集合相关的高频面试题。本篇的面试题基于网络整理以及自己的总结编辑。在不断的完善补充哦。欢迎小伙伴们在评论区发表留言哦#xff01;
1、基础
1.1、Java 集合框架有哪些#xff1f;
Java 集合框架#xff0c;大家可以看看 《Java 集…前言
本篇主要总结JAVA面试中关于集合相关的高频面试题。本篇的面试题基于网络整理以及自己的总结编辑。在不断的完善补充哦。欢迎小伙伴们在评论区发表留言哦
1、基础
1.1、Java 集合框架有哪些
Java 集合框架大家可以看看 《Java 集合框架》 文章。写的非常详细在这里就不具体说明了
1.2、集合框架的优点
集合框架的优点很多只说一些我们开发中可以直观体验到的
集合框架的部分优点如下
1、降低开发成本与维护成本 让你使用核心集合类降低开发成本而非实现我们自己的集合类。 通过使用 JDK 附带的集合类可以降低代码维护成本。 2、提高代码质量 随着使用经过严格测试的集合框架类代码质量会得到提高。 3、复用性和可操作性
集合框架中的泛型的优点
1、避免了在运行时出现异常 Java5 引入了泛型所有的集合接口和实现都大量地使用它。泛型允许我们为集合提供一个可以容纳的对象类型。因此如果你添加其它类型的任何元素它会在编译时报错。这避免了在运行时出现 ClassCastException因为你将会在编译时得到报错信息。 2、代码整洁 泛型也使得代码整洁我们不需要使用显式转换和 instanceOf 操作符。它也给运行时带来好处因为不会产生类型检查的字节码指令。 1.3、Java 集合框架的基础接口有哪些
Java中集合主要分为两种单列的Collection和双列的Map Collection 为集合层级的根接口。一个集合代表一组对象这些对象即为它的元素。 Collection有两个子接口 1、Set 是一个不能包含重复元素的集合。无序不可重复的接口。 2、List 是一个有序集合可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态变换的数组。 Map 是一个将 key 映射到 value 的对象。一个 Map 不能包含重复的 key每个 key 最多只能映射一个 value 。 一些其它的接口有 Queue、Dequeue、SortedSet、SortedMap 和 ListIterator 。 1.3.1、为何 Collection 不从 Cloneable 和 Serializable 接口继承
Collection 接口指定一组对象对象即为它的元素。 如何维护这些元素由 Collection 的具体实现决定。例如一些如 List 的 Collection 实现允许重复的元素而其它的如 Set 就不允许。很多 Collection 实现有一个公有的 clone 方法。然而把它放到集合的所有实现中也是没有意义的。这是因为 Collection 是一个抽象表现重要的是实现。 1.3.2、为何 Map 接口不继承 Collection 接口 尽管 Map 接口和它的实现也是集合框架的一部分但 Map 不是集合集合也不是 Map。因此Map 继承 Collection 毫无意义反之亦然。如果 Map 继承 Collection 接口那么元素去哪儿Map 包含 key-value 对它提供抽取 key 或 value 列表集合( Collection )的方法但是它不适合“一组对象”规范。 1.3.3、Collection 和 Collections 的区别 Collection 是集合类的上级接口继承与他的接口主要有 Set 和List 。Collections 是针对集合类的一个工具类它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 2、数据结构
2.1、List
ArrayList Object 数组。Vector Object 数组。LinkedList 双向链表(JDK6 之前为循环链表JDK7 取消了循环)。
2.2、Map 2.2.1、HashMap JDK8 之前HashMap 由数组链表组成的数组是HashMap的主体链表则是主要为了解决哈希冲突而存在的“拉链法”解决冲突。JDK8 以后在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为 8 时将链表转化为红黑树以减少搜索时间。 2.2.2、LinkedHashMap LinkedHashMap 继承自 HashMap所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外LinkedHashMap 在上面结构的基础上增加了一条双向链表使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作实现了访问顺序相关逻辑。 2.2.3、Hashtable 数组链表组成的数组是 HashMap 的主体链表则是主要为了解决哈希冲突而存在的。 2.2.4、TreeMap
红黑树自平衡的排序二叉树。
2.3、Set
2.3.1、HashSet 无序唯一基于 HashMap 实现的底层采用 HashMap 来保存元素。 2.3.2、LinkedHashSet LinkedHashSet 继承自 HashSet并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样不过还是有一点点区别的。 2.3.3、TreeSet 有序唯一红黑树(自平衡的排序二叉树)。 2.4、什么是迭代器(Iterator) Iterator 接口提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素但是不可以直接调用集合的 #remove(Object Obj) 方法删除可以通过迭代器的 #remove() 方法删除。 2.5、Iterator 和 ListIterator 的区别是什么 Iterator 可用来遍历 Set 和 List 集合但是 ListIterator 只能用来遍历 List。Iterator 对集合只能是前向遍历ListIterator 既可以前向也可以后向。ListIterator 实现了 Iterator 接口并包含其他的功能。比如增加元素替换元素获取前一个和后一个元素的索引等等。 2.5、快速失败fail-fast和安全失败fail-safe的区别是什么
差别在于 ConcurrentModification 异常 快速失败当你在迭代一个集合的时候如果有另一个线程正在修改你正在访问的那个集合时就会抛出一个 ConcurrentModification 异常。 在 java.util 包下的都是快速失败。安全失败你在迭代的时候会去底层集合做一个拷贝所以你在修改上层集合的时候是不会受影响的不会抛出 ConcurrentModification 异常。在 java.util.concurrent 包下的全是安全失败的。 2.6、如何删除 List 中的某个元素
有两种方式分别如下 方式一使用 Iterator 顺序向下如果找到元素则使用 remove 方法进行移除。 方式二倒序遍历 List 如果找到元素则使用 remove 方法进行移除。 2.7、Enumeration 和 Iterator 接口有什么不同 Enumeration 跟 Iterator 相比较快两倍而且占用更少的内存。Iterator 相对于 Enumeration 更安全因为其他线程不能修改当前迭代器遍历的集合对象。同时Iterators 允许调用者从底层集合中移除元素这些 Enumerations 都没法完成。 2.8、为何 Iterator 接口没有具体的实现 Iterator 接口定义了遍历集合的方法但它的实现则是集合实现类的责任。每个能够返回用于遍历的 Iterator 的集合类都有它自己的 Iterator 实现内部类。 这就允许集合类去选择迭代器是 fail-fast 还是 fail-safe 的。比如ArrayList 迭代器是 fail-fast 的而 CopyOnWriteArrayList 迭代器是 fail-safe 的。 2.9、Comparable 和 Comparator 的区别? Comparable 接口在 java.lang 包下用于当前对象和其它对象的比较所以它有一个 #compareTo(Object obj) 方法用来排序该方法只有一个参数。Comparator 接口在 java.util 包下用于传入的两个对象的比较所以它有一个 #compare(Object obj1, Object obj2) 方法用来排序该方法有两个参数。 2.10、compareTo 方法的返回值表示的意思 大于 0 表示对象大于参数对象。小于 0 表示对象小于参数对象等于 0 表示两者相等。 2.11、如何对 Object 的 List 排序 对 Object[] 数组进行排序时我们可以用 Arrays#sort(...) 方法。对 ListObject 数组进行排序时我们可以用 Collections#sort(...) 方法。 2.12、有哪些关于 Java 集合框架的最佳实践 基于应用的需求来选择使用正确类型的集合这对性能来说是非常重要的。例如如果元素的大小是固定的并且知道优先级我们将会使用一个 Array 而不是 ArrayList 。一些集合类允许我们指定他们的初始容量。因此如果我们知道存储数据的大概数值就可以避免重散列或者大小的调整。总是使用泛型来保证类型安全可靠性和健壮性。同时使用泛型还可以避免运行时的 ClassCastException 异常。在 Map 中使用 JDK 提供的不可变类作为一个 key这样可以避免 hashcode 的实现和我们自定义类的 equals 方法。应该依照接口而不是实现来编程。返回零长度的集合或者数组而不是返回一个 null 这样可以防止底层集合是空的。 3、区别
3.1、List 和 Set 区别
ListSet 都是继承自 Collection 接口。 List 特点元素有放入顺序元素可重复。Set 特点元素无放入顺序元素不可重复重复元素会覆盖掉。 注意元素虽然无放入顺序但是元素在 Set 中的位置是有该元素的 hashcode 决定的其位置其实是固定的。 另外 List 支持 for 循环也就是通过下标来遍历也可以用迭代器但是 Set 只能用迭代因为他无序无法用下标来取得想要的值。 3.2、Set 和 List 对比 Set检索指定的元素效率高删除和插入效率高插入和删除可能会引起元素位置改变。List和数组类似List 可以动态增长查找指定的元素效率低插入删除指定的元素效率低因为可能会引起其他元素位置改变。 当然如果是随机访问指定下标则 List 会快于 Set 。总之什么场景下使用 Set 什么场景下使用 List 还是比较明确的。 3.3、List 和 Map 区别 List 是对象集合允许对象重复。Map 是键值对的集合不允许 key 重复。 3.4、Array 和 ArrayList 有何区别什么时候更适合用 Array Array 可以容纳基本类型和对象而 ArrayList 只能容纳对象。Array 是指定大小的而 ArrayList 大小是固定的可自动扩容。Array 没有提供 ArrayList 那么多功能比如 addAll、removeAll 和 iterator 等。 尽管 ArrayList 明显是更好的选择但也有些时候 Array 比较好用比如下面的三种情况。 如果列表的大小已经指定大部分情况下是存储和遍历它们对于遍历基本数据类型尽管 Collections 使用自动装箱来减轻编码任务在指定大小的基本类型的列表上工作也会变得很慢。如果你要使用多维数组使用 [][] 比 List 会方便。 3.5、ArrayList 与 LinkedList 区别
3.5.1、 ArrayList 优点ArrayList 是实现了基于动态数组的数据结构因为地址连续一旦数据存储好了查询操作效率会比较高在内存里是连着放的。缺点因为地址连续ArrayList 要移动数据所以插入和删除操作效率比较低。 3.5.2、LinkedList 优点LinkedList 基于链表的数据结构地址是任意的所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。缺点因为 LinkedList 要移动指针所以查询操作性能比较低。 3.5.3、 适用场景分析 当需要对数据进行对随机访问的情况下选用 ArrayList 。 当需要对数据进行多次增加删除修改时采用 LinkedList 。 如果容量固定并且只会添加到尾部不会引起扩容优先采用 ArrayList 。 当然绝大数业务的场景下使用 ArrayList 就够了。主要是注意好避免 ArrayList 的扩容以及非顺序的插入。 3.6、ArrayList 是如何扩容的 如果通过无参构造的话初始数组容量为 0 当真正对数组进行添加时才真正分配容量。每次按照 1.5 倍位运算的比率通过 copeOf 的方式扩容。在 JKD6 中实现是如果通过无参构造的话初始数组容量为10每次通过 copeOf 的方式扩容后容量为原来的 1.5 倍。 重点是 1.5 倍扩容这是和 HashMap 2 倍扩容不同的地方。 3.7、ArrayList 集合加入 1 万条数据应该怎么提高效率 ArrayList 的默认初始容量为 10 要插入大量数据的时候需要不断扩容而扩容是非常影响性能的。因此现在明确了 10 万条数据了我们可以直接在初始化的时候就设置 ArrayList 的容量 3.8、ArrayList 与 Vector 区别
ArrayList 和 Vector 都是用数组实现的主要有这么三个区别 Vector 是多线程安全的线程安全就是说多线程访问同一代码不会产生不确定的结果而 ArrayList 不是。这个可以从源码中看出Vector 类中的方法很多有 synchronized 进行修饰这样就导致了 Vector 在效率上无法与 ArrayList 相比。 Vector 是一种老的动态数组是线程同步的效率很低一般不赞成使用。 两个都是采用的线性连续空间存储元素但是当空间不足的时候两个类的增加方式是不同。 Vector 可以设置增长因子而 ArrayList 不可以。 3.8.1、适用场景分析 Vector 是线程同步的所以它也是线程安全的而 ArrayList 是线程无需同步的是不安全的。如果不考虑到线程的安全因素一般用 ArrayList 效率比较高。 实际场景下如果需要多线程访问安全的数组使用 CopyOnWriteArrayList 。 如果集合中的元素的数目大于目前集合数组的长度时在集合中使用数据量比较大的数据用 Vector 有一定的优势。 这种情况下使用 LinkedList 更合适。
3.9、HashMap 和 Hashtable 的区别 HashMap 和 Hashtable 都实现了 Map 接口因此很多特性非常相似。但是他们有以下不同点 HashMap 允许键和值是 null而 Hashtable 不允许键或者值是 null。 Hashtable 是同步的而 HashMap 不是。因此HashMap 更适合于单线程环境而 Hashtable 适合于多线程环境 【重点】1、HashTable 是同步的而 HashMap 是非同步的效率上比 HashTable 要高。也因此HashMap 更适合于单线程环境而 HashTable 适合于多线程环境。 【重点】2、HashTable 中数组默认大小是 11 扩容方法是 old * 2 1 HashMap 默认大小是 16 扩容每次为 2 的指数大小。 Hashtable 是在 Java 1.0 的时候创建的而集合的统一规范命名是在后来的 Java2.0 开始约定的而当时其他一部分集合类的发布构成了新的集合框架。 一般现在不建议用 HashTable 。主要原因是两点 HashTable 是遗留类内部实现很多没优化和冗余。即使在多线程环境下现在也有同步的 ConcurrentHashMap 替代没有必要因为是多线程而用 Hashtable 。 3.10、Hashtable 的 #size() 方法中明明只有一条语句 return count; 为什么还要做同步 同一时间只能有一条线程执行固定类的同步方法但是对于类的非同步方法可以多条线程同时访问。所以这样就有问题了可能线程 A 在执行 Hashtable 的 put 方法添加数据线程 B 则可以正常调用 #size() 方法读取 Hashtable 中当前元素的个数那读取到的值可能不是最新的可能线程 A 添加了完了数据但是没有对 count 线程 B 就已经读取 count 了那么对于线程 B 来说读取到的 count 一定是不准确的。 而给 #size() 方法加了同步之后意味着线程 B 调用 #size() 方法只有在线程 A 调用 put 方法完毕之后才可以调用这样就保证了线程安全性。
3.11、HashSet 和 HashMap 的区别 Set 是线性结构值不能重复。HashSet 是 Set 的 hash 实现HashSet 中值不能重复是用 HashMap 的 key 来实现的。Map 是键值对映射可以空键空值。HashMap 是 Map 的 hash 实现key 的唯一性是通过 key 值 hashcode 的唯一来确定value 值是则是链表结构。因为不同的 key 值可能有相同的 hashcode 所以 value 值需要是链表结构。 他们的共同点都是 hash 算法实现的唯一性他们都不能持有基本类型只能持有对象。 为了更好的性能Netty 自己实现了 key 为基本类型的 HashMap 例如 IntObjectHashMap 3.12、HashSet 和 TreeSet 的区别 HashSet 是用一个 hash 表来实现的因此它的元素是无序的。添加删除和 HashSet 包括的方法的持续时间复杂度是 O(1) 。TreeSet 是用一个树形结构实现的因此它是有序的。添加删除和 TreeSet 包含的方法的持续时间复杂度是 O(logn) 。 3.13、如何决定选用 HashMap 还是 TreeMap 对于在 Map 中插入、删除和定位元素这类操作HashMap 是最好的选择。然而假如你需要对一个有序的 key 集合进行遍历 TreeMap 是更好的选择。 基于你的 collection 的大小也许向 HashMap 中添加元素会更快再将 HashMap 换为 TreeMap 进行有序 key 的遍历。
3.14、HashMap 和 ConcurrentHashMap 的区别
ConcurrentHashMap 是线程安全的 HashMap 的实现。主要区别如下 ConcurrentHashMap 对整个桶数组进行了分割分段(Segment)然后在每一个分段上都用 lock 锁进行保护相对 于Hashtable 的 syn 关键字锁的粒度更精细了一些并发性能更好。而 HashMap 没有锁机制不是线程安全的。 JDK8 之后ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。 HashMap 的键值对允许有 null 但是 ConCurrentHashMap 都不允许。 3.15、队列和栈是什么列出它们的区别
栈和队列两者都被用来预存储数据。 java.util.Queue 是一个接口它的实现类在Java并发包中。 队列允许先进先出FIFO检索元素但并非总是这样。Deque 接口允许从两端检索元素。栈与队列很相似但它允许对元素进行后进先出LIFO进行检索。 Stack 是一个扩展自 Vector 的类而 Queue 是一个接口。 4、原理
4.1、HashMap 的工作原理是什么 HashMap是基于hashing的原理 HashMap是以键值对(key-value)的形式存储元素的。我们使用put(key, value)存储对象到HashMap中使用get(key)从HashMap中获取对象。当调用put()方法的时候HashMap会计算key的hash值然后把键值对存储在集合中合适的索引上。如果key已经存在了value会被更新成新值。 HashMap 是基于 hashing 的原理。 4.2、当两个对象的 hashCode 相同会发生什么 因为 hashcode 相同所以它们的 bucket 位置相同“碰撞”会发生。 因为 HashMap 使用链表存储对象这个 Entry包含有键值对的 Map.Entry 对象会存储在链表中。 4.3、Hash碰撞的解决方案 开放定址法发生冲突继续寻找下一块未被占用的存储地址。如线性探测、平方探测、随机探测。再hash也就是有多个hash函数当一个函数计算产生冲突之后再用另外一个函数计算。公共溢出区把产生冲突的元素放在一个公共的溢出区里面链地址法采用数组链表的结构。HashMap采用的就是这种方式HashMap产生冲突的时候元素是插在链表的头部还是尾部为什么会插在链的头部因为这样的话不需要把指针移动到最后面一个元素进行插入操作效率更高。 4.4、hashCode 和 equals 方法有何重要性
HashMap 使用 key 对象的 #hashCode() 和 #equals(Object obj) 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候这些方法也会被用到。 如果这两个方法没有被正确地实现在这种情况下两个不同 Key 也许会产生相同的 #hashCode() 和 #equals(Object obj) 输出HashMap 将会认为它们是相同的然后覆盖它们而非把它们存储到不同的地方。 同样的所有不允许存储重复数据的集合类都使用 #hashCode() 和 #equals(Object obj) 去查找重复所以正确实现它们非常重要。#hashCode() 和 #equals(Object obj) 方法的实现应该遵循以下规则 如果 o1.equals(o2) 那么 o1.hashCode() o2.hashCode() 总是为 true 的。如果 o1.hashCode() o2.hashCode() 并不意味 o1.equals(o2) 会为 true 。 4.5、HashMap 默认容量是多少 默认容量都是 16 负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容最小的可能性是16 * 0.75 12一般为原内存的 2 倍。 4.6、HashMap默认容量为什么是16 为了数据的均匀分布减少哈希碰撞。因为确定数组位置是用的位运算若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。 4.7、HashMap 的长度为什么是 2 的幂次方 为了能让 HashMap 存取高效尽量较少碰撞也就是要尽量把数据分配均匀每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢我们首先可能会想到采用 % 取余的操作来实现。但是重点来了 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与()操作也就是说 hash % length hash (length - 1) 的前提是 length 是 2 的 n 次方。并且采用二进制位操作 相对于 % 能够提高运算效率 这就解释了 HashMap 的长度为什么是 2 的幂次方。
4.8、有哪些顺序的 HashMap 实现类 LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序。TreeMap 是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。 4.9、HashSet 的工作原理是什么
HashSet 是构建在 HashMap 之上的 Set hashing 实现类。让我们直接撸下源码代码如下 private transient HashMapE,Object map;private static final Object PRESENT new Object();map 属性当我们创建一个 HashMap 对象时其内部也会创建一个 map 对象。后续 HashSet 所有的操作实际都是基于这个 map 之上的封装。 PRESENT 静态属性所有 map 中 KEY 对应的值都是它避免重复创建。 OK 再来看一眼 add 方法代码如下 public boolean add(E e) {return map.put(e, PRESENT) null;
}4.10、HashSet 如何检查重复
当你把对象加入 HashSet 时HashSet会先计算对象的hashcode值来判断对象加入的位置同时也会与其他加入的对象的hashcode值作比较。 如果没有相符的 hashcode HashSet会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象这时会调用 equals 方法来检查 hashcode 相等的对象是否真的相同。 如果两者相同HashSet 就不会让加入操作成功。如果两者不同HashSet 就会让加入操作成功。 总结
八股文总结是一个漫长积累的过程欢迎各位小伙伴在评论区留言哦
