Java collection 集合

Java collection 集合

一、集合框架概述

1.1 概念

集合和数组都是对多个数据进行操作的结构，叫做java容器。

1.2 数组存储数据的特点

一旦初始化之后，其长度就确定了
一旦定义好之后，其数据类型就确定了，比如int[]、String[]

1.3 数组存储元素的弊端

一旦初始化以后，其长度不可修改
数组中提供的方法非常有限，对于插入、删除、添加数据等操作非常不便，同时效率不高
获取数组中实际元素的个数，数组没有现成的方法或属性可用
数组存储数据的特点是有序的、可重复的，对于无序、不可重复的需求、不能满足

1.4 Java集合

Java集合可分为Collections和Map两种体系。

Collection接口：单列集合，定义了存取一组对象的方法的集合

List：元素有序，可重复的集合
set：元素无序，不可重复的集合

Map接口：双列集合，保存具有key-value 的集合

二、Collection 接口方法

方法：

Modifier and Type	Method and Description
`boolean`	`add(E e)` 确保此集合包含指定的元素（可选操作）。
`boolean`	`addAll(Collection<? extends E> c)` 将指定集合中的所有元素添加到此集合（可选操作）。
`void`	clear() 从此集合中删除所有元素（可选操作）。
`boolean`	`contains(Object o)` 如果此集合包含指定的元素，则返回 `true` 。
`boolean`	`containsAll(Collection<?> c)` 如果此集合包含指定 `集合`中的所有元素，则返回true。
`boolean`	`equals(Object o)` 将指定的对象与此集合进行比较以获得相等性。
`int`	`hashCode()` 返回此集合的哈希码值。
`boolean`	`isEmpty()` 如果此集合不包含元素，则返回 `true` 。
`Iterator<E>`	`iterator()` 返回此集合中的元素的迭代器。
`default Stream<E>`	`parallelStream()` 返回可能并行的 `Stream`与此集合作为其来源。
`boolean`	`remove(Object o)` 从该集合中删除指定元素的单个实例（如果存在）（可选操作）。
`boolean`	`removeAll(Collection<?> c)` 删除指定集合中包含的所有此集合的元素（可选操作）。
`default boolean`	`removeIf(Predicate<? super E> filter)` 删除满足给定谓词的此集合的所有元素。
`boolean`	`retainAll(Collection<?> c)` 仅保留此集合中包含在指定集合中的元素（可选操作）。
`int`	`size()` 返回此集合中的元素数。
`default Spliterator<E>`	`spliterator()` 创建一个`Spliterator`在这个集合中的元素。
`default Stream<E>`	`stream()` 返回以此集合作为源的顺序 `Stream` 。
`Object[]`	`toArray()` 返回一个包含此集合中所有元素的数组。
`<T> T[]`	`toArray(T[] a)` 返回包含此集合中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。

public class TestCollection {
    @Test
    public void test(){
        // add(E e)
        Collection col = new ArrayList();
        col.add("AA");
        col.add("BB");
        col.add(11);
        col.add(new Date());
        System.out.println(col);
        //获取元素个数
        System.out.println(col.size());
        Collection col1 = new ArrayList();
        col.add("CC");
        col.add("DD");
        col.add(22);
        //将集合添加到集合中
        col.addAll(col1);
        System.out.println(col);
        //清空元素
        col.clear();
        //判断元素是否为空
        System.out.println(col.isEmpty());
    }
}

三、Iterator迭代器接口

1.1 迭代器概念

在程序开发中，经常需要遍历集合中的所有元素。针对这种需求，JDK专门提供了一个接口java.util.Iterator。Iterator接口也是Java集合中的一员，但它与Collection、Map接口有所不同，Collection接口与Map接口主要用于存储元素，而Iterator主要用于迭代访问（即遍历）Collection中的元素，因此Iterator对象也被称为迭代器。

1.2 Iterator方法

Modifier and Type	Method and Description
`default void`	`forEachRemaining(Consumer<? super E> action)` 对每个剩余元素执行给定的操作，直到所有元素都被处理或动作引发异常。
`boolean`	`hasNext()` 如果迭代具有更多元素，则返回 `true` 。
`E`	`next()` 返回迭代中的下一个元素。
`default void`	`remove()` 从底层集合中删除此迭代器返回的最后一个元素（可选操作）。

代码演示：

