线性表List

(插入顺序和遍历顺序是否一致，有没有下标)

1. 有序列表：有序 长度固定 数据位置不变 代表：数组

2. 顺序存储：有序 长度可变 数据位置可变 数据之间是挨着存 插入和删除的效率低 查询的效率高

3. 链式存储(链表)：有序 长度可变 数据位置可变 见缝插针 插入和删除的效率高 查询的效率低

散列表

1. hashtable 哈希表

2. 新华字典（目录+内容）

3. 散列表=目录（顺序存储）+内容（链表）

4. 无序

5. 长度可变

6. 数据位置可变

7. 插入和删除的效率高 查询的效率高

Java集合概念

1. 数据的集合 Java语言专门提供了一堆能存很多数据的类，叫集合类

2. 集合类可以称之为超级数组：

   • 长度可以动态增长

   • 一个集合中可以存任意类型的数据

3. API结构图（重点）

   • 分两大帮派：Collection（单值集合） Map（双值集合）

   • Collection又分为两个帮派：List（有序+可重复）和Set（无序+唯一）

Collection

1. 单列/单值集合

2. 它是一个接口

3. List和Set继承了Collection接口，List接口加入了一些独有方法，而Set接口没有

List

1. 它是一个接口

2. 特点：有序（插入顺序和遍历顺序一致，有下标）+可重复

3. Vector类/ArrayList类/linkedList类实现了List接口

• List接口中的方法

  boolean contains(Object o)继承自Collection

  如果要判断o在当前集合中是否存在 在自定义类时一定要重写equals方法

  存储（添加）

  boolean add(Object o)   继承自Collectionvoid add (int index，Object o)     加塞儿专用

  替换

  set(int index，Object o)

  删除

  remove(Object o)  继承自Collectionremove(int index)void clear()  继承自Collection

  判断

  boolean contains(Object o)   继承自Collection    思考：内部怎么实现？boolean isEmpty()   继承自Collection

  获取

  int  capacity()   集合的容量int size()   继承自Collection    集合中存了多少个数据    相当于数组.lengthObject get(int index)    相当于arr[i]

  举例：

  Vector a=new Vector();a.add("aaa");a.add(100);a.add(99.99);System.out.println(a);//替换a.set(1, 521);System.out.println(a);//删除//a.remove(2);//a.remove("aaa");//a.clear();//判断a.contains(521);System.out.println(a.contains(521));System.out.println(a.isEmpty());//获取int k1=a.size();System.out.println(k1);

Vector类

Vector（向量列表）：底层数据结构是动态的数组结构，线程安全，无论增删还是查询都非常慢(多线程环境)。默认初始容量为10，增量为10。

1. 构造方法：

   public Vector()public Vector(int initialCapacity)public Vector(int initialCapacity,int capacityIncrement)

2. 特点

   • 数据结构：动态的数组结构（顺序存储）
   • 线程：保证线程安全
   • 效率：增删慢，查询快
   • 默认初始容量为10，增量为10
   • 有序的
   • 构造方法：无参构造
   • 功能方法

linkedList（链式列表）

底层是链表数据结构，线程不安全，对元素的增删的操作效率很高，随机查询的效率低(因为要移动指针寻址)。默认初始容量为0，增量不明确。

• 构造方法

  public linkedList()

• 独有方法：

  public void addFirst(Object e)   相当于add(0, e)public void addLast(Object e)   相当于add(e)public Object getFirst()  相当于get(0)public Object getLast()  相当于get(al.size()-1)public Object removeFirst()   相当于remove(0)public Object removeLast()   相当于remove(al.size()-1) 

ArrayList类（重点）

ArrayList（线性列表）：底层数据结构是动态的数组结构，线程不安全，增删的效率很慢(因为要移动数据)，但是随机查询的效率很高。默认初始容量为10，增量未指定（经调试发现：原容量的50%）。

构造方法：public ArrayList()public ArrayList(int initialCapacity)

• 数据结构：动态的数组结构（顺序存储）
• 线程：不保证线程安全
• 效率：增删慢，查询快
• 默认初始容量为10，增量未指定（经调试发现：原容量的50%）
• 有序的
• 构造方法：无参构造
• 功能方法

linkedList类

1. 数据结构：链表
2. 线程：不保证线程安全
3. 效率：增删快，查询慢
4. 默认初始容量为0，增量不明确
5. 有序的
6. 构造方法：无参构造
7. 功能方法
8. 独有方法

会使用泛型（重点）

