JavaSE学习笔记 - Collection集合

• 集合是一种容器，可以用来存储对象。在数组中存储对象是长度一旦确定是不能改变的，但是集合的长度是可变的。
• 集合中存储的都是 Java 对象的引用，集合不能存储基本数据类型。

集合继承结构图

Collection

• 单列集合类的父接口

public class Main {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("abc");
        collection.add("abc");
        collection.add("bcd");
        Object[] objs = collection.toArray();
        for (int i = 0; i < objs.length; i++) {
            System.out.print(objs[i] + " ");//abc abc bcd 
        }
        System.out.println();
        System.out.println(collection.contains("abc"));//true
        System.out.println(collection.size());//3
        System.out.println(collection.isEmpty());//false
        System.out.println(collection.remove("abc"));//true
        System.out.println(collection);//[abc, bcd]
        collection.clear();
        System.out.println(collection.size());//0
    }
}

contains()

• 通过下列源码可以看出，在判断是否包含这个某一个对象的时候，底层使用了 equals 方法，由于 String 类重写了 equals 方法，所以可以直接判断出是否包含某一个字符串，如果判断自定义的 Java 对象的话，就需要重写 equals 方法来按照自己写的规则来判断集合中是否存在某一个对象。equals 方法默认比较的是对象的引用，所以如果不重写 equals 方法，该方法则返回 false。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
               return i;
    }
    return -1;
}

remove()

• 通过源代码可以发现，remove 底层也是使用了 equals 方法，所以在删除自定义类型的对象的时候如果使用此方法需要重写 equals 方法，并且这个方法在删除对象的时候只会删除第一个出现的对象。

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

Iterator

• 遍历集合中的元素，此接口在使用的时候需要 Colletion 通过 iterator 方法来获取迭代器对象，使用这个接口的 hasNext 方法可以判断是否还有可以迭代的对象，如果有则返回 true，否则返回 false。如果还有可以迭代的对象，我们就可以使用 next 方法迭代出下一个元素。如果我们想要删除迭代器中的某一个对象，那么就需要通过迭代器中的 remove 方法来删除。在操作迭代器的时候，我们无法通过集合来删除元素，因为一旦集合的结构发生了改变我们就需要获取新的迭代器来迭代对象，否则就会发生异常。
• 我们也可以使用增强 for 循环来遍历迭代器中的元素，这个循环没有下标

public class Main {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("abc");
        collection.add("abc");
        collection.add("bcd");

        for (String string : collection) {
            System.out.print(string + " ");//abc abc bcd
        }
        System.out.println();
        
        Iterator<String> it = collection.iterator();
        while (it.hasNext()) {
            String string = it.next();
            //java.util.ConcurrentModificationException
            //通过集合来删除了元素
            //集合结构一旦发生改变就需要重新获取迭代器
            collection.remove(string);
            System.out.print(string + " ");
        }
        System.out.println();
        System.out.println(collection);

        while (it.hasNext()) {
            String string = it.next();
            it.remove();
            System.out.print(string + " ");//abc abc bcd
        }
        System.out.println();
        System.out.println(collection);//[]通过迭代器全部删除
        
    }
}

List

• List 集合中出现的元素是可以重复的，所有的元素都是以线性的方式存储的，可以通过执行的索引来访问其中的元素
• 有序可重复：有序指的是存入的顺序和取出的顺序是相同的，允许存储重复的元素

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("a");
        list.add("b");
        list.add("b");
        list.add("c");
        System.out.println(list);//[a, a, b, b, c]

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");//a a b b c
        }
        System.out.println();

        list.set(0, "d");
        System.out.println(list); //[d, a, b, b, c]

        list.remove(0);
        System.out.println(list);//[a, b, b, c]

        System.out.println(list.indexOf("b"));//1
        System.out.println(list.lastIndexOf("b"));//2
    }
}

Stack

• 继承自 Vector，扩容机制和 Vector 相同，这个类不经常使用。

Vector

• 底层是数组，方法上都有 synchronized，线程安全的，所以相比于 ArrayList 效率较低，用法和 ArrayList 一样，所以这个类不经常使用。
• 初始化容量为 10，建议使用预估计值给 Vector 一个初始容量，原因与 ArrayList 一样，减少扩容的次数，提高程序的执行效率。

protected Object[] elementData;

public Vector() {
    this(10);
}

扩容

• 从扩容的源码中可以找到如下代码，int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);，在 Vector 进行扩容时，新的容量是旧的容量的 2 倍。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList

• 底层是 final 修饰的 Object 数组，查询快，增删慢。查询快是因为在数组中我们有了首地址和元素下标就可以通过表达式快速的计算出某一个位置的内存地址。
• 使用较为频繁，如果不指定容量，初始化容量为 10，但是我们在使用的时候最好给一个预估计的容量，这个可以减少扩容(下面解释)的次数，增加程序的执行效率。
• ArrayList 不能存储大量的数据，因为在内存中不好找到很多连续的内存空间地址。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