public class TestIterator {
    @Test
    public void test(){
        Collection col = new ArrayList();
        col.add("AA");
        col.add("BB");
        col.add(11);
        col.add(new Date());
        Iterator iterator = col.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

remove：

public class TestIterator {
    @Test
    public void test(){
        Collection col = new ArrayList();
        col.add("AA");
        col.add("BB");
        col.add(11);
        col.add(16);
        col.add(21);
        col.add(new Date());
        Iterator iterator = col.iterator();
        while (iterator.hasNext()){
            Object o = iterator.next();
            if("16"==String.valueOf(o)){
                iterator.remove();
            }
        }
        Iterator iterator1 = col.iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }
    }
}

1.3 Iterator迭代器的执行原理

错误代码：

        Iterator iterator = col.iterator();
        //错误方式1
        while (iterator.next()!=null){
            System.out.println(iterator.next());
        }
        //错误方式2
        while (col.iterator().hasNext()){
            System.out.println(col.iterator().next());
        }

四、List

1.1 List 接口

存储有序的，可重复的数据,List 除了从 Collection 集合继承的方法外， List 集合里添加了一些根据索引来操作集合元素的方法。

void add(int index, Object ele) 在 index 位置插入 ele 元素
boolean addAll (int index, Collection eles) 从 index 位置开始将 eles 中的所有元素添加进来
Object get( int index): 获取指定 index 位置的元素
int indexOf (Object obj) 返回 obj 在集合中首次出现的位置
int lastIndexOf (Object obj) 返回 obj 在当前集合中末次出现的位置
Object remove( int index): 移除指定 index 位置的元素，并返回此元素
Object set( int index, Object ele) 设置指定 index 位置的元素为 ele
List subList (int fromIndex , int toIndex) 返回从 fromIndex 到 toIndex位置的子集合

1.2 ArrayList

作为list的主要实现类，线程不安全，效率高，底层是使用Object[] elementData实现的。

源码扩容问题：

