第一章 数据结构和算法（主要考察集合）

1.java中常用的数据结构

因为这边讨论的主题是面试，所以数据结构和算法谈到的可能更多的还是基于Collection中相关的容器以及一些容器的操作方法。

• Array
  特点：

  • 支持快速查询（随机访问）
  • 尽量在索引存在语义的情况下使用数组（当索引所占空间太大时，本身数据大小可能都超过元素大小，不适合用索引，比如身份证）
  • 适用于数据个数（数组大小）已经确定，不会更改的情况

  我们在日常工作中可能很少会选择使用数组（Array），最大的原因在于:java中的数组没法动态扩容（add），即数组申明完，大小（size）就确定，没法再增加数组空间。正因为这个原因，才有了ArrayList，关于两者的区别，下面会提到。

• List
  定义：List仅仅是一个接口（Interface），存在于java.util包下，继承了Collection接口

  我们经常用到的ArrayList只是List的一个实现类，本质是一个动态数组;而我们不常用的LinkedList同样是List的一个实现类。

  • List接口中包含了一些关于List的基本操作方法（method），比如：isEmpty()，size（），remove（）等等
  • jdk8中引入了函数式编程之后，在接口中增加了default 修饰方法（默认方法，存在方法体），List接口中就存在默认方法，比如：default void sort（）、default Spliterator<E> spliterator()
    ps：spliterator方法重写了Collection接口中的spliterator方法。

• Map
  定义：Map同样是一个接口，也存在于java.util包下，但Map并不是Collection的子接口

  我们平时使用的HashMap继承自抽象类AbstractMap，而AbstractMap就是Map的实现类；而我们不常用的LinkedHashMap，TreeMap、ConcurrentHashMap本质也都是实现了Map（细节有差异）。

2. 关于数组和List的区别

3.面试官都要问的集合（扩展）