扩容

• 在扩容机制的源码中我们可以看到 int newCapacity = oldCapacity + (oldCapacity >> 1);，如果容量不够的时候，新容量是是原来容量的 1.5 倍。底层通过创建一个新的 Object 的数组，然后使用 System.arraycopy 将原来的数组的元素拷贝到新的数组中，原来的数组会被垃圾回收机制销毁。由于底层使用的是数组拷贝，所以在使用这个集合的时候如果不指定容量，那么扩容机制将会是程序的执行时间变长，会增加程序的执行效率，所以在使用这个集合的时候最好预估计一个容量。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

LinkedList

• 底层是双向链表，内存地址不连续，查询慢，增删快

public boolean add(E e) {
    linkLast(e);
    return true;
}

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

双向链表添加内存分析图

• 第一次调用 add 方法
  
• 第二次调用 add 方法
  
• 第三次调用 add 方法
  

常用方法

public class Main {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("a");
        linkedList.add("b");
        linkedList.add("c");
        System.out.println(linkedList);//[a, b, c]
        linkedList.addFirst("d");//[d, a, b, c]
        System.out.println(linkedList);//d
        System.out.println(linkedList.getFirst());//c
        System.out.println(linkedList.getLast());//d
        System.out.println(linkedList.remove());//d
        System.out.println(linkedList.removeFirst());//a
        System.out.println(linkedList);//[b, c]
        linkedList.pop();
        System.out.println(linkedList);//[c]
        linkedList.push("d");
        System.out.println(linkedList);//[d, c]
    }
}

Set

• 无序不可重复：无序是指存入的顺序和取出的顺序不一致，且存入的元素是不可重复的。
• 没有索引，所以不能使用普通的 for 循环遍历，使用迭代器遍历或者增强 for 来遍历

public class Main {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(2);
        set.add(4);
        set.add(3);
        System.out.println(set);//[1, 2, 3, 4]

        for (Integer integer : set) {
            System.out.print(integer + " ");//1 2 3 4 
        }
        System.out.println();

        Iterator<Integer> it = set.iterator();
        while (it.hasNext()) {
            Integer integer = it.next();
            System.out.print(integer + " ");//1 2 3 4 
        }
        System.out.println();

        List<Integer> list = new ArrayList<>(set);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");//1 2 3 4 
        }
        System.out.println();
    }
}

HashSet

• HashMap 和 TreeMap 的介绍
• 底层是 HashMap，HashSet 是将元素放入了 HashMap 的 Key 部分。

public HashSet() {
    map = new HashMap<>();
}

• 在看完了 HashMap 之后我们知道，HashMap 的初始化容量为 16，默认加载因子为 0.75，在进行扩容的时候每次都在原来容量的基础上乘 2，在指定容量的时候必须是 2 的倍数。HashSet 也是如此，在 HashSet 底层就是将元素放入了 HashMap 和 Key 的部分，如果把元素放入哈希表的时候，首先需要将元素的哈希值转换为下标值，如果当前下标有元素，则使用当前元素和单向链表上面的结点的 Key 值进行比较，如果最终没有相同的 Key 值就让这个 Key 放入链尾，如果有则覆盖 Key 值。所以使用 HashSet 存储自定义的类时需要重写 hashCode 和 equals 方法，这个才能让 HashSet 的存取效率更加的高效。

public class Main {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        set.add(new Person("abc"));
        set.add(new Person("abc"));
        set.add(new Person("abb"));
        set.add(new Person("acc"));
        System.out.println(set);//[Person{name='abc'}, Person{name='abb'}, Person{name='acc'}]
    }
}

TreeSet

• HashMap 和 TreeMap 的介绍
• 底层是 TreeMap，TreeSet 是将元素放入了 TreeMap 的 Key 部分。TreeMap 底层使用了平衡二叉树的数据结构，我们可以对 TreeMap 的 Key 按照一定的规则排序，也就是说我们可以对 TreeSet 中的 Key 值进行排序，在存储自定义类的时候我们必须要自定义一个排序的规则，否则程序就是抛出异常。排序方式和 TreeMap 相同，有两种方式对 TreeSet 中的元素进行排序。
• 元素可以自动排序，需要重写某些方法

public TreeSet() {
    this(new TreeMap<E,Object>());
}

自定义比较器

public class Person {
    String name;
    public Person() {
    }

    public Person(String name) {
        this.name = name;
    }

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(name, person.name);
    }

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

