概述

集合是java中提供的一种容器，可以用来存储多个数据，集合框架主要java.util 包中，存储结构可以分为两大类，分别是单列集合java.util.Collection和双列集合java.util.Map。
Collection是单列集合类的根接口，用于存储一系列符合某种规则的元素，它有两个重要的子接口，分别是java.util.List和java.util.Set。其中，List的特点是元素有序、元素可重复。Set的特点是元素无序，而且不可重复。List接口的主要实现类有java.util.ArrayList和java.util.LinkedList，Set接口的主要实现类有java.util.HashSet和java.util.TreeSet。
image.png
集合和数组的区别
(1)长度：数组的长度是不变的，集合的长度是可变的
(2)存储内容：数组存放的是基本数据类型和引用类型，集合只能存储引用类型。
(3)存储类型：数组存放的类型是相同，而集合可以实现不同类型。

Collection接口方法

Collection是所有单列集合类的父接口，因此在Collection中定义了单列集合(List和Set)通用的方法，方法如下：

  1. boolean add(E e)// 添加元素
  2. boolean addAll(Collection c)//将指定 collection 中的所有元素都添加到此 collection 中
  3. void clear()// 清空元素
  4. boolean contains(E e)//如果 包含指定的元素，则返回 true
  5. boolean isEmpty()//如果此 collection 不包含元素，则返回 true。
  6. Iterator iterator()//返回在此 collection 的元素上进行迭代的迭代器
  7. boolean remove(E e)// 移除元素
  8. boolean removeAll(Collection c)//移除 collection 的元素
  9. int size() // 返回此 collection 中的元素个数
  10. Object[] toArray()//把集合中的元素，存储到数组中

List接口

  1. 它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。
  2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
  3. 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。
  1. - public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
  2. - public E get(int index):返回集合中指定位置的元素。
  3. - public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
  4. - public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

ArrayList

  • 它继承于AbstractList，实现了List,RandomAccess[随机访问],Cloneable[可克隆], java.io.Serializable[序列化]这些接口。
  • ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
  • ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。
  • ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆
  • ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输
  • 和Vector不同，ArrayList中的操作不是线程安全的。所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

底层数据结构是数组，查询快，增删慢，线程不安全，效率高。

构造方法

  • ArrayList()：构造一个初始容量为10的空列表
  • ArrayList(Collection<?extend E> c)：构造一个包含指定元素的列表
  • ArrayList( int initialCapcity )：构造一个具有初始容量值得空列表
  1. ArrayList<String> list = new ArrayList<String>();

增加元素

  • add(E e)：添加一个元素到列表的末尾。
  • add( int index, E element ) :在指定的位置添加元素
  • addAll( Collection<? extends E> c )：添加一个集合到元素的末尾.以上返回类型是boolean

  • ensureCapcity（int minCapcity）：确保列表中含有minCapcity的最小容量

    删除操作

  • remove(Object o)：删除列表中第一个出现O的元素

  • remove( int index)：删除列表中指定位置的元素
  • removeAll（Collection<?> c）：删除列表中包含C的所有元素
  • removeIf（Predictcate<? super E> filter）：删除列表中给定谓词的所有元素
  • removeRange( int from,int to )：删除从from到to的所有元素

  • clear（）：清除所有的元素。返回类型为void

    更改操作

  • retainAll( Collection<?> c )：仅仅保留列表中和C相同的元素，相当于&运算

  • set（int index,E element）：用element替换index位置上的元素。
  • size()：返回此列表的元素数
  • sort(Comparator<? super E> c)：按照指定的排序规则排序
  • subList( int from , int to )：返回从from到to之间的列表
  • toArray()：将列表转化为数组
  • trimToSize( )：修改当前实例的容量是列表的当前大小。

查操作

  • contains（Object o）：如果包含元素o,则返回为true
  • get（int index）:返回指定索引的元素
  • indexOf( Object o )：返回此列表中指定元素的第一次出现的索引，如果列表不包含此元素，返回-1
  • lastindexOf( Object o ):返回此列表中指定元素的最后一次出现的索引，如果列表不包含此元素，返回-1
  • isEmpty（）：如果列表为空，返回true.
  • iterator()：返回列表中元素的迭代器
  • listIterator（）：返回列表的列表迭代器（按适当的顺序）
  • listIterator(int index)：从适当的位置返回列表的列表迭代器（按照正确的顺序）