1. 集合中可以存任意类型的数据，貌似强大，存的时候很爽，取得时候不知道该转换为什么类型，叫类型安全问题
2. 泛型的作用：解决线程安全问题 怎么解决：限制集合只能存一种数据类型
3. 泛型的语法：ArrayList al=new ArrayList();
4. 泛型技术是JDK5才有的
5. 泛型只支持引用数据类型（基本数据类型要使用包装类）
6. JDK7提供了一种简化的写法：菱形写法
7. Java中所有的集合都支持泛型，使用泛型后，就不存在类型安全问题了

泛型的底层实现原理（了解）

1. 让参数或返回值的类型动态可变
2. 自定义泛型方法
3. 自定义泛型类
4. 自定义泛型接口

泛型的技术实现细节（考试/面试）

1. JDK5加入泛型技术时，按说应该升级改造JVM
2. 升级改造JVM的成本较高
3. SUN工程师打起了编译器的主意
4. 编译器在编译时需要检查各项语法
5. SUN工程师在编译器中加入一条针对泛型的语法检查，编译通过后，编译器把字节码文件中凡是泛型的代码删掉
6. Java语言是伪泛型

Set集合概述

1. List Set都是集成了Collection接口的接口
2. Set并没有加入独有方法，Set接口中的方法全部继承自Collection
3. Set集合：无序+唯一 没有下标
4. Set集合没有带有下标的方法

HashSet类（重点）

• 数据结构：散列表（目录+内容）

• 效率：增删和查询都快

• 初始容量：默认初始容量是16，加载因子是0.75

• 线程：不保证线程安全

• 构造方法：无参

• 功能方法

• 无序（插入顺序和遍历顺序不一定一致，没有下标）

• 唯一：我们自定义类时必须重写equals和hashCode方法，不然虽然不会报错，但是会重复添加 先拿着hashCode比内容，如果哈希值不一样就直接添加到集合中；如果哈希值一样，再调用equals进行内容判断

• 构造方法：

  HashSet()无参构造HashSet(int initialCapacity)指定初始容量，默认加载因子为0.75（也就是百分之75）HashSet(int initialCapacity,float loadFactor)指定初始容量，指定加载因子。

linkedHashSet类（了解即可）

• 构造方法

  linkedHashSet()无参构造初始容量16，加载因子默认0.75linkedHashSet(int initialCapacity)指定初始容量，默认加载因子为0.75linkedHashSet(int initialCapacity, float loadFactor)构造一个带有指定初始容量和加载因子的新空链接。

• 数据结构：散列表（目录+内容）+链表（记录了插入的顺序）

• 效率：增删和查询都快

• 初始容量：默认初始容量是16，加载因子是0.75

• 线程：不保证线程安全

• 构造方法：无参

• 功能方法

• 无序（插入顺序和遍历顺序一致，没有下标）

• 唯一

• 该类继承了HashSet类

Map 双值/双列集合（键值对（Entry））

• Map一次可以存两个数据，一个叫键（key），一个叫值（value），这两个数据是一对儿， 叫键值对（Entry）

• 键和值可以是任意类型，Map集合也是支持泛型的

• 在一个Map集合中，键不允许重复，值允许重复，如果键重复，值将会覆盖之前的值

• 无序的（插入顺序和遍历顺序不一定一致，没有下标）

HashMap类（重点）

• 数据结构:散列表 (目录+内容)

• 效率: 增删和查询都快

• 初始容量: 默认初始容量是 16，加载因子是 0.75

• 线程: 不保证线程安全

• 构造方法: 无参

• 功能方法

• 无序(插入顺序和遍历顺序不一定一致,没有下标)

• 唯一(键不允许重复)

• Map集合无法直接遍历

• 如果键是Integer类型，会按照顺序排

• 构造方法

  HashMap()无参构造，默认初始容量16，加载因子0.75HashMap(int initialCapacity)构造一个带指定初始容量和默认加载因子（0.75）的空HashMapHashMap(int initialCapacity)构造一个带指定初始容量和指定加载因子的空HashMap

linkedHashMap类（了解）

• 数据结构：散列表（目录+内容）+链表（记录了插入顺序）

• 效率：增删和查询都快

• 初始容量：默认初始容量是16，加载因子是0.75

• 线程：不保证线程安全

• 构造方法：无参

• 功能方法

• 无序（插入顺序和遍历顺序一致，没有下标）

• 唯一（键不允许重复）

• 该类继承了HashMap类

• 构造方法

  linkedHashMap()构造一个初始容量16，加载因子0.75的空集合linkedHashMap(int initialCapacity)构造一个指定初始容量，加载因子默认0.75的空集合linkedHashMap(int initialCapacity,float loadFactor)构造一个指定初始容量，指定加载因子的空集合linkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)构造一个带有指定初始容量、加载因子、排序模式的空集合