前言

1. List - 列表

   a. 保证元素的存入顺序，可以存储重复的元素

   b. ArrayList - 顺序表

   i.  底层依靠数组来存储元素
   
   ii. 数组的默认初始容量为10
   
   iii. 在扩容的时候，每次增加当前容量的一半 \-\-- 右移
   
   iv. 增删相对复杂，但是查询相对简单
   
   v.  线程不安全
   

   c. LinkedList - 链表

   i.  底层依靠节点来存储数据
   
   ii. 节点之间通过地址来相互引用
   
   iii. 增删相对简单，但是查询相对复杂
   
   iv. 线程不安全
   

思考：在增删次数和查询次数相差不大的情况下，使用ArrayList/LinkedList? - 建议使用LinkedList --- LinkedList内存空间是不连续的，所以此时对内存的硬性要求会更低一点；如果使用ArrayList，那么要求内存中需要找到一块连续的足够大的空间

List

一、Vector - 向量

1. 是Java中最早的集合

2. 底层依然是依靠数组来存储元素

3. 底层数组的默认初始容量是10

4. 如果不指定容量增量，那么每次扩容都是加上当前的长度，从而使数组的大小变为了原来的2倍

5. 线程安全

二、Stack - 栈

1. 是Vector的子类

2. 满足后进先出(LIFO)的原则

3. 栈顶元素：最后放入栈中的元素栈底元素：最先放入栈中的元素入栈/压栈：将元素放入栈中出栈/弹栈：将元素从栈中取出

4. 底层是依靠数组存储元素 --- 顺序栈

扩展：

1. 如何实现一个链式栈

2. 面试题：如何实现一个最小栈 --- 保证元素的存入顺序，提供一个getMin方法获取这个栈中的最小值

三、Queue - 队列

1. 遵循先进先出(FIFO)的原则

2. 队头元素：最先放入队列中的元素

队尾元素：最后放入队列中的元素

3. Deque：双向队列

Set

一、概述

1. 称之为是一个散列集合

2. 存储的元素是不重复的；如果添加重复的元素，则该元素被舍弃

二、HashSet

1. 存储元素的时候根据元素的哈希码来进行计算和存储的

2. 同一个类的同一对象的哈希码一定是相同的，同一个类的不同对象哈希码一般是不同的

3. 元素个数越多的时候，rehash的效率就要越低

4. 加载因子越小，增加rehash的次数，同时导致空间的浪费；加载因子越大，增加在插入的过程中的比较次数

5. JDK1.8中，当桶中元素个数超过8个的时候，会将当前桶中的链表扭转成一个红黑树；当红黑树中的节点个数不足7个的时候，扭转回链表

三、TreeSet

1. 会对放入其中的元素进行排序

2. 要求放入的元素所对应的类必须实现Comparable接口

3. TreeSet在底层采用的是二叉树结构

4. TreeSet在放入元素的时候实际上会跟元素进行比较，而在比较的时候调用的不是equals而是compareTo

迭代器

1. 迭代器本质上是通过指针的挪动来依次指向每一个元素，然后通过指针指向来获取对应的元素

2. Enumeration是Java中最早的迭代器，但是被Iterator取代

3. 增强for循环本质上是一种迭代遍历，底层用的是迭代器Iterator

4. 需要注意的是Enumeration是通过elements()方法来获取，而elements是

Vector类中的方法，所以只有Vector类调用elements()产生Enumeration对象

5. Iterator对象是通过iterator()方法获取，而iterator是Collection接口中的方法，所以任何一个集合都可以利用iterator()方法来产生Iterator对象

泛型

一、概述

1. 参数化类型，对应的接口ParamerizedType

2. 是JDK1.5的特性之一

3. 用具体类型替换泛型的过程 - 泛型的擦除 - 发生在编译期

4. 泛型的定义格式：<名字>

5. 泛型的上限：? extends 类/接口 -表示传入这个类/接口及其子类/子接口/实现类对象

6. 泛型的下限：? super 类/接口 - 表示传入这个类/接口及其父类/父接口对象

Map<K,V> - 映射

一、概述

1. 是java中映射的顶级接口

2. Map是一个容器，这个容器存储的是键值对

3. 一个映射的完成需要两组值，第一组值称之为key-键，第二组值称之为value-值

4. 键是唯一的，每一个键对应一个值

5. 在映射中，键和值是成对出现，把这种结构称之为叫键值对。所以一个映射实际上是由多个键值对来组成的