0826（040天 集合框架05 亿点总结）

0826（040天 集合框架05 亿点总结）

每日一狗（田园犬西瓜瓜）

集合框架05 亿点总结

1. 一些接口

Collection继承于Iterable接口。Iterable定义了对象必须可遍历，可迭代

1.1 Iterable接口

public interface Iterable<T> {

    Iterator<T> iterator();
    
    default void forEach(
        Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}
 6
@FunctionalInterface // 函数式接口，提供lambda表达式写法
public interface Consumer<T> 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.2 Collection

元素可重复，无序

1.3 List

删除元素的二义性：当存储的数据是Integer时，你传一个3进去就是按照指定索引进行取出，但是传入的是一个(Integer)3时候就是按照对象来进行删除，返回是否成功。

E remove(int index)：

boolean remove(Object obj)：

1.4 Set

继承Collection接口，没有特殊方法，元素之间无序唯一

---

2. 一级标题

2.1 forEach结构

能够使用forEach结构遍历的必须要实现Iterable接口

package com.yang1;

import java.util.Iterator;

public class Test01 {

	public static void main(String[] args) {
		A1 a = new A1();
		for(Object t:a) {
			
		}
	}

}

class A1 implements Iterable<Object> {

	@Override
	public Iterator<Object> iterator() {
		
		return null;
	}

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

2.2 ArrayList

扩容时计算容积

minCapacity= 需求最小容积

oldSize = 原始数组容积

newSize = oldSize*3/2 = 新算出来的容积

判定：算出来的newSize 满足minCapacity的最小容积

1. 真：判定：newSize 满足MAX_ARRAY_SIZE内置最大容积
   1. 真：返回 newSize
   2. 假：返回 （newSize>0否异常） 和 Integer.MAX_VALUE之间的最小值
2. 假：
   1. elementData容器是否为初始化空容积时返回默认初始化容积DEFAULT_CAPACITY=10和minCapacity的最大值
   2. minCapacity < 0 时就已经是从Integer.MAX_VALUE容积时还要进行扩展。抛出异常
   3. 返回 minCapacity

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容50%
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // 最大容积时在扩容就没了
            throw new OutOfMemoryError();
        return minCapacity;
    }
    // 新容积满足最小容积
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity // 小于最大容积值时返回
        : hugeCapacity(minCapacity);
}
/15
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 最大容积时在扩容就没了
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE // 最小容积大于最大容积返回Integer.MAX_VALUE 
        : MAX_ARRAY_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

2.3 Vector

构造器

public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
5 将指定数组中的数据中的多少个拷贝到指定类型的数据类型红枣年糕
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

扩容时获取新容积

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? // 扩容步长大于0时按照步长扩容
                                     capacityIncrement : oldCapacity); // 扩容步不大于0则使用100%比例扩容
    if (newCapacity - minCapacity <= 0) { // 新容积不满足最小容积时
        if (minCapacity < 0) // 所需容积是否溢出
            throw new OutOfMemoryError();
        return minCapacity; // 返回扩容长度为最小容积值
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0) // 如果计算出来的新值
        ? newCapacity // 返回新的容积
        : hugeCapacity(minCapacity); // 
}
13
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

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

3. 泛型

解决问题：我在编码的时候也不确定我这个类型应该是什么类型

3.1 应用

class A1<T>{ // 泛型类
    T id;
    void pp(T t){} // 泛型类的成员方法
    
    

}
1
2
3
4
5
6
7

静态方法中不可以使用泛型类中的泛型类，想用就必须在静态方法中再次声明泛型

<T> void pp(T t){} // 泛型实例成员方法
static <T> void dd(T t){} // 泛型静态方法
1
2

通配符 ?

上限 extends

下限 super

下限一般配合通配符不确定参数一起使用

3.2 泛型的擦除与补偿

4. 待整理

4.1 概述ArrayList、LinkedList和Vector的区别

相同点

实现了List接口，元素之间有序可重复。

ArrayList 和 Vector 的底层存储都是数组。

不同点

ArrayList、Vector

主要区别的是Vector的多数方法都是有synchronized修饰的，线程安全的；反之ArrayList线程不安全，并发效率高。

ArrayList的扩容比是1.5倍，而Vector可以设定固定的扩容步长capacityIncrement，在不设定时用的扩容比例是2.0。

扩容容积计算步骤：

1. ArrayList和Vector扩容容积合法性判定基本一致，newCapacity（ke pai sei tei）新容积同时满足minCapacity最小容积和MAX_ARRAY_SIZE最大容积时返回newCapacity；
2. newCapacity不满足minCapacity最小容积时，需要判定minCapacity的合法性。0
3. 当newCapacity也不满足MAX_ARRAY_SIZE要求时，则此时的minCapacity已经相当巨大了，此时需要判定minCapacity应该考虑取用Integer.MAX_VALUE 和MAX_ARRAY_SIZE哪个合适，不管咋选都要最少>=minCapacity

注释：由于ArrayList存在延迟创建的机制，在第2步minCapacity合法性判定时需要多判定一个elementData是否为空数组，是则返回minCapacity和DEFAULT_CAPACITY之间的最大值。

0 > minCapacity 即当所需容积小于0时，当前容积为Integer.MAX_VALUE，在调用grow(size + 1)时数据已经溢出，数组索引使用整形，这里相当于已经数组已经满了，在插入数据会抛出内存溢出错误。

ArrayList在未指定或指定容积为0时会使用延迟创建的方式进行内存优化，Vector未指定容积时默认容积为10。

ArrayList、LinkedList

主要区别在于底层存储，ArrayList用数组进行存储，LinkedList底层存储使用的是双向链表。

在插入删除和检索时二者各有所长，ArrayList检索高效、LinkedList删除插入高效

如何选用

• ArrayList
  • 检索O(1)，插入删除O(n)，线程不安全
  • 适用做数据的高效读取的场景。并发高效
• LinkedList
  • 检索O(n)，插入删除O(1)，线程不安全
  • 用作临时数据常来插入删除数据。并发高效
• Vector
  • 检索O(1)，插入删除O(n)，线程安全
  • 相对于ArrayList来说适用于线程安全的需求

4.2 概述Collection、List和Set接口

Collection

相对于其余二者来说是顶级接口，自身继承于另一个更加抽象的接口Iterable

元素无序、可以重复。定义了一个容器应该满足的一些抽象方法元素的增删改查，容器的遍历，容器的导入与导出，容器清空等等

List

继承Collection，在Collection基础上引入了索引的概念，元素之间

Set

---

扩展小芝士

• 对于可以存储null的容器在实现 remove(Object o) 时需要分支为两部分，一部分来用来判定null，另一分支用于判定非空