常用方法#

三种遍历#

(1) 迭代器遍历

迭代器是用来遍历集合的专用方式（数组没有迭代器，只能遍历集合），在Java中迭代器的代表是Iterator。

• 获取迭代器Iterator<E> iterator()：返回集合的迭代器对象，该对象默认指向集合中第一个元素。

迭代器中常用方法：

• boolean hasNext()：访问当前位置是否有元素存在，存在返回true。
• E next()：获取当前位置的元素，并同时将迭代器对象指向下一个元素处。

1
Collection<String> names = new ArrayList<>();
2
names.add("张三");
3
...
4

5
// 得到集合的迭代器对象
6
Iterator<String> it = names.iterator();
7
while (it.hasNext()) {
8
    String name = it.next();
9
    System.out.println(name);
10
}

(2) 增强for（foreach）

可以用来遍历集合或数组。

1
for(元素的数据类型 变量名: 数组或集合) {
2

3
}

1
for (String name : names) {
2
    System.out.println(name);
3
}

(3) Lambda表达式

需要使用Collection的方法：

1
default void forEach(Consumer<? super T> action)

会将匿名内部类对象传给forEach的action

1
names.forEach(new Consumer<String>() {
2
    @Override
3
    public void accept(String s) {
4
        System.out.println(s);
5
    }
6
});
7
names.forEach(s -> System.out.println(s)); // 简化
8
names.forEach(System.out::println); // 简化

集中遍历的区别—并发修改异常问题#

遍历集合的同时又存在增删改查集合元素的行为时可能会出现业务异常，这种现象称之为并发修改异常问题。

需求：购物车存在如下商品：Java入门、宁夏枸杞、枸杞子、黑枸杞、特技枸杞。现在用户不想买枸杞，选择了批量删除。

1
ArrayList<String> list = new ArrayList<>();
2
list.add("Java入门");
3
list.add("宁夏枸杞");
4
list.add("枸杞子");
5
list.add("黑枸杞");
6
list.add("特技枸杞");
7
// 错误
8
for (int i = 0; i < list.size(); i++) {
9
    String name = list.get(i);
10
    if (name.contains("枸杞子")) {
11
        list.remove(name);
12
    }
13
}
14
System.out.println(list);

1
for (int i = 0; i < list.size(); i++) {
2
    String name = list.get(i);
3
    if (name.contains("枸杞子")) {
4
        list.remove(name);
5
        i--;
6
    }
7
}

1
for (int i = list.size() - 1; i >= 0; i--) {
2
    String item = list.get(i);
3
    if (item.contains("枸杞")) {
4
        list.remove(i);
5
    }
6
}

1
// 错误
2
Iterator<String> iterator = list.iterator();
3
while (iterator.hasNext()) {
4
    String item = iterator.next();
5
    if (item.contains("枸杞")) {
6
        list.remove(item);
7
    }
8
}

1
Iterator<String> iterator = list.iterator();
2
while (iterator.hasNext()) {
3
    String item = iterator.next();
4
    if (item.contains("枸杞")) {
5
        iterator.remove();
6
    }
7
}

1
for (String s : list) {
2
    if (s.contains("枸杞")) {
3
        list.remove(s);
4
    }
5
}

1
list.forEach(s -> {
2
    if (s.contains("枸杞")) {
3
        list.remove(s);
4
    }
5
});

1
list.removeIf(s -> s.contains("枸杞"));

特点、功能#

有序、可重复、有索引

List支持索引，所以多了很多与索引相关的方法。当然，Collection的功能List也都继承了。

支持的遍历方式：

1. for循环（因为有索引）
2. 迭代器
3. 增强for循环
4. Lambda表达式（forEach）

ArrayList和LinkedList的不同#

底层采用的数据结构不同。

• ArrayList是基于数组存储数据的

  • （根据索引）查询速度快。
  • 增删数据效率低（容量不够会扩容、删除后面的数据要前移）。

• LinkedList是基于双链表存储数据的

  链表结点在内存中不连续，每个结点包含数据值和下一个结点地址。

  • 查询慢（无论查询哪个数据都要从头开始遍历）。
  • 增删相对快。

  双链表：首尾指针

  • 查询慢

  • 对首尾元素进行增删改查的速度极快。

  方法名称	说明
  public void addFirst(E e)	在列表头部插入指定元素
  public void addLast(E e)	在列表尾部插入指定元素
  public E getFirst()	返回列表第一个元素
  public E getLast()	返回列表最后一个元素
  public E removeFirst()	从列表删除并返回第一个元素
  public E removeLast()	从列表删除并返回最后一个元素

  应用场景：

  • 设计队列（先进先出，首部出队、尾部进队）。
  • 设计栈（先进后出，栈顶出栈）。

特点#

无序（添加元素的顺序和获取出的顺序不一致）、不重复、无索引

• HashSet：无序、不重复、无索引
• LinkedHashSet：有序（添加的顺序和实际顺序一致）、不重复、无索引
• TreeSet：排序（自动升序）、不重复、无索引

基本都是Collection的功能，几乎没有额外的新功能。

HashSet底层原理#

哈希值

