总结

Java的集合类都在java.util包中,使用前需要导入：import java.util.*;

单列集合(Collection)

  • Collection是单列集合的根接口,实现了该接口的类称为单列集合
    • List 子接口: 实现List接口的集合称为List集合
      • List集合的特点是存储的元素有序且可重复
      1. ArrayList
      2. LinkedList
    • Set 子接口: 实现Set接口的集合称为Set集合
      • Set集合的特点是存储的元素无序且不可重复
      1. HashSet
      2. TreeSet
    • Queue 子接口
  • 有序是指元素的存储位置有顺序,不是指元素按大小有序

双列集合(Map)

  • Map是双列集合类的根接口,实现了该接口的类称为双列集合
    • HashMap
    • TreeMap
    • HashTable
  • 双列集合用于存储具有键(Key)—值(Value)对应关系的元素,每个元素由键和值组成一个二元组<Key,Value>
  • 键用来唯一标识元素,可以通过键找到值

List

  • 实现List接口的集合称为List集合,也可称为列表,主要有ArrayList和LinkedList。
  • List集合允许出现重复元素,元素以线性方式存储,可以通过索引(下标)来访问。List集合的存储顺序和遍历顺序一致。

List

ArrayList

  • 在ArrayList集合的内部封装了一个数组,初始长度的默认值是10,也可以在创建集合对象时指定数组的初始长度。
  • ArrayList集合的add(Object o)方法将元素添加到列表的尾部,而add(int index,Object o)方法将元素插入列表的指定位置index处
  • 删除元素时,ArrayList集合将被删除元素之后的元素都向前移一个位置以填补空位
  • 将元素插入指定位置时,会将该位置的元素以及后面的元素都向后移一个位置
  • 更新操作的效率低
  • 查询操作的效率高
  • 集合和数组一样,索引的取值范围是从0开始,到size-1为止(size是集合中的元素个数),不能超出此范围,否则会引发异常。

LinkedList

  • 在LinkedList集合内部维护了一个双向链表,每个元素都存有分别指向前一个元素和后一个元素的引用,从而将所有的元素链接起来
  • 调用LinkedList的add(int index,Object o)方法添加元素,需要先找到索引index指示的位置,所以时间复杂度是O(n)。
  • 调用add(Object o)、addFirst(Object o)、addLast(Object o)等方法添加元素,因为位置是已知的,只需要添加新节点,所以时间复杂度是O(1)

LinkedList

Iterator

  • Iterator接口也是Java集合框架中的一员,也称为迭代器
  • 集合的iterator()方法返回一个Iterator接口的实现类对象,用于遍历集合中的元素
  • Iterator 方法:
    • boolean hasNext(): 判断是否还有下一个元素,如果是,返回 true,否则返回false。
    • Object next(): 访问下一个元素并返回该元素的引用。调用next()方法访问下一个元素时,要保证该元素的存在,否则会抛异常
    • void remove(): 删除刚访问过的元素
  • 在使用Iterator迭代器遍历集合的过程中，如果调用集合的remove()或add()方法执行删除或添加操作，那么再继续遍历就会引发异常
    • 删除某个元素后跳出循环不再继续迭代
    1
    2
    3
    4
    if("Annie".equals(obj)) {
        list.remove(obj);
        break;
    }
    • 可以使用Iterator迭代器自身的删除方法，也就是将代码list.remove(obj) 替换成it.remove()
    1
    2
    3
    if("Annie".equals(obj)) {
        it.remove();
    }

ListIterator接口

  • 为了使迭代方式多样化，既可以正向迭代，也可以反向迭代，Java提供了ListIterator接口
  • 它是Iterator的子接口，新增了一些方法
  • 集合的listIterator()方法返回一个ListIterator迭代器对象
  • 注意，List集合实现了ListIterator接口，而Set集合没有实现ListIterator迭代器

ListIterator

  • ListIterator新增的方法主要用于反向迭代，此外还提供add()方法用于在遍历的过程中添加元素
  • 由于ListIterator是Iterator的子接口，因此是双向迭代器
  • 在遍历集合的期间，通过Iterator迭代器只能删除元素，而通过ListIterator迭代器既可以添加也可以删除元素
  • listIterator(int index)方法的index参数指定迭代的起始位置，正反向迭代都可以执行，index的范围是0到list.size()；
  • 无参数的listIterator()方法,则相当于调用listIterator(0)

