黑马程序员技术交流社区

标题: 【成都校区】集合框架底层数据结构总结+关于集合的概念面试题 [打印本页]

作者: meikoYang 时间: 2018-11-20 13:56
标题: 【成都校区】集合框架底层数据结构总结+关于集合的概念面试题
集合框架底层数据结构总结
Collection
1. List
Arraylist： Object数组（查询快，增删慢）
Vector： Object数组（底层也是数组）
LinkedList：双向循环链表（查询慢，增删快）
2. Set
HashSet（无序，不可重复）: 底层采用哈希表结构来保存元素（查询速度非常快）
哈希表：本质：是数组（存储了链表的数组）
LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。--LinkedHashSet:本质是一个有序的HashSet：哈希表+链表
TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树。)
Map
HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap: LinkedHashMap 继承自 HashMap，所以它的底层仍然是由哈希表（数组）和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
HashTable: 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap: 红黑树（自平衡的排序二叉树）

关于集合的概念面试题

1.Java集合类里面最基本的接口有：
1.Collection：代表一组对象，每一个对象都是它的子元素。
2.Set：不包含重复元素的Collection。无序，无索引，不可重复
3.List：有顺序的collection，并且可以包含重复元素。
4.Map：可以把键(key)映射到值(value)的对象，键不能重复。
2.什么是迭代器(Iterator)？
Iterator接口提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素。
3.Enumeration接口和Iterator接口的区别有哪些？
Enumeration速度是Iterator的2倍，同时占用更少的内存。但是，Iterator远远比Enumeration安全，因为其他线程不能够修改正在被iterator遍历的集合里面的对象。同时，Iterator允许调用者删除底层集合里面的元素，这对Enumeration来说是不可能的。
4.ArrayList和LinkedList有什么区别？
ArrayList和LinkedList都实现了List接口，他们有以下的不同点：
1.ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。
2.LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。
3.相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
4.LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。
5 . Java 中的 HashMap 的工作原理是什么？
Java 中的 HashMap 是以键值对(key-value)的形式存储元素的。HashMap 需要一个hash函数，它使用 hashCode()和 equals()方法来向集合/从集合添加和检索元素。当调用 put()方法的时候，HashMap会计算 key 的 hash 值，然后把键值对存储在集合中合适的索引上。如果 key 已经存在了，value 会被更新成新值。HashMap 的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。
6 . Comparable 和Comparator 接口是干什么的？列出它们的区别。
Java 提供了只包含一个 compareTo() 方法的 Comparable 接口。这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明输入对象小于，等于，大于已经存在的对象。
Java 提供了包含 compare() 和 equals() 两个方法的 Comparator 接口。compare() 方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。equals() 方法需要一个对象作为参数，它用来决定输入参数是否和 comparator 相等。只有当输入参数也是一个 comparator 并且输入参数和当前 comparator 的排序结果是相同的时候，这个方法才返回 true。
7 . List、Set、Map 是否继承自 Collection 接口？
List、Set 是，Map 不是。Map 是键值对映射容器，与 List 和 Set 有明显的区别，而 Set 存储的零散的元素且不允许有重复元素，List 是线性结构的容器，适用于按数值索引访问元素的情形。
8 . List、Set、Map 三个接口存储元素时各有什么特点？
1）List 是有序的 Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在 List 中的位置，类似于数组下标）来访问 List 中的元素，这类似于 Java 的数组。
2）Set 是一种不包含重复的元素的 Collection，即任意的两个元素 e1 和 e2 都有e1.equals(e2)=false，Set 最多有一个 null 元素。
3）Map 接口：请注意，Map 没有继承 Collection 接口，Map 提供 key 到 value 的映射，键唯一，值可以重复。
9.你是怎么理解 Java 泛型的？
泛型是 Java SE 1.5的新特性，泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中，分别称为泛型类、泛型接口、泛型方法。
泛型的好处是在编译的时候检查类型安全，并且所有的强制转换都是自动和隐式的，提高代码的重用率。
10.HashMap和HashSet区别？
1. HashMap实现了Map接口，HashSet实现了Set接口
2.HashMap存储键值对，HashSet存储对象
3.HashMap调用put()向map中添加元素，HashSet调用add()像set中添加元素
4.HashMap使用Key计算hashcode,HashSet使用成员计算Hashcode

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2