public class Main {
    public static void main(String[] args) {
        Set<Person> set = new TreeSet<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                return o1.name.compareTo(o2.name);
            }
        });
        set.add(new Person("abc"));
        set.add(new Person("abc"));
        set.add(new Person("abb"));
        set.add(new Person("acc"));
        System.out.println(set);//[Person{name='abb'}, Person{name='abc'}, Person{name='acc'}]
    }
}

自定义类实现 Comparable 接口

public class Person implements Comparable<Person>{
    String name;
    public Person() {
    }

    public Person(String name) {
        this.name = name;
    }

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(name, person.name);
    }

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

    @Override
    public int compareTo(Person o) {
        return 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Set<Person> set = new TreeSet<>();
        set.add(new Person("abc"));
        set.add(new Person("abc"));
        set.add(new Person("abb"));
        set.add(new Person("acc"));
        System.out.println(set);//[Person{name='abb'}, Person{name='abc'}, Person{name='acc'}]
    }
}

Queue

LinkedList

• 上面已经做了叙述

ArrayDeque

• 底层使用了可变的数组，初始化容量为 16，也可以对容量进行预估计。由于和 LinkedList 一样都是继承自 Deque 接口，所以常用方法和 LinkedList 一样。

扩容

• 从 int newCapacity = n << 1; 可以看出，在扩容时新的容量是原来容量的 2 倍。扩容的时候也是开了一个新的数组，将旧的数组的元素拷贝到新的数组，垃圾回收器在一定的时间自动回收旧数组。

public boolean add(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

PriorityQueue

• 底层使用了数组的形式来存储数据，逻辑上是二叉堆，和 TreeMap 一样，在使用 PriorityQueue 的时候需要实现 Comparable 接口方法。下面源码中使用了 Integer 这个类，它已经实现了 Comparable 接口，如果是我们自定义的类，在使用 PriorityQueue 时，我们需要实现 Comparable 来按照我们自己的规则进行排序。在使用自定义的比较器的时候我们不需要实现 Comparator 接口。
• 在我们自定义对象的时候如果要按照我们使用的规则来排序，那么在这个类上实现 Comparable 接口
• 如果我们在定义 PriorityQueue 想要改变某种排序规则，那么我们就可以使用 Comparator 的匿名内部类定义一个新的排序规则。

public class Main {
    public static void main(String[] args) {
        //在不指定排序规则的时候默认是小根堆
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        queue.add(1);
        queue.add(3);
        queue.add(2);

        System.out.println(queue.peek());
        while (!queue.isEmpty()) {
            System.out.print(queue.poll() + " "); //3 2 1
        }

    }
}

• 初始化容量为 11

transient Object[] queue; // non-private to simplify nested class access

public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

• 扩容：int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));，从源码中我们可以看出，这个二叉堆在 6 层以内的时候，新的容量是旧的容量 + 2，在大于 6 层的时候，新的容量 = 旧容量 + 旧 容量 >> 1，也就是扩容为原来的 1.5 倍。

public boolean add(E e) {
   return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

Collections工具类

常用方法

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("abc");
        list.add("bcd");
        list.add("acd");
        Collections.addAll(list, "a", "b", "c");
        System.out.println(list);//[abc, bcd, acd, a, b, c]

        Collections.shuffle(list);//打乱顺序
        System.out.println(list);//[acd, b, bcd, a, c, abc]
    }
}

排序

• 底层使用了快速排序算法，Collections 不能对 Set 集合排序，如果想要排序需要把 Set 集合转换为 List 集合，然后进行排序或者自定义排序即可。被排序的对象必须要实现 Comparable 接口。

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("abc");
        list.add("bcd");
        list.add("acd");
        Collections.addAll(list, "a", "b", "c");

        Collections.sort(list);
        System.out.println(list);//[a, abc, acd, b, bcd, c]
    }
}

自定义排序

• 实现 Comparable

public class Main {
    public static void main(String[] args) {
        List<Person> list = new ArrayList<>();
        Collections.addAll(list, new Person(1, "a"), new Person(3, "b"), new Person(2, "c"));
        System.out.println(list);//[Person{no=1, name='a'}, Person{no=3, name='b'}, Person{no=2, name='c'}]
        Collections.sort(list);
        System.out.println(list);//[Person{no=1, name='a'}, Person{no=2, name='c'}, Person{no=3, name='b'}]

        //使用比较器自定义规则
        Collections.sort(list, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                return o2.no - o1.no;
            }
        });
        System.out.println(list);//[Person{no=3, name='b'}, Person{no=2, name='c'}, Person{no=1, name='a'}]
    }
}

• 自定义比较器

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(3);
        list.add(5);
        Collections.addAll(list, 2, 4, 6);

        //默认升序
        Collections.sort(list);
        System.out.println(list);//[1, 2, 3, 4, 5, 6]

        //自定义比较器变为降序
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        System.out.println(list);//[6, 5, 4, 3, 2, 1]
    }
}