Collection 子接口:List 接口

一、存储的数据特点

有序的、可重复的数据

二、常用的方法

方法描述
add(Object)增加
remove(int index)/ remove(Object obj)删除
set(int index , object ele)修改
get(int index)查找
add(int index, Object ele)插入
size()长度
① Itertor 迭代器 ②foreach ③ for遍历

三、常用的实现类

  • Collection 接口:单例集合,用来存储一个一个对象
    • List 接口;存储有序的,可重复的数据。
      • ArrayList: 作为 List 接口的主要的实现类:线程不安全,效率高:底层使用 Objecet[] elementDate 存储
      • LinkedList: 对于频繁的插入、删除操作,使用此类效率比 ArraList 高:底层使用双向链表存储。
      • Vector: 作为 List 接口的古老实现类:线程安全,效率低:底层使用 object[] elementDate 存储

四、源码分析

  1. ArrayList 的源码分析
  • JDK 7 情况下:

    • ArrayList list = new ArrayList(); 底层创建长度是 10 的 object[ ]数组 elementDate
    • List.add(123); elementDate[0] = new Integer(123)
    • ….
    • list.add(11); 如果此次的添加导致底层 elementDate 数组容量不够,则扩容。

    默认情况下:扩容为原来的 1.5 倍,同时需要将原有的数组中的数据复制到新的数组中。

    结论:建议开发中使用带参的构造器:ArrayList list = new ArrayList(int capacity)

  • JDK 8 中的 ArrayList 的变化:

    • ArrayList list = new ArrayList(); 底层 object[ ] elementDate 初始化为{},并没有创建长度为 10 的数组
    • list.add(123); 第一次调用 add()时,底层创建了长度为 10 的数组,并将数组 123 添加 dao elementDate[0]
    • ….

    后续的添加和扩容与 jdk 7 无异。

    结论:jdk 7 中的 ArrayList 的对象的创建类似于单例的饿汉式,而 jdk 8 中的 ArrayList 的对象的创建类似于单例模式的懒汉式延迟了数组的创建,节省了空间。

  1. LinkedList 的源码分析

    • LinkedList list = new LinkedList(); 内部声明的 Node 类型的 first 和 last 属性,默认值 null。
    • list.add(123); 将 123 封装到 Node 中,创建 Node

    其中 Node 定义为:体现了 linkedList 的双向链表的说法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;//前

    Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
    }
    }
  • Vector 的源码分析
    • jdk 7 和 jdk 8 中通用 Vector() 构造器创建对象,底层都是创建 10 的数组。
    • 在扩容方面。默认扩容为原数组的 2 倍。

五、存储元素的要求

​ 添加对象,所在的类要重写 equals()方法

Collection 子接口:set 接口

一、存储的数据特点

无序的,不可重复的元素

  • 以 HashSet 为例说明
    • 无序性:不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加,而是根据数组的哈希值决定的。
    • 不可重复性:保证添加的元素按照 equals()判断时,不能返回 true,即,相同的元素只能添加一个。

二、元素添加的过程:(以 HashSet 为例)

  • 我们向 HashSet 中添加元素 a,首先调用元素 a 所在类的 hashcode()方法,计算元素 a 的哈希值,此哈希值接着某种算法在 HashSet 底层数组中的存放位置(即为:索引位置)

  • 接着判断数组位置上是否已经有元素:

    • 如果此位置上没有其他元素,则元素 a 添加成功。 —-》 情况 1

    • 如果此位置上有其他元素 b(获以链表形式存在的多个元素,则比较元素 a 与元素 b 的 hash 值)

      • 如果 hash 值不相同,则元素 a 添加成功。 —》 情况 2
      • 如果 hash 值相同,进而需要调用元素的 a 所在类的 equals()方法
        • equals() 返回 true, 元素 a 添加失败
        • equals() 返回 false, 元素 a 添加成功。 —》 情况 3

      对于添加成功的情况 2 和情况 3 而言:元素 a 与已经存在指定索引上数据以链表的方式存储。

      JDK 7 :元素 a 放大数组中,指向元素 a。

      JDK 8 : 原来的元素在数组中,指向元素 a。

      总结:七上八下

      HashSet 底层:数组加链表的结构。(前提:jdk7)

三、常用的方法

​ set 接口没有定义新的方法,使用的都是 collection 声明方法。

四、常用实现类

  • Collection 接口:单例集合,用来存储一个一个的对象、
    • set 接口:存储无序的、不可重复的数据
      • HashSet : 作为 Set 接口主要实现类;可以存储 null 值
        • LinkedHashSet: 作为 HashSet 的子类;遍历其内部数据时,可以按照添加的顺序遍历,造添加数据的同时,每一个数据还在维护两个引用。记录此数据的前一个和后一个数据。对于频繁的遍历操作,LinkedHashSetLinkedHashSet 效率高于 HashSet.
      • TreeSet:可以添加对象的指定属性,进行排序。

五、存储对象所在类的要求

  • HashSet/LinkedHashSet:

    • 要求:向 Set(主要指:HashSet、LinkedHashSet)中添加数据,其所在的类一定要重写hashcode()**和equals()**。

    • 要求:重写的 HashCode() 和 equals() 尽可能保持一致:相等的对象必须具体的相等的散列码

      ​ 重写的两个方法的小技巧:对象中用作 equals()方法比较的 Field,都应该用来计算 hashcode 值。

  • TreeSet:

    • 自然排序中,比较两个对象是否相等的标准为:compareTo() 返回 0,不再是 equals()
    • 定制排序中,比较两个对象是否相同的标准为:compare()返回 0.不再是 equals().

六、TreeSet 的使用

  • 向 TreeSet 中添加的数据,要求是相同类的对象。
  • 两种排序方式:自然排序(实现 Comparable 接口 和 定制排序(Comparator)
  1. 自然排序:

    创建 User 类

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class User implements Comparable{
private String name;
private int age;

public User() {
}

public User(String name, int age) {
this.name = name;
this.age = age;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return age;
}

public void setAge(int age) {
this.age = age;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return age == user.age &&
name.equals(user.name);
}

@Override
public int hashCode() {
return Objects.hash(name, age);
}

@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}

@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User) o;
if(this.name.equals(user.name)){
return this.age - user.age;
}
return this.name.compareTo(user.name);
}
throw new RuntimeException("输入的值无法判断");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Test
public void test1() {
TreeSet set = new TreeSet();
set.add(new User("hunan", 12));
set.add(new User("beijing", 12));
set.add(new User("hunan", 9));
set.add(new User("fujian", 15));
set.add(new User("lingxia", 18));

Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}

image-20200721182530695

  1. 定制排序
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
@Test
public void test2(){
Comparator com = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User user1 = (User) o1;
User user2 = (User) o2;
return Integer.compare(user1.getAge(), user2.getAge());
}else{
throw new RuntimeException("输入的数据类型不匹配");
}
}
};

TreeSet set = new TreeSet(com);
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Mary",33));
set.add(new User("Jack",33));
set.add(new User("Jack",56));

Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}

image-20200721183621349