本章目标：

1. 集合层次结构

2. Collection接口

3. List


ArrayList
LinkedList
Vector

4. Set

  1. HashSet<br />    TreeSet<br />    LinkedHashSet

5. Map

HashMap
TreeMap
LinkedHashMap

6. 迭代器

7. 自定义集合

8. 扩展内容

本章内容

一、层次结构

1. Collection

  • List
    • ArrayList
    • LinkedList
    • Vector

  • Set

    • HashSet
      • LinkedHashSet
    • TreeSet

      2. Map

  • HashMap

  • TreeMap
  • Hashtable

二、Collection

1.存放若干个独立元素

•boolean add(Object element)

•boolean remove(Object element)

2.Collection 接口还支持查询操作：

•int size()

•boolean isEmpty()

•boolean contains(Object element)

•Iterator iterator()

3.组操作 ：

Collection 接口支持的其它操作，要么是作用于元素组的任务，要么是同时作用于整个集合的任务。

•boolean containsAll(Collection collection)

•boolean addAll(Collection collection)

•void clear()

•void removeAll(Collection collection)

•void retainAll(Collection collection)

三、List

1.数据结构：

2.逻辑结构：线性 树 图

3.存储结构：线性 链式

List: 有序集合，可以放入重复（equals进行判断）元素，会按照存入的顺序给每个元素编号，遍历的时候也可以依靠编号进行遍历

  2. 1.  `void add(int index,  Object element):  在指定位置index上添加元素element`
  4. 3.  `boolean addAll(int index,  Collection c):  将集合c的所有元素添加到指定位置index`
  6. 5.  `Object get(int index):  返回List中指定位置的元素`
  8. 7.  `int indexOf(Object o):  返回第一个出现元素o的位置，否则返回-1`
  10. 9.  `int lastIndexOf(Object o)  ：返回最后一个出现元素o的位置，否则返回-1`
  12. 11.  `Object remove(int index)　：删除指定位置上的元素`
  14. 13.  `Object set(int index,  Object element)  ：用元素element取代位置index上的元素，并且返回旧的元素`

注意：比较对象是按照equals来进行比较的

1.ArrayList

  • 常用API
  • 底层：底层是一个Object类型的数组，初始的默认长度10，也可以指定长度，初始长度如果满了，底层进行自动扩容，扩容为原来的1.5倍oldCapacity + (oldCapacity >> 1)。10—->15—->22，如果对集合中的元素个数可以预估，那么建议预先指定一个合适的初始容量,可以减少扩容的次数
    new ArrayList(20);
    线程不安全，性能高。
  • 优点：查找效率高，向末尾添加、删除元素也可以

  • 缺点：增加 、删除牵扯到数组的扩容和移动，效率低

    2.LinkedList：

  • 常用API：addFirst addLast

  • 底层是一个链表（双向）结构，添加的元素和前后元素的地址信息会封装成一个Node类型的对象，放到集合中，不是线性存储，内存中是链式存储，不连续的空间。
  • 优点：增加、删除效率高

  • 缺点：查找效率低

    3.Vector

  • 常用API
    构造方法
    Vector()
    Vector(初始容量)
    Vector((初始容量，扩容数量)
    向向量序列中添加元素
    addElement(Object obj)
    insertElementAt(Object obj， int index)
    修改或删除向量序列中的元素
    Void setElementAt(Object obj， int index)
    boolean removeElement (Object obj)
    Void removeElementAt (int index)
    Void removeAllElements ()
    查找向量序列中的元素
    Object elementAt(int index)
    boolean contains (Object obj)
    int indexOf (Object obj， int start_index)
    int lastIndexOf (Object obj， int start_index)

  • 底层是一个Object类型的数组，初始的默认长度为10，默认扩容的时候扩容为原来的2倍 ,如果自己指定扩容的长度，那么就是就容量加指定的，如果没有指定，就是旧容量的2倍。

  • 线程安全，性能低

    4.对照区别

  • ArrayList和linkedList的区别

  • ArrayList和Vector的区别

四、Set

set 无序集合，存入的元素在逻辑上没有位置编号，也不能依靠编号去操作元素

1.HashSet

  • 常用API:clear isEmpty reomve size

  • 特点

    • 输出是无序的：和存入顺序不一定一致
    • 不能放入重复元素：两个对象用equals方法比较返回true,并且两个对象拥有相同的哈希码,也就是hashCode方法要有相同的返回值
    • 可以放入null元素
    • HashSet的典型应用场景就是去除重复元素

  • 底层存储结构：
    HashSet的底层是一个HashMap,只是将HashMap中的值设置为一 个常量，用所有的键组成了一个HashSet

    2. LinkedHashSet:

底层有一个链表结构，按照添加顺序维护顺序

3.TreeSet

  • 特点
    • 输出有序
    • 不能放入null对象
    • 不能放入重复对象（比较对象的大小，如CompareTo方法的返回值为0
    • TreeSet的典型应用场景就是自带排序功能
  • 自然排序
    要求元素对应的类型实现Comparable接口，调用Treeset的无参数构造的时候采用自然排序的方式
  • 比较器排序(Comparator)：
    单独实现一个比较器类，比较器类实现Comparator接口，重写compare（o1,o2）方法.然后创建Treeset的时候将比较器作为构造方法的参数传入，不要求元素类型实现Comparable接口
  • 判断重复元素的依据
    compareTo或者compare方法的返回值进行比较排序，方法如果返回0，认为两个对象是相等的，不会重复存储。
  • 存储结构：TreeSet**的底层是用TreeMap进行实现，TreeMap中所有的键构成了TreeSet.、

五、Map

map存放键值对
常用的API

  • Put（key,value）
  • get(key)
  • keySet()
  • values()
  • entrySet()
  • containsKey(key):注意查找依据
  • containsValue(value)::注意查找依据
  • size()
  • remove(key)
  • clear

1. HashMap


特点
可以放入NULL值，NULL键
不能放入重复键（依靠equals和hashcode进行判断）
键是无序的（所有的键构成了一个hashSet）
底层结构：数组加链表|数组加红黑树

2.TreeMap


  • 按照键进行排序（无参数构造TreeMap(),自然排序，TreeMap(Comparator)，按照自定义比较器进行排序）
  • 不能放入null键，可以放入null值
  • 键不能重复（判断的依据是比较的大小如果相同，调用compareTo或者compare()方法返回值如果为0，就认为是相同的对象） 底层为树结构。