    transient Object[] elementData; //初始化一个空的数组
    /**
     * Constructs an empty list with an initial capacity of ten. 构建
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
*******************扩容源码*************************************************
    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!  size 为list中元素个数
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    //
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //如果当前数组为空，返回DEFAULT_CAPACITY=10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity; //当前数组不为空，为size+1
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code  
        if (minCapacity - elementData.length > 0)  //未扩容前 elementData.length=10
            grow(minCapacity);  //--->扩容
    }
    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; //原来数组的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1); //向右移位操作，变为原来的1.5倍
        if (newCapacity - minCapacity < 0)  //如果新的数组容量newCapacity小于传入的参数要求的最小容量minCapacity，那么新的数组容量以传入的容量参数为准。
            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); //copy数组元素到新的扩容后的数组
    }

1.3 LinkedList

对于频繁插入和删除，使用此类效率比ArrayList高，底层是使用双向链表的结构实现的。

新增方法：

void addFirst (Object obj) 在该列表开头插入指定元素
void addLast (Object obj) 将指定元素追加到该列表末尾
Object getFirst() 返回此列表中第一个元素
Object getLast() 返回此列表中最后一个元素
Object removeFirst() 从此列表中删除并返回第一个元素
Object removeLast() 从此列表删除并返回最后一个元素

源码：

    //存储数据的结构node    
    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;
        }
    }
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
//**************************添加元素**************************************
    /**
     * Appends the specified element to the end of this list.
     *
     * <p>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<E> l = last; //最后一个元素，如果第一次添加为null
        final Node<E> newNode = new Node<>(l, e, null); //添加一个新元素
        last = newNode; //这个新的元素结构就是链条的最后一个了
        if (l == null) //如果为null，说明第一次添加元素
            first = newNode; 
        else
            l.next = newNode; //不是第一次添加，那就是链条的最后了
        size++;
        modCount++;
    }

1.4 Vector

作为list接口的古老实现类，线程安全的，底层是使用Object[] elementData实现的。

实例化为长度为10的数组，扩容为原来的2倍。

五、Set

Set接口：存储无序的、不可重复的数据

1.1 HashSet

作为Set接口的主要实现类，线程不安全的，可以存储null
HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能
HashSet 集合判断两个元素相等的标准两个对象通过 hashCode () 方法比较相等，并且两个对象的 equals() 方法返回值也相等
对于存放在 Set 容器中的对象，对应的类一定要重写 equals 和 hashCode(Objectobj) 方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码 “。

HashSet存储图解：

1.2 LinkedHashSet

作为HashSet的子类，遍历内部数据时，可以按照添加的顺序遍历

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

底层结构图解：

1.3 TreeSet

可以按照添加指定对象的属性，进行排序。

TreeSet 是 SortedSet 接口的实现类， TreeSet 可以确保集合元素处于排序状态。
TreeSet 底层使用红黑树结构存储数据。
TreeSet 两种排序方法：自然排序和定制排序。默认情况下， TreeSet采用自然排序。

排序：

自然排序：

TreeSet 会调用集合元素的 compareTo (Object obj ) 方法来比较元素之间的大小关系，然后将集合元素按升序默认情况排列。
如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable接口。实现 Comparable 的类必须实现 compareTo (Object obj ) 方法，两个对象即通过compareTo (Object obj ) 方法的返回值来比较大小。
因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是同一个类的对象。

定制排序：

要实现定制排序，需要将实现 Comparator 接口的实例作为形参传递给 TreeSet 的构造器。

    @Test
    public void test2(){
        TreeSet set = new TreeSet(new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Person)o1).getAge() - ((Person)o2).getAge();
            }
        });
        set.add(new Person("小明",19));
        set.add(new Person("小x",20));
        set.add(new Person("小g",34));
        set.add(new Person("小b",65));
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

1.4 理解Set的无序性

无序性：不代表随机性

六、Map

1.1 Map接口继承树

1.2 Map接口概述

Map与Collection并列存在。用于存储具有映射关系的数据：key-value

常用方法：

添加、删除、修改操作：

Object put(Object key,Object value) ：将指定 key value 添加到或修改当前 map 对象中
void putAll(Map m): 将 m 中的所有 key value 对存放到当前 map 中
Object remove(Object key)：移除指定 key 的 key value 对，并返回 value
void clear()：清空当前 map 中的所有数据

元素查询的操作：

Object get(Object key) ：获取指定 key 对应的 value
boolean containsKey(Object key) ：是否包含指定的 key
boolean containsValue(Object value)：是否包含指定的 value
int size()：返回 map 中 key value 对的个数
boolean isEmpty()：判断当前 map 是否为空
boolean equals(Object obj) ：判断当前 map 和参数对象 obj 是否相等

元视图操作的方法：

Set keySet()：返回所有 key 构成的 Set 集合
Collection values()：返回所有 value 构成的 Collection 集合
Set entrySet()：返回所有 key value 对构成的 Set 集合

1.3 HashMap

HashMap 是 Map 接口使用频率最高的实现类。

JDK 7及以前版本： HashMap 是数组+链表结构即为链地址法。

JDK 8版本发布以后： HashMap 是数组+链表+红黑树实现。

HashMap中的内部类：

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

1.4 LinkedHashMap

LinkedHashMap 是 HashMap 的子类。
在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。
与 LinkedHashSet 类似 LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key V alue 对的插入顺序一致。

LinkedHashMap中的内部类： Entry

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

1.5 Properties

Properties 类是 Hashtable 的子类，该对象用于处理属性文件.

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);

七、Collections工具类

常用方法：

max(Collection<? extends T> coll) 根据其元素的 自然顺序返回给定集合的最大元素。
max(Collection<? extends T> coll, Comparator<? super T> comp) 根据指定的比较器引发的顺序返回给定集合的最大元素。
reverse(List<?> list) 反转指定列表中元素的顺序
sort(List<T> list) 根据其元素的natural ordering对指定的列表进行排序。
sort(List<T> list, Comparator<? super T> c) 根据指定的比较器引起的顺序对指定的列表进行排序。
copy(List<? super T> dest, List<? extends T> src) 将所有元素从一个列表复制到另一个列表中。
frequency(Collection<?> c, Object o) 返回指定集合中与指定对象相等的元素数。

Java collection 集合

Java collection 集合

一、集合框架概述

1.1 概念

1.2 数组存储数据的特点

1.3 数组存储元素的弊端

1.4 Java集合

二、Collection 接口方法

三、Iterator迭代器接口

1.1 迭代器概念

1.2 Iterator方法

1.3 Iterator迭代器的执行原理

四、List

1.1 List 接口

1.2 ArrayList

1.3 LinkedList

1.4 Vector

五、Set

1.1 HashSet

1.2 LinkedHashSet

1.3 TreeSet

1.4 理解Set的无序性

六、Map

1.1 Map接口继承树

1.2 Map接口概述

1.3 HashMap

1.4 LinkedHashMap

1.5 Properties

七 、Collections工具类

七、Collections工具类