3.容器的学习(1/2)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20

20容器_LinkedList容器的使用（非List标准）

public class LinkedListTest2 {
    public static void main(String[] args) {
        System.out.println("-------LinkedList-------------");
        //将指定元素插入到链表开头
        LinkedList linkedList1 = new LinkedList<>();
        linkedList1.addFirst("a");
        linkedList1.addFirst("b");
        linkedList1.addFirst("c");
        for (String str:linkedList1){
            System.out.println(str);
        }
        System.out.println("----------------------");
        //将指定元素插入到链表结尾
        LinkedList linkedList = new LinkedList<>();
        linkedList.addLast("a");
        linkedList.addLast("b");
        linkedList.addLast("c");
        for (String str:linkedList){
            System.out.println(str);
        }


        System.out.println("---------------------------");
        //返回此链表的第一个元素
        System.out.println(linkedList.getFirst());
        //返回此链表的最后一个元素
        System.out.println(linkedList.getLast());


        System.out.println("-----------------------");
        //移除此链表中的第一个元素，并返回这个元素
        linkedList.removeFirst();
        //移除此链表中的最后一个元素，并返回这个元素
        linkedList.removeLast();
        for (String str:linkedList){
            System.out.println(str);
        }


        System.out.println("-----------------------");
        linkedList.addLast("c");


        //从此链表所表示的堆栈处弹出一个元素,等效于removeFirst
        linkedList.pop();
        for (String str:linkedList){
            System.out.println(str);
        }
        System.out.println("-------------------");
        //将元素推入此链表所表示的堆栈  这个等效于addFisrt(E e)
        linkedList.push("h");
        for (String str:linkedList){
            System.out.println(str);
        }
    }
}

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

21容器_LinkedList源码分析 添加元素

添加元素

节点类