• 就是一个int类型的随机值，Java中每个对象都有一个哈希值。
• Java中所有对象，都可以用Object类的hashCode()方法返回对象的哈希值。
• 同一个对象多次调用hashCode()返回的哈希值相同。
• 不同的对象，它们的哈希值大概率不同，也有可能相同（哈希碰撞）。

HashSet基于哈希表存储数据。

• JDK8之前，哈希表=数组+链表。
  1. 创建一个默认长度为16的数组，默认加载因子为0.75，数组名table
     • 当数组存入16*0.75=12时，扩容两倍（32），重新存入数据。
  2. 使用元素的哈希值对数组的长度做取余运算计算出存入的位置。
  3. 判断当前位置是否为null，如果是null直接存入。否则，调用equals方法比较是否相等；如果相等则不存，不相等则存入。
     • JDK8之前，新元素存入数组，占老元素位置，老元素挂下面（头插入）
     • JDK8开始，新元素挂老元素下面（尾插入）
• JDK8开始，哈希表=数组+链表+红黑树（可以自平衡的二叉树）。
  • 当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树。

哈希表是一种增删改查性能都较好的数据结构。

自定义对象去重#

需求：创建一个存储对象的集合，存储多个对象。要求多个学生对象的成员变量相同时，我们就认为是同一个对象，只保留一个。

1
Set<Student> set = new HashSet<>();
2
set.add(new Student("小明", 18, "北京"));
3
set.add(new Student("小红", 18, "南京"));
4
set.add(new Student("小明", 18, "北京"));
5
set.add(new Student("小红", 18, "南京"));
6
System.out.println(set);

如果希望Set集合认为2个内容一样的对象时重复的，必须重写对象的hashCode方法和equals方法：

1
@Override
2
public boolean equals(Object o) {
3
    if (this == o) return true;
4
    if (o == null || getClass() != o.getClass()) return false;
5
    Student student = (Student) o;
6
    return age == student.age && Objects.equals(name, student.name) && Objects.equals(address, student.address);
7
}
8

9
@Override
10
public int hashCode() {
11
    return Objects.hash(name, age, address);
12
}

LinkedHashSet底层原理#

有序、不重复、无索引。

• 依然是基于哈希表（数组+链表+红黑树）实现的。
• 但是，它的每个元素额外的多了一个双链表机制记录它前后元素的位置（读的时候，从首支指针开始寻找）。
• 更浪费内存了。

TreeSet#

可排序（默认升序）、不重复、无索引。

• 底层基于红黑树实现的排序。
  • 对于数值类型：Integer、Double，默认按数值大小升序
  • 对于字符串类型：默认按首字符的编号升序
  • 对于自定义类型（如Student对象），默认无法排序

解决方法：

1. 让对象类实现Comparable接口，重写compareTo方法。

   1
   @Override
   2
   public int compareTo(Student o) {
   3
       if (this.age > o.age) return 1;
   4
       else if (this.age < o.age) return -1;
   5
       else return 0; // 如果想根据年龄去重返回0，否则返回非0
   6
   }

   1
   @Override
   2
   public int compareTo(Student o) {
   3
       return this.age - o.age;
   4
   }

2. 集合自带比较器Comparator对象，指定比较规则。

   1
   Set<Student> set = new TreeSet<>(new Comparator<Student>() {
   2
       @Override
   3
       public int compare(Student o1, Student o2) {
   4
           return o1.getAge() - o2.getAge();
   5
       }
   6
   });

   1
   Set<Student> set = new TreeSet<>(((o1, o2) -> o1.getAge() - o2.getAge()));

如果要比较Double类型，就不能这么写了，要老实点判断。

或者调用Double的方法：

1
Set<Student> set = new TreeSet<>(((o1, o2) -> Double.compare(o1.getSalary(), o2.getSalary())));

体系和特点#

• Map集合也叫“键值对集合”
• 所有键不允许重复，值可以重复。键和值一一对应。

应用场景：

需要存储一一对应的数据对时。例如购物车：

1
{商品1: 2, 商品2: 3, ...}

Map集合的特点都是由键决定的。

• HashMap：无序、不重复、无索引。（键值对都可以是null）
• LinkedHashMap：有序、不重复、无索引。（键值对都可以是null）
• TreeMap：按照key大小默认升序排序、不重复、无索引。（键不可以是null）

常用方法#

Map集合的方法：

遍历方式#

(1) 键找值——先获取Map集合全部的键，再通过遍历键来找值。

1
Set<String> keySet = map.keySet();
2
for (String key : keySet) {
3
    String value = map.get(key);
4
    System.out.println(key + ":" + value);
5
}

(2) 键值对——把“键值对”看成一个整体进行遍历。（难度较大）

• 想办法把Map集合变成Set集合来遍历
• entrySet()方法会遍历把Map中的每个键值对封装为Entry对象

1
for (Map.Entry<String, String> entry : map.entrySet()) {
2
    System.out.println(entry.getKey() + ":" + entry.getValue());
3
}

(3) Lambda——JDK1.8开始的新技术。内部用的是法二（非常简单）

1
map.forEach(new BiConsumer<String, String>() {
2
    @Override
3
    public void accept(String key, String value) {
4
        System.out.println(key + ":" + value);
5
    }
6
});
7
// or
8
map.forEach((k, v) -> System.out.println(k + ":" + v));

实现原理#

和Set一样，Set底层就是用Map实现的。