Java容器_元素遍历和比较(2)

for i 遍历 List

List 可以直接通过 get 方法进行 for i 遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Test {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("b");
    for (int i = 0; i < list.size(); i++) {
      if ("b".equals(list.get(i))) {
        list.remove(i);
        //remove掉一个元素后,后面的元素会向前进一位
        //所以要i--,让指针回退一位
        i--;
        //list.remove(i--);
      }
    }
    System.out.println(list); //[a]
  }
}

但 Set 没有 get 方法,所以需要通过迭代器来进行遍历

Iterator

Collection 继承了 Iterable 接口,可通过 iterator 方法创建 Iterator 对象来遍历 Collection 中的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Test {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    //获取迭代器
    Iterator<String> it = list.iterator();
    //判断集合中是否有元素
    while(it.hasNext()) {
      //获取元素
      System.out.print(it.next()); //abc
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Test {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    Iterator<String> it = list.iterator();
    while (it.hasNext()) {
      String s = it.next();
      if ("a".equals(s)) {
        //在遍历时进行remove
        //可能会抛出异常ConcurrentModificationException
        //list.remove("a");
        //可以用迭代器提供的remove方法删除
        it.remove();
      }
    }
    System.out.println(list); //[b]
  }
}

上面代码出现 ConcurrentModificationException 异常的原因将在 List 源码分析中进行讨论

Set 通过迭代器的遍历与 List 同理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Test {
  public static void main(String[] args) {
    HashSet<String> set = new HashSet<>();
    set.add("a");
    set.add("b");
    Iterator<String> it = set.iterator();
    while (it.hasNext()) {
      String s = it.next();
      if ("a".equals(s)) {
        //set.remove("a");
        it.remove();
      }
    }
    System.out.println(set); //[b]
  }
}

Iterator 迭代器只提供了删除的方法,没有提供添加的方法,对于 List,可以通过 Iterator 的子类 ListIterator 来进行遍历时的添加

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Test {
  public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    ListIterator<String> lit = list.listIterator();
    while (lit.hasNext()) {
      String s = lit.next();
      if ("b".equals(s)) {
        lit.add("c");
      }
    }
    System.out.println(list); //[a, b, c]
  }
}

foreach

JDK 1.5 引入了 foreach 来简化遍历的语法,其底层也是通过 Iterator 来遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Test {
  public static void main(String[] args) {
    HashSet<String> set = new HashSet<>();
    set.add("a");
    set.add("b");
    for (String s : set) {
      if ("a".equals(s)) {
        //foreach底层是迭代器,所以也会有并发修改异常
        //set.remove("a");
      }
    }
    //String s;
    //for (Iterator<String> it = set.iterator(); it.hasNext();) {
    //    s = it.next();
    //}
  }
}

List 遍历方式的选择

ArrayList 通过 get 方法进行 for i 遍历比用 iterator 迭代器遍历要快,而 LinkedList 用 iterator 迭代器遍历则比用索引的 for i 遍历要快,因为 LinkedList 通过索引来遍历每次都要重头开始

1
2
3
4
head
head -> item1
head -> item1 -> item2
...

所以应该考虑到 List 的不同实现而采用不同的遍历方式来提高性能

ArrayList 实现了 RandomAccess 接口,而 Linked 没有实现,所以可以通过判断 list 是否实现了 RandomAccess 接口来选择合适的遍历方式

1
list instanceof RandomAccess

Comparable 和 Comparator

一个类实现了 Comparable 接口并重写 compareTo 方法,则表示该类可以被比较

1
2
3
public interface Comparable<T> {
  public int compareTo(T o);
}

compareTo 返回 0 表示等于,返回正数表示大于,返回负数表示小于

注意相等的情况,尽量使 compareTo 与 equals 的结果一致,JDK 实现的 Java 核心类基本都保持了 compareTo 与 equals 结果一致,但 BigDecimal 不一致

对于没有实现 Comparable 接口的类,可以实现一个比较器 Comparator 传给排序方法进行比较

1
2
3
public interface Comparator<T> {
  int compare(T o1, T o2);
}

compare 方法,同样是返回 0 表示等于,返回正数表示大于,返回负数表示小于,但优先级比 compareTo 方法更高,即如果既实现了 Comparable 又传入了 Comparator,则 Comparable 的比较规则将会被覆盖

注意 o2 是被比较的一方,即返回的结果是 o1 等于/大于/小于 o2

比较实例

TreeSet 的 add 方法比普通 Set 的要特殊,是通过 compareTo 方法或者 Comparator 比较器来进行判重,而不是通过 hashcode 和 equals 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Test {
  public static void main(String[] args) {
    TreeSet<Student> ts = new TreeSet<>();
    ts.add(new Student("张三"));
    ts.add(new Student("张三"));
    ts.add(new Student("王五"));
    ts.add(new Student("李四"));
    System.out.println(ts);
    //compareTo返回0 [张三]
    //compareTo返回正数 [张三, 张三, 王五, 李四]
    //compareTo返回负数 [李四, 王五, 张三, 张三]
  }
}

class Student implements Comparable<Student> {
  String name;
  public Student(String name) {
    this.name = name;
  }
  @Override
  public String toString() {
    return this.name;
  }
  @Override
  public int compareTo(Student o) {
    //return 0;
    //return 1;
    return -1;
  }
}

Comparator 比较器的方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Test {
  public static void main(String[] args) {
    TreeSet<Student> ts = new TreeSet<>(new ComparatorImpl());
    ts.add(new Student("张三"));
    ts.add(new Student("张三"));
    ts.add(new Student("王五"));
    ts.add(new Student("李四"));
    System.out.println(ts);
    //[张三, 李四, 王五]
  }
}

class Student {
  String name;
  public Student(String name) {
    this.name = name;
  }
  @Override
  public String toString() {
    return this.name;
  }
}

class ComparatorImpl implements Comparator<Student> {
  @Override
  //第二个参数s2是被比较的一方
  public int compare(Student s1, Student s2) {
    //先比较name的长度
    int numDiff = s1.name.length() - s2.name.length();
    //若长度相同则再比较String值
    //因为String实现了Comparable接口,所以可直接返回compareTo的值
    return numDiff == 0 ? s1.name.compareTo(s2.name) : numDiff;
  }
}

以上内容是玉山整理的笔记,如有错误还请指出