数据结构复习1

1、什么是集合？

就是一组数据的集合体，就像篮子装着苹果、香蕉等等，这些“水果”就代表数据，“篮子”就是这个集合。

集合的特点：

集合用于存储对象。

对象是确定的个数可以用数组，如果不确定可以用集合，因为集合的长度是可以变化的。

集合和数组的区别：

数组的长度是固定的，集合的长度是可变的。

数组可以存储基本数据类型，也可以存储引用数据类型，而集合只能存储引用数据类型。

2、什么是集合框架？

就像是一个“工具箱”，里面装满了这种“容器”，这些“容器”都有自己的用途和特点。

（List、Set、Map）

3、什么是接口？

就是一种规范，规定了某个对象必须实现哪些方法，但不必关注如何具体实现，就像是去餐馆里点菜，只要点想要的菜，不需要知道菜是具体怎么做的。

4、什么是算法？

在一个实现了集合框架的接口的对象上完成某种有用的计算方法。

5、什么是数据结构？

就是容器中存储数据的方式。

使用一个体系的原则：参阅顶层内容，建立底层对象。

6、使用集合框架的好处

容量自增长。

提供了高性能的数据结构和算法。

允许不同API之间互相操作。

可以方便地扩展或改写集合。

通过使用JDK（Java开发工具包）自带的集合类，可以代码维护和学习新API的成本。

7、常用的集合类有哪些？

常用的集合类主要分为两大类：实现Collection接口的集合类和实现Map接口的映射类。

Collection接口的子接口包括：List接口和Set接口。

List接口的实现类主要有：ArrayList、LinkedList、Vector等等。

Set接口的实现类主要有：HashSet、LinkedHashSet、TreeSet等等。

Map接口的实现类主要有：HashMap、LinkedHashMap、TreeMap等等。

8、List、Set、Map的区别

List：一个有序容器，可以存储重复元素，可以插入多个null元素，元素都有索引。

Set：一个无序容器，不可以存储重复元素，只允许插入一个null元素，必须确保元素的唯一性。

Map：是一个键值对集合，存储键和值之间的映射。Key无序，唯一；value不要求有序，可以不唯一。

9、集合框架底层数据结构

List接口：

ArrayList：Object数组，当添加或删除元素时，如果数组满了或者有空余空间，ArrayList会自动调整数组大小。

Vector：Object数组，线程安全。

LinkedList：双向链表，在开始和结束处添加或删除元素会非常快。

Set接口：

HashSet：无序、唯一，基于HashMap实现的，底层采用HashMap实现。

LinkedHashSet：和HashSet差不多，但它还有一个双向链表用来记录元素的插入顺序，所以遍历LinkedHashSet时，元素会按照被添加的顺序出现。

TreeSet：有序、唯一，通过红黑树来实现的（平衡二叉树）。

Map接口：

HashMap：在JDK1.8之前，它主要是由数组和链表组成的，数组是HashMap的主体，链表则主要是为了解决哈希冲突而存在的。从JDK1.8开始，如果链表太长（默认超过8个元素），就会转换为红黑树来优化性能。

LinkedHashMap：增加了一条双向链表，使得可以保持键值对的插入顺序。

HashTable：和HashMap类似，线程安全。

TreeMap：基于红黑树实现的。

10、哪些集合类是线程安全的？

Vector、Stack（堆栈类，先进后出）、HashTable、Enumeration（枚举，相当于迭代器）