遍历

  1. public class ArrayListTraversal {
  2.     public static void main(String[] args) {
  3.         List<String> letters = new ArrayList<>();
  4.         letters.add("a");
  5.         letters.add("b");
  6.         letters.add("c");
  8.         //1.迭代器
  9.         Iterator<String> it = letters.iterator();
  10.         while (it.hasNext()) {
  11.             System.out.println(it.next());
  12.         }
  14.         //2.索引
  15.         for (int i = 0; i < letters.size(); i++) {
  16.             String s = letters.get(i);
  17.             System.out.println(s);
  18.         }
  20.         //3.for-each
  21.         for (String s : letters) {
  22.             System.out.println(s);
  23.         }
  24.     }
  25. }

LinkedList

采用链表结构存储数据 这种结构的优点是操作列表数据快。但是随机访问集合中的数据慢

  1. - public void addFirst(E e):将指定元素插入此列表的开头。
  2. - public void addLast(E e):将指定元素添加到此列表的结尾。
  3. - public E getFirst():返回此列表的第一个元素。
  4. - public E getLast():返回此列表的最后一个元素。
  5. - public E removeFirst():移除并返回此列表的第一个元素。
  6. - public E removeLast():移除并返回此列表的最后一个元素。
  7. - public E pop():从此列表所表示的堆栈处弹出一个元素。
  8. - public void push(E e):将元素推入此列表所表示的堆栈。
  9. - public boolean isEmpty()：如果列表不包含元素，则返回true。

eg

  1. LinkedList<String> list = new LinkedList<String>();
  2.         list.addFirst("A");
  3.         list.addFirst("B");
  4.         list.addFirst("C");
  5.         list.removeLast();
  6.         list.addLast("F");
  7.         System.out.println(list.toString());
  8. #[C, B, F]

Arraylist 与 LinkedList 区别

  • 1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  • 2. 底层数据结构： Arraylist 底层使用的是 **Object** 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
  • 3. 插入和删除是否受元素位置的影响： ① **ArrayList** 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② **LinkedList** 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
  • 4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  • 5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）

    Vector

    底层数据结构是数组，查询快，增删慢，线程安全，效率低。
  1. public void addElement(E obj)：添加元素
  2. public E elementAt(int index)：根据索引获取元素
  3. public Enumeration elements()：获取所有的元素

Set接口

Set集合是由一串无序的，不能重复的相同类型元素构成的集合。Set接口直接实现类是HashSet,HashSet是基于散列表数据结构实现的。
哈希表确定元素是否相同
1、 判断的是两个元素的哈希值是否相同。 如果相同，再判断两个对象的内容是否相同。
2、 判断哈希值相同，其实判断的是对象的HashCode方法。判断内容相同，用的是equals方法。

HashSet

  1. HashSet<String> set = new HashSet<>();
  2.         set.add(new String("a"));
  3.         set.add("b");
  4.         set.add("c");
  5.         set.add("a");
  6.         //遍历
  7.         for (String name : set) {
  8.             System.out.println(name);
  9.         }

LinkedHashSet

HashSet保证元素唯一，可是元素存放进去是没有顺序的，在HashSet下面有一个子类java.util.LinkedHashSet，它是链表和哈希表组合的一个数据存储结构,实现了集合的顺序存储

  1. public static void main(String[] args) {
  3.         LinkedHashSet<String> linkSet = new LinkedHashSet<>();
  4.         for (int i = 0; i < 10; i++) {
  5.             String s = getRandomString(10);
  6.             System.out.printf("RandomString=%s\n", s);
  7.             linkSet.add(s);
  8.         }
  9.         Iterator linkIterator = linkSet.iterator();
  10.         while (linkIterator.hasNext()) {
  11.             System.out.printf("LinkedHashSet=%s\n", linkIterator.next());
  12.         }
  13.     }
  15.     // 生成指定长度的随机字符串
  16.     public static String getRandomString(int length) {
  17.         String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*";
  18.         Random random = new Random();
  19.         StringBuffer sb = new StringBuffer();
  20.         int strLength = str.length();
  21.         for (int i = 0; i < length; i++) {
  22.             int number = random.nextInt(strLength);
  23.             sb.append(str.charAt(number));
  24.         }
  25.         return sb.toString();
  26.     }

