尚硅谷_Java零基础教程-java入门必备-初学者基从入门到精通全套完整版(宋红康主讲) P513-564

文章目录

1. JAVA集合框架概述
2. Collection接口方法
3. Iterator迭代器接口
4. Collection子接口一：List
- ArrayList源码分析
- LinkedList源码分析
- List接口中常用方法
5. Collection子接口二：Set
- *hashCode()的重写
- LinkedHashSet
- TreeSet
6. Map接口
- HashMap底层实现
- - jdk7
  - jdk8
- HashMap底层源码分析——jdk7
- HashMap底层源码分析——jdk8
- LinkedHashMap底层实现
- Properties
7. Collections工具类
- 操作List
- 同步控制

1. JAVA集合框架概述

一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊端，而java集合就像一种容器，可以动态地把多个对象的引用放入容器中。
- 数组在内存存储方面的特点：
  - 数组初始化之后，长度就确定了。
  - 数组声明的类型，就决定了进行元素初始化时的类型
- 数组在存储数据方面的弊端：
  - 长度不可变，不便于扩展。
  - 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时无法直接获取存储元素的个数。
  - 数组存储的数据是有序的、可以重复的。——存储数据的特点单一。
JAVA集合类可以用于存储数量不等的多个对象，还可以用于保存具有映射关系的关联数组。
集合的使用场景，例如：
- JSON对象或JSON数组（客户端）<==>Java对象或Java对象构成的List（服务器端）
Java集合可分为Collection和Map两个体系

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

|---- List：元素有序、可重复

|---- Set：元素无序、可重复

|---- Map接口：双列数据，保存具有映射关系的“key-value”键值对的集合。

|---- HashMap, LinkedHashMap, TreeMap, Hashtable, Properties

随记——java基础——集合——202006141. JAVA集合框架概述2. Collection接口方法3. Iterator迭代器接口4. Collection子接口一：List5. Collection子接口二：Set6. Map接口7. Collections工具类

2. Collection接口方法

package java.util;

import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;



public interface Collection<E> extends Iterable<E> {
    // Query Operations

    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);

    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);

    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

contains调用的是equals方法。
retainAll求交集
equals方法要求当前集合和形参集合的元素都相同。
数组–>集合： Arrays.asList()；
- Arrays.asList(new int[]{123,456}) //size()=1，识别为一个元素，类型为int[]
- Arrays.asList(new Integer[]{123,456}) //size()=2，识别为两个元素

3. Iterator迭代器接口

Iterator对象被称为迭代器（设计模式的一种），主要用于遍历Collections集合中的元素。
GOF给迭代器模式的定义为：提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。
类似“公交上的售票员”
Collection接口继承了java.lang.Iterable接口，该接口有一个iterate()方法，那么所有实现了Collection接口的集合类都有一个iterate()方法，用以返回一个实现了Iterator接口的对象。
Iterator仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator对象，则必须有一个被迭代的集合。
集合对象每次调用iterate()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Iterator iterator = collection.iterator();
        while (iterator.hasNext()){
            //next():1.指针下移 2.将下移后指向的元素返回
            System.out.println(iterator.next());
        }

错误方式一：

while (iterator.next()!=null){
            System.out.println(iterator.next());
        }

错误方式二：死循环

while (collection.iterator().hasNext()){
            System.out.println(collection.iterator());
        }

remove()方法
- Iterator 可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove方法，而不是集合对象的remove方法。
- 如果还未调用next()或在上一次调用next方法之后以及调用了remove方法，再调用remove会报 IllegalStateException

例如：

while (iterator.hasNext()){
            //next():1.指针下移 2.将下移后指向的元素返回
            System.out.println(iterator.next());
            iterator.remove();
            iterator.remove();
        }

foreach内部调用了迭代器。

注意:

String[] arr = new String[]{"MM","MM","MM"};

//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = "GG";
//        }//[GG, GG, GG]

        for (String s: arr) {
            s = "GG";
        }//[MM, MM, MM]

        System.out.println(Arrays.toString(arr));

4. Collection子接口一：List

鉴于java中数组用来存储数据的局限性，通常使用List替代数组。
List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
List接口实现类常用的有：ArrayList，LinkedList，Vector（？常用）
- Vector底层使用Object[]数组，线程安全
- ArrayList底层使用Object[]数组
- LinkedList底层使用双向链表

ArrayList源码分析

ArrayList扩容机制（jdk7）
- 空参构造器创建一个为10的Object[]数组elementData
- 当添加元素使得当前size == elementData.length时，扩容为原来数组的1.5倍，将原来数组的元素copy到新数组。
ArrayList扩容机制（jdk8）
- 空参构造器，elementData初始化为{}
- 第一次调用add()时，底层才创建了长度为10的数组，并将add的数据添加到位置上。
- 后续扩容与jdk7无异
“相当于”从饿汉式变成懒汉式。
jdk9源码：

初始化（空参构造器）：

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};

添加元素

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

调用内部add：

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

扩容：

private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

调用内部扩容：

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5倍
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

LinkedList源码分析

空参构造器：first和last都为null
add() 和addLast()都调用内部linkLast()（linkFirst与之对应）

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++;
    }

Vector底层创建长度为10的数组。扩容为2倍。

List接口中常用方法