foreach

foreach循环除了用于遍历数组外，也可以用于遍历集合，是一种更加简洁的for循环，也称增强型for循环

1
2
3
for(集合中的元素类型 临时变量 : 容器) {
    执行语句
}

与for循环相比，foreach循环不需要获得容器的长度，也不需要通过索引访问容器中的元素，而是自动的遍历容器中的每个元素

foreach循环只能用于遍历访问，不能用于修改集合或数组中的元素。
因为临时变量保存的是所访问元素的引用，修改临时变量，只是修改了临时变量的引用，而不是修改所引用元素的值

Set

  • 与List集合不同，Set集合中的元素无序、不允许重复
  • 主要实现类有HashSet和TreeSet
  • HashSet内部维持一个哈希表结构，根据对象的哈希值来确定元素的存储位置
  • TreeSet内部则维持一个二叉排序树，对存入集合中的每个元素进行排序

HashSet

  • 当使用HashSet的add()方法添加一个元素时，首先调用该元素的hashCode()方法获得对象的哈希值，然后根据哈希值确定一个存储位置
  • 如果这个位置上没有元素，直接将该元素存入此位置
  • 如果这个位置上已存入元素，则调用该元素的equals()方法依次和已存入元素进行比较
    • 比较结果均为false说明不存在重复元素，则将该元素存入这个位置
    • 若和某个已存入元素的比较结果为true，说明该元素和这个已存入元素的值相等，则抛弃该元素
  • 由于哈希表冲突现象的存在，哈希值相同的对象未必就是值相同的对象

当向HasheSet集合中存入元素时，为了保证HasheSet正常工作，存入的对象应当重写Object根类的hashCode()和equals()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public int hashCode(){
    return id.hashCode();
}

@Override
public boolean equals(Object o){
    // if(this == o) { return true; }
    // if(getClass() != o.getClass()) { return false; }
    if(o == null) { return false; }
    if(!(o instanceof S)) { return false; } 
    S s = (S) o;
    return this.id.equals(s.id); 
}

TreeSet

  • TreeSet集合采用二叉排序树来存储元素，会对存入的元素进行排序
  • 因为要排序，所以要比较元素的大小，这就需要元素实现Comparable接口，或者给集合传入一个自定义的Comparator比较器
  • TreeSet集合同样不允许存入重复元素，若插入重复的新元素则会抛弃
  • 和HashSet集合不同，TreeSet集合是通过比较大小来判断是否是重复元素，大小相同元素的就认为是重复元素
  • 通过Iterator迭代器遍历TreeSet集合时，输出的字符串按字典序形成有序序列
  • 因为TreeSet集合在内部对元素进行排序，而String类实现的Comparable接口是按字典序比较大小的
  • TreeSet集合用Iterator迭代器遍历形成的元素序列都是有序序列
  • 往TreeSet集合中添加的元素需要实现Comparable接口，否则无法比较大小，没法进行排序
  • 可以自己为TreeSet集合定义一个比较器，即定义一个Comparator接口的实现类，把该实现类的对象输入TreeSet集合作为比较器

Map

实现了Map接口的集合称为Map集合，也叫双列集合，常用的有HashMap和TreeMap(提示：HashSet由HashMap实现，TreeSet由TreeMap实现)
双列集合存储的每个元素都包含一个键Key和一个值Value，从键到值构成一个映射。键具有唯一性，可以唯一确定一个元素

  • 访问Map集合中的元素时，只要指定了Key，就能找到对应的值
  • Map集合添加元素使用put(Object k, Object v)方法，查找元素使用get(Object k)方法

HashMap