Iterator

Iterator主要用于迭代访问（即遍历）Collection中的元素，因此Iterator对象也被称为迭代器。
获取集合的迭代器
Iterator iterator()
Iterator接口的常用方法如下：

E next():返回迭代的下一个元素。
boolean hasNext():如果仍有元素可以迭代，则返回 true。
在调用Iterator的next()方法之前，迭代器的索引位于第一个元素之前，不指向任何元素，当第一次调用迭代器的next()方法后，迭代器的索引会向后移动一位，指向第一个元素并将该元素返回，当再次调用next()方法时，迭代器的索引会指向第二个元素并将该元素返回，依此类推，直到hasNext()方法返回false，表示到达了集合的末尾，终止对元素的遍历。

  1. public static void main(String[] args) {
  2.     ArrayList<Integer> list = new ArrayList<>();
  3.     for (int i = 0; i < 5; i++) {
  4.         list.add(i);
  5.     }
  6.     Iterator<Integer> iterator = list.iterator();
  7.     while (iterator.hasNext()) {
  8.         int i = iterator.next();
  9.         System.out.println(i);
  10.     }
  11. }

for 遍历集合
它的内部原理其实是个Iterator迭代器，所以在遍历的过程中，不能对集合中的元素进行增删操作。for遍历格式如下：

  1. for(元素的数据类型  变量 : Collection集合or数组){ 
  2.     //写操作代码
  3. }

eg:

  1. public static void main(String[] args) {
  2.     ArrayList<Integer> list = new ArrayList<>();
  3.     for (int i = 5; i > 0; i--) {
  4.         list.add(i);
  5.     }
  6.    for (int i :list){
  7.        System.out.println(i);
  8.    }
  9. }

Comparable

Comparable是排序接口。如果一个类实现Comparable接口，那么该类就支持 排序。实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort或 Arrays.sort进行自动排序。
此外，实现此接口的对象可以用作有序映射中的键或有序集合中的集合，无需指 定比较器。
此接口只有一个方法compare，

  1. package java.lang;
  3. public interface Comparable<T> {
  4.     int compareTo(T var1);
  5. }

比较此对象与指定对象的顺序，如果该对象小 于、等于或大于指定对象，则分别返回负整数、零或正整数。

  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Iterator;
  5. class User implements Comparable {
  6.     private String Name;
  7.     private int age;
  9.     public User(String name, int age) {
  10.         Name = name;
  11.         this.age = age;
  12.     }
  14.     @Override
  15.     public String toString() {
  16.         return "User{" +
  17.                 "Name='" + Name + '\'' +
  18.                 ", age=" + age +
  19.                 '}';
  20.     }
  22.     // 根据年龄排序，如果年龄一样　根据姓名排序
  23.     public int compareTo(Object o) {
  24.         User u = (User) o;
  25.         if (this.age != u.age) {
  26.             return this.age - u.age;// 升序排列
  27.         } else {
  28.             return this.Name.compareTo(u.Name);
  29.         }
  30.     }
  31. }
  33. public class comparable {
  34.     public static void main(String[] args) {
  35.         ArrayList<User> list = new ArrayList<User>();
  36.         list.add(new User("张三", 20));
  37.         list.add(new User("李四", 30));
  38.         list.add(new User("王五", 20));
  39.         list.add(new User("赵六", 18));
  40.         list.add(new User("孙七", 25));
  41.         list.add(new User("周八", 30));
  42.         Collections.sort(list);
  43.         Iterator<User> iterator = list.iterator();
  44.         while (iterator.hasNext()) {
  45.             User user = iterator.next();
  46.             System.out.println(user);
  47.         }
  48.     }
  49. }

打印结果

  1. User{Name='赵六', age=18}
  2. User{Name='张三', age=20}
  3. User{Name='王五', age=20}
  4. User{Name='孙七', age=25}
  5. User{Name='周八', age=30}
  6. User{Name='李四', age=30}

总结

  1. List
    Arraylist： Object数组
    Vector： Object数组
    LinkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)
  2. Set
    HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
    LinkedHashSet： LinkedHashSet 继承于 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
    TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树)
  3. Map
    HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
    LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
    Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
    TreeMap： 红黑树（自平衡的排序二叉树）