private static class Node {
    E item;
    Node next;
    Node prev;


    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

成员变量

transient int size = 0;


/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node first;


/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node last;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

添加元素

/**
 * Appends the specified element to the end of this list.
 *
 * 
This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}


/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

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

22容器_LinkedList源码分析 头尾添加元素

头尾添加元素

addFirst

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}


/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node f = first;
    final Node newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

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

addLast

/**
 * Appends the specified element to the end of this list.
 *
 * 
This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}


/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

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

23容器_LinkedList源码分析 获取元素

获取元素

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

1
2
3
4
5
6
7
8
9
10
11
12

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

1
2
3
4
5

/**
 * Tells if the argument is the index of an existing element.
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}        

1
2
3
4
5
6
7

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node node(int index) {
    // assert isElementIndex(index);


    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

24容器_Set接口介绍

Set接口继承自Collection接口，Set接口中没有新增方法，它和Collection接口保持完全一致。我们在前面学习List接口的使用方式，在Set中仍然适用。因此，学习Set的使用将没有任何难度。

Set接口特点

Set特点：无序、不可重复。无序指Set中的元素没有索引，我们只能遍历查找；不可重复指不允许加入重复的元素。更确切地讲，新元素如果和Set中某个元素通过equals()方法对比为true，则只能保留一个。

Set常用的实现类有：HashSet、TreeSet等，我们一般使用HashSet。

25.容器_HashSet_HashSet容器的使用

HashSet是Set接口的实现类。是Set存储特征的具体实现。

public class HashSetTest {
    public static void main(String[] args) {
        //实例化HashSet
        Set set = new HashSet<>();
        //添加元素
        set.add("a");
        set.add("b1");
        set.add("c2");
        set.add("d");
        set.add("a");


        //获取元素,在Set容器中没有索引，所以没有对应的get(int index)方法
        for(String str: set){
            System.out.println(str);
        }
        System.out.println("--------------------");
        //删除元素
        boolean flag = set.remove("c2");
        System.out.println(flag);
        for(String str: set){
            System.out.println(str);
        }
        System.out.println("------------------------");
        int size = set.size();
        System.out.println(size);
    }
}
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

26.容器_HashSet_HashSet存储特征分析

HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程不安全的。HashSet允许有null 元素。

无序：

在HashSet中底层是使用HashMap存储元素的。HashMap底层使用的是数组与链表实现元素的存储。元素在数组中存放时，并不是有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定元素在数组中的位置。

不重复：

当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会调用元素的equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素，如果不相同则会使用单向链表保存该元素。

27容器_HashSet通过HashSet存储自定义对象

要自定义对象的化要添加三个方法

equals
hashcode

1
2
3

创建Users对象

public class Users {
    private String username;
    private int userage;


    public Users(String username, int userage) {
        this.username = username;
        this.userage = userage;
    }


    public Users() {
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;


        Users users = (Users) o;


        if (userage != users.userage) return false;
        return username != null ? username.equals(users.username) : users.username == null;
    }


    @Override
    public int hashCode() {
        int result = username != null ? username.hashCode() : 0;
        result = 31 * result + userage;
        return result;
    }


    public String getUsername() {
        return username;
    }


    public void setUsername(String username) {
        this.username = username;
    }


    public int getUserage() {
        return userage;
    }


    public void setUserage(int userage) {
        this.userage = userage;
    }


    @Override
    public String toString() {
        return "Users{" +
                "username='" + username + '\'' +
                ", userage=" + userage +
                '}';
    }
}

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
63
64
65
66

在HashSet中存储Users对象

public class HashSetTest2 {
    public static void main(String[] args) {
        //实例化HashSet
        Set set = new HashSet<>();
        Users u = new Users("oldlu",18);
        Users u1 = new Users("oldlu",18);
        set.add(u);
        set.add(u1);
        System.out.println(u.hashCode());
        System.out.println(u1.hashCode());
        for(Users users:set){
            System.out.println(users);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

https://www.itbaizhan.com/course/id/39439.html

28容器_HashSet_HashSet底层源码分析

成员变量

private transient HashMap map;


// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

1
2
3
4
5
6

添加元素

/**
 * Adds the specified element to this set if it is not already present.
 * More formally, adds the specified element e to this set if
 * this set contains no element e2 such that
 * (e==null ? e2==null : e.equals(e2)).
 * If this set already contains the element, the call leaves the set
 * unchanged and returns false.
 *
 * @param e element to be added to this set
 * @return true if this set did not already contain the specified
 * element
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

29容器_TreeSet_TreeSet容器的使用

TreeSet实现了Set接口，它是一个可以对元素进行排序的容器。底层实际是用TreeMap实现的，内部维持了一个简化版的TreeMap，通过key来存储元素。 TreeSet内部需要对存储的元素进行排序，因此，我们需要给定排序规则。

排序规则实现方式：

• 通过元素自身实现比较规则。
• 通过比较器指定比较规则。

public class TreeSetTest {
    public static void main(String[] args) {
        //实例化TreeSet
        Set set = new TreeSet<>();
        //添加元素
        set.add("c");
        set.add("a");
        set.add("d");
        set.add("b");
        set.add("a");


        //获取元素
        for(String str :set){
            System.out.println(str);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

String类中有compareTo比较函数

30容器_Set_TreeSet通过元素自身实现比较规则

在元素自身实现比较规则时，需要实现Comparable接口中的compareTo方法，该方法中用来定义比较规则。TreeSet通过调用该方法来完成对元素的排序处理。

创建Users类

public class Users implements Comparable{
    private String username;
    private int userage;


    public Users(String username, int userage) {
        this.username = username;
        this.userage = userage;
    }


    public Users() {
    }


    @Override
    public boolean equals(Object o) {
        System.out.println("equals...");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;


        Users users = (Users) o;


        if (userage != users.userage) return false;
        return username != null ? username.equals(users.username) : users.username == null;
    }


    @Override
    public int hashCode() {
        int result = username != null ? username.hashCode() : 0;
        result = 31 * result + userage;
        return result;
    }


    public String getUsername() {
        return username;
    }


    public void setUsername(String username) {
        this.username = username;
    }


    public int getUserage() {
        return userage;
    }


    public void setUserage(int userage) {
        this.userage = userage;
    }


    @Override
    public String toString() {
        return "Users{" +
                "username='" + username + '\'' +
                ", userage=" + userage +
                '}';
    }


    //定义比较规则
    //正数：大，负数：小，0：相等
    @Override
    public int compareTo(Users o) {
        if(this.userage > o.getUserage()){
            return 1;
        }
        if(this.userage == o.getUserage()){
           return this.username.compareTo(o.getUsername());
        }
        return -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
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

Set set1 = new TreeSet<>();
Users u = new Users("oldlu",18);
Users u1 = new Users("admin",22);
Users u2 = new Users("sxt",22);
set1.add(u);
set1.add(u1);
set1.add(u2);
for(Users users:set1){
    System.out.println(users);
}

1
2
3
4
5
6
7
8
9
10
11

31容器_ TreeSet _通过比较器实现比较规则

通过比较器定义比较规则时，我们需要单独创建一个比较器，比较器需要实现Comparator接口中的compare方法来定义比较规则。在实例化TreeSet时将比较器对象交给TreeSet来完成元素的排序处理。此时元素自身就不需要实现比较规则了。

创建Student类

public class Student {
    private String name;
    private int age;


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


    public Student() {
    }


    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", 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;


        Student student = (Student) o;


        if (age != student.age) return false;
        return name != null ? name.equals(student.name) : student.name == null;
    }


    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

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
63
64
65
66

创建比较器

public class StudentComparator implements Comparator {


    //定义比较规则
    @Override
    public int compare(Student o1, Student o2) {
        if(o1.getAge() > o2.getAge()){
            return 1;
        }
        if(o1.getAge() == o2.getAge()){
            return o1.getName().compareTo(o2.getName());
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class TreeSetTest3 {
    public static void main(String[] args) {
        //创建TreeSet容器，并给定比较器对象
        Set set = new TreeSet<>(new StudentComparator());
        Student s = new Student("oldlu",18);
        Student s1 = new Student("admin",22);
        Student s2 = new Student("sxt",22);
        set.add(s);
        set.add(s1);
        set.add(s2);
        for(Student student:set){
            System.out.println(student);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

32容器_ TreeSet_底层源码分析

成员变量

/**
 * The backing map.
 */
private transient NavigableMap m;


// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

1
2
3
4
5
6
7
8
9

构造方法

public TreeSet() {
    this(new TreeMap());
}

1
2
3
4

添加元素

/**
 * Adds the specified element to this set if it is not already present.
 * More formally, adds the specified element e to this set if
 * this set contains no element e2 such that
 * (e==null ? e2==null : e.equals(e2)).
 * If this set already contains the element, the call leaves the set
 * unchanged and returns false.
 *
 * @param e element to be added to this set
 * @return true if this set did not already contain the specified
 * element
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16