HashMap内部维持一个Hash表，用于存储具有键—值映射关系的数据

  • HashMap集合不允许出现重复的键，如果出现重复的键，则认为是重复的元素，那么新元素会覆盖键相同的旧元素
  • 通过重写键的hashCode()方法来计算键的hash码，通过重写键的equals()方法来判断键是否相同，如果不重写，就会调用从Object类继承的这两个方法
  • 往HashMap集合添加元素的过程与HashSet集合类似
    • 首先调用键的hashCode()方法计算键的hash码，根据hash码计算出存储位置
    • 如果在该位置上没有元素就直接存入
    • 如果该位置上已有元素，则调用键的equals()方法依次和这些已有元素的键进行比较
    • 如果比较结果均为false，就将该元素存入当前位置，否则说明有重复元素，则用新元素覆盖键相同的旧元素

三种遍历

1
2
3
4
5
6
7
8
9
Map map = new HashMap();
// map.put(); ...
Set set = map.KeySet();
Iterator it = set.iterator();
while(it.hasNext()){
    Object k = it.next();
    Object v = map.get(k);
    System.out.println(k + " : "+ v);
}
1
2
3
4
5
6
7
8
9
10
Map map = new HasMap();
// map.put(); ...
Set set = map.entrySet();
Iterator it = set.iterator();
while (it.hasNext()){
    Map.Entry entry = (Map.Entry) it.next();
    Object k = entry.getKey();
    Object v = entry.getValue();
    System.out.println(k + " : " + v);
}
1
2
3
4
5
6
7
8
Map map = new HasMap();
// map.put(); ...
Collection vs = map.values();
Iterator it = vs.iterator();
while (it.hasNext()){
    Object v = it.next();
    System.out.println(v);
}

TreeMap

  • 用来存储由键-值对构成的元素，不允许出现重复的键
  • TreeMap集合使用二叉排序树来存储元素，元素是按键的大小顺序排列的
  • 元素的键要实现Comparable接口或者实现键的自定义比较器Comparator，以便能对键比较大小
  • 键大小相同的元素即认为是重复元素，对于重复元素，也是新元素覆盖旧元素
  • TreeMap集合的遍历方式与HashMap集合相同，也是那三种方式

工具类

  • java.util包提供了工具类Collections用来操作集合
  • Collections类封装了大量静态方法对集合中的元素进行排序、查找和修改等操作

排序操作

  • static void reverse(List list)：反转List集合中的元素顺序
  • static void sort(List list)：根据自然序对集合中的元素进行排序
  • static void shuffle(List list)：对List集合中的元素进行随机排序(洗牌)

查找替换

  • static int binarySearch(List list, Object key)：使用二分查找法搜索集合中是否存在指定值为key的元素，返回该值的索引
  • static Object max(Collection col)：返回集合中最大的元素
  • static Object min(Collection col)：返回集合中最小的元素
  • static boolean replaceAll(List list, Object oldVal, Object newVal)：用新值newVal取代集合中的所有旧值oldVal
  • static void swap(List list, int i, int j)：交换集合中位置i和位置j处的元素

Arrays

java.util包还提供了用于操作数组的工具类Arrays，封装大量的静态方法用于操作数组

排序

  • 可以使用Arrays的sort()方法实现数组的排序。
  • 如果数组的元素是字符型、整型或浮点型等数值类型，则按值的大小进行排序。
  • 如果数组的元素是对象，则所有元素都必须实现 Comparable 接口(按该接口的compareTo方法比较大小)，否则无法排序。

查找

  • binarySearch()方法使用二分查找法搜索指定值的位置，需要先对数组排序。
  • 如果数组的元素是对象，还需要自己实现比较器：int binarySearch(Object[] a, Object key, Comparator c)，这里参数c是一个自定义的Comparator比较器。

把数组转换为字符串

  • 使用Arrays的toString()方法将数组存储的数据转换成字符串形式：[“元素1”, “元素2”, …]，这样就可以直接打印输出数组了。
  • 如果数组的元素是八种基本类型，没有任何问题；如果数组的元素是对象，则要调用对象的toString()方法实现转换，所以元素必须正确的重写Object类的toString()方法

拷贝元素

Arrays工具类的copyOfRange(Object[] original, int from, int to)方法将数组中指定范围的元素复制到一个新的数组中，该方法中参数original表示被复制的数组，from表示被复制元素的初始索引(包括)，to表示被复制元素的最后索引(不包括)

填充元素

可以使用Array的fill(Object[] a, Object val)方法将指定的值赋给数组中的每一个元素