subList(int fromIndex,int toIndex)：类似substring，返回一个子list
常用：增删改查、遍历
注意：
- list.remove(2) ：删除下标为2的元素
- list.remove(new Integer(2)) 删除元素2

5. Collection子接口二：Set

|---- Set接口

|---- HashSet：线程不安全，可以存储null值

|----LinkedHashSet：可以按照添加的顺序遍历

|----TreeSet：可以排序

Set接口中没有定义额外的方法。
无序性：不等于随机性，存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据hash值决定。
不可重复性：equals判断
向set中添加的数据，其所在的类一定要重写equals和hashcode方法。并且重写的equals和hashcode方法尽可能保持一致性。

*hashCode()的重写

重写hashCode()的基本原则：

在程序运行时，同一个对象多次调用hashCode()返回相同的值
当两个对象equals()方法返回true时，这两个对象的hashCode()的返回值也应相等。
对象中用作equals()比较的Field，都应该用来计算hashCode值。

代码示例：

class Enn{
    int id;
    String name;
    
	@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Enn enn = (Enn) o;
        return id == enn.id &&
                Objects.equals(name, enn.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

public static int hash(Object... values) {
        return Arrays.hashCode(values);
    }

public static int hashCode(Object a[]) {
        if (a == null)
            return 0;

        int result = 1;

        for (Object element : a)
            result = 31 * result + (element == null ? 0 : element.hashCode());

        return result;
    }

为什么有31这个数字?

选择系数时要尽可能大，因为计算出来的hash地xiangc址越大，hash冲突的概率就越低。（减少冲突）
31只占用5bits，相乘造成数据溢出的概率较小。
31可以由i<<5-1得到，效率较高。（提升效率）
31是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和1和被乘数的因数整除。（减少冲突）

LinkedHashSet

LinkedHashSet是HashSet的子类。
HashSet底层是用HashMap实现的，其中，所有key的value都指向同一个静态的Object对象。

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

随记——java基础——集合——202006141. JAVA集合框架概述2. Collection接口方法3. Iterator迭代器接口4. Collection子接口一：List5. Collection子接口二：Set6. Map接口7. Collections工具类

TreeSet

向TreeSet添加的对象，要求是相同类的对象

TreeSet treeSet = new TreeSet();
        treeSet.add(1);
        treeSet.add(1l); //报错
        treeSet.add(1.0d);
        treeSet.add(1.0f);
        for (Object o:treeSet         ) {
            System.out.println(o);
        }

报错：

java.lang.ClassCastException

两种排序方式：自然排序和定制排序
- 注意：TreeSet在自然排序和定制排序中，比较两个对象是否相同的标准，compareTo() / compare() 返回0，不再是equals()方法。

6. Map接口

|---- Map接口

|---- HashMap：线程不安全，可以存储null的key和value值

|----LinkedHashMap：可以按照添加的顺序遍历。在原有的hashmap结构上，添加了一对指针，指向前一个和后一个。对于频繁的遍历操作，效率高于hashmap。

|----TreeMap：可以排序。采用红黑树。

|----Hashtable：作为古老的实现类，线程安全，效率低，不可以存储null的key和value值

|----Properties

Map中的key：无序、不可重复，使用Set存储所有的key。——key所在的类要重写equals和hashcode（HashMap，不包括TreeMap）
Map中的value：无序、可重复，使用Collection存储所有的value
Map中的entry：无序、不可重复，使用Set存储所有的entry

HashMap底层实现

jdk7

new HashMap<>()：实例化后，创建一个长度是16的一维数组 Entry<K,V>[] table
map.put(k1,k2)：调用k1所在类的hashCode()计算k1哈希值，此哈希值经过某种算法计算之后，得到在Entry数组中的存放位置。
1. 如果此位置上的数据不为空，则添加数据。
2. 如果不为空，比较key和已经存在的一个或多个数据的hash值：如果都不相同，则添加数据；如果hash值相同，则进一步比较（调用k1的equals方法），如果false，添加成功；如果true，替换该value值。
3. 上面第2步中，添加数据以链表的形式存储。

jdk8

new HashMap<>()：没有创建一个长度是16的一维数组
jdk底层数组是 Node<K,V>[]
首次调用put方法，底层创建长度为16的数组。
底层结构增加了红黑树：当数组某一个索引位置上链表长度超过8时且当前数组长度超过64，则该索引位置上所有数据改为红黑树存储。

HashMap底层源码分析——jdk7

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

调用：

public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                        initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                        loadFactor);

            //Find a power of 2 >= initialCapacity
            int capacity = 1;
            while (capacity<initialCapacity)
                capacity <<= 1;

            this.loadFactor = loadFactor;
            threshold = Math.min(capacity*loadFactor,MAXIMUM_CAPACITY);
            table = new Entry[capacity];
            useAltHashing = sun.misc.VM.isBooted() && 
                    (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
            init();
        }

put()方法：

（略）

addEntry方法：

void addEntry(int hash, K key ,V value, int bucketIndex){
	//超出临界值且要存入的位置非空时
	if((size>=threshold) && (null != table[bucketIndex])){
		resize(2*table.length);
		bucketIndex = indexFor(hash,table.length);
	}
	createEntry(hash,key,value,bucketIndex);
}

resize()方法：扩容

HashMap底层源码分析——jdk8