集合三大接口
- 编程语言
- 2小时前
- 3热度
- 0评论
参考文献
- List
- Set
- Map
1、什么是Iterable：实现此接口可以让对象成为以for-each循环语句的目标
先看一下Ilerable的源码
public interface Iterable<T> {
// 返回一个内部元素为T类型的顺序迭代器
Iterator<T> iterator();
// JDK1.8新增，方便对内部元素遍历，然后执行一个操作action
default void forEach(Consumer<? super T> action) {
// 验证action是否为null，若为null，抛出NullPointerException
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
// JDK1.8新增 返回一个内部元素为T类型的并行迭代器
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
forEach具体使用
List<Integer> numbers = Arrays.asList(1, 2, 3);
numbers.forEach(integer -> System.out.println(integer));
// 这个和上面的等价，都是输出1 2 3
numbers.forEach(new Consumer<Integer>() {
@Override
public void accept(Integer integer) {
System.out.println(integer);
}
});
只要继承Iterable，就可以让这个类创建的对象用for-each循环输出，为什么可以？因为它实际上还是通过迭代器实现的，所以Iterable继承了Iterator，请看下面例子
// 编译前
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
for (Integer i : list) {
System.out.println(i);
}
// 编译后
List<Integer> list = new ArrayList(Arrays.asList(1, 2, 3));
Iterator var2 = list.iterator();
while(var2.hasNext()) {
Integer i = (Integer)var2.next();
System.out.println(i);
}
通过这个例子我们知道了for-each的本质就是用iterator来实现的。
2、什么是Iterator：顺序遍历迭代器，我们先看下源码
public interface Iterator<E> {
// 判断迭代器遍历的集合还有无元素
boolean hasNext();
// 返回集合里面下一个元素
E next();
// 删除集合里上一次next()方法返回的元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 对剩余的每个元素指定给定操作，直到操作完毕或引发异常
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
forEachRemaining与我们刚才了解的Iterable中的forEach有什么区别呢？
forEachRemaining()方法内部是通过使用迭代器Iterator遍历所有元素，
forEach()方法内部使用的是增强for循环。
forEach()方法可以多次调用，
forEachRemaining()方法第二次调用不会做任何操作，因为不会有下一个元素。
3、Iterable和Iterator有什么关系
- Iterator是迭代器接口，实现此接口的实例可以对元素集合迭代遍历。Iterable是为了只要实现该接口就能使用for-each迭代
- Iterable中封装了Iterator，实现了Iterable就能用Iterator迭代器
- 集合Collection、List、Set都是Iterable的实现类，所以他们及其他们的子类都可以使用foreach进行迭代。
- Iterator的核心方法都依赖当前位置。而当实现Iterable则不然，每次调用都返回一个从头开始的迭代器，各个迭代器之间互不影响。
4、继承了Iterable的Collection
- Collection是接口，其继承了Iterable接口
- Collection属于单值类型集合，重点子接口List接口和Set接口
下面来看源码，基本都是接口，没有实现
public interface Collection<E> extends Iterable<E> {
// 主要方法如下
int size(); // 元素数量
boolean isEmpty();
boolean contains(Object o);// 如果包含元素O则返回为true
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);//删除包含集合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);
}
}
而List和Set继承了Collection
- List：可重复集合，实现类有ArrayList，Vector 和 LinkedList
- Set：不可重复集合，实现类有HashSet 和 TreeSet
先看List源码，这里只看List新增的内容
在看Set源码，Set新增的内容都是collection中的内容。这里直接看collection就可以了。
3.Map接口，主要用的都是前面几个
public interface Map<K,V> {
// Query Operations 查询操作
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
// Modification Operations 修改做
V put(K key, V value);
V remove(Object key);
// Bulk Operations 批量操作
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Views 视图
// 所有key的集合，不能重复
Set<K> keySet();
// 所有value的结合
Collection<V> values();
// 所有键值对的集合，不能重复
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
// @since 1.8 返回一个比较器，比较的规则是key的自然大小
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
// @since 1.8 返回一个比较器，比较规则是value的自然大小
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
// @since 1.8 返回一个比较器，比较规则用cmp参数传入，比较的是key
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
// @since 1.8 返回一个比较器，比较规则用cmp参数传入，比较的是value
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// 还有Comparison and hashing 比较和散列 下面的不怎么用懒得看了
}
List两大实现类：ArrayList 和 LinkedList（还有个Vector不常用）
1. ArrayList
- 继承了AbstractList抽象类，它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
- 实现了List接口
- RandomAccess随机访问接口：提供随机访问功能
- Cloneable 克隆接口：覆盖clone()，能被克隆
- java.io.Serializable 序列化接口：这意味着ArrayList支持序列化，能通过序列化去传输
ArrayList的特点：基本的ArrayList，常常用于随机访问元素，但是在List中间插入和移除元素时较慢。同时，ArrayList的操作不是线程安全的！一般在单线程中才使用ArrayList，而在多线程中一般使用Vector或者CopyOnWriteArrayList。对于这些我们先有一个概念。
ArrayList中的属性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素数组
transient Object[] elementData;
}
ArrayList中的3个构造方法
- ArrayList()：构造一个初始容量为10的空列表，但是数组为空，第一次add的时候才会加数据
- ArrayList(Collection<?extend E> c)：构造一个包含指定元素的列表
- ArrayList(int initialCapcity)：构造一个据有初始容量值的列表
// 传入一个int的值，构造一个initialCapacity容量的列表
public ArrayList(int initialCapacity) {
//如果初始化容量大于0，则创建一个对应Object数组
//如果初始化容量等于0，创建一个空数组
//如果初始化容量不是这个，直接报非法参数错误
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 无参构造方法默认
public ArrayList() {
// 直接初始化一个容量为10的数组（DEFAULT_CAPACITY = 10）
// 初始的Data为一个空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 这个不常用，主要作用是将一个Collection<T>转换为ArrayList
// 其中T必须继承E
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//先转换为数组，
//然后统计数组的数据个数
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//每个集合的toarray()的实现方法不一样，所以需要判断一下，
//如果不是Object[].class类型，
//那么需要使用ArrayList中的方法去改造一下。
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果size等于0，直接用空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList构造方法总结：就是初始化一下存储数据的elementData数组
ArrayList中的核心方法：增add
// 第一步：增加
public boolean add(E e) {
// 确认容量，通过此步骤已经可以确保增加这个元素不会越界
ensureCapacityInternal(size + 1);
// 直接将元素加在数组，并且size++
elementData[size++] = e;
return true;
}
// 确保列表中含有minCapcity的最小容量
// 注：ensureCapacity() 是提供给用户使用的方法，在 ArrayList 的实现中并没有使用
private void ensureCapacityInternal(int minCapacity) {
// 进一步确认ArrayList的容量，看是否需要进行扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算传入的elementData需要的最小容量
// minCapacity就是传入指定的容量，计算后的容量不得低于这个值
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果elementData为空，则返回默认容量10和minCapacity中的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则直接返回指定的minCapacity
return minCapacity;}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;// 修改的次数自增，该变量主要是用来实现快速失效fail-fast机制的
// overflow-conscious code 判断是否需要扩容
// 如果指定的minCapacity大于数组长度才会扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容主程序
private void grow(int minCapacity) {
// overflow-conscious code
// 先按照1.5倍扩容
int oldCapacity = elementData.length;//之前的数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1);//新长度，1.5倍
// 如果按照1.5倍扩容后依然满足不了，就让新的容量直接扩到要求的最小长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新长度大于了允许的最大范围，则执行大容量分配
// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2^31-1-8
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);
}
// 此方法最大分配Integer.MAX_VALUE
// 当传入容量参数超过了2^31-1-8时，即溢出后直接报错
// 当传入容量参数超过了2^31-1-8了但是又小于2^31-1，那么以2^31-1为准
// 当传入容量参数不大于2^31-1-8时，以容量2^31-1-8为准
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0了说明溢出了，直接报错
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 判断如果minCapacity大于MAX_ARRAY_SIZE 则返回Integer.MAX_VALUE
// 否则返回MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
// 在某个位置插入元素，效率低
// 举例 a = [1,2,3], a.add(1,100) → a = [1,100,2,3]
public void add(int index, E element) {
// 1.越界检查
rangeCheckForAdd(index);
// 2.确认容量
ensureCapacityInternal(size + 1); // Increments modCount!!
// 3.将index及之后的元素后移一位，空出index位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 4.插入元素，元素个数自增
elementData[index] = element;
size++;
}
// add方法的实战总结
List<Integer> numbers = new ArrayList();
// this.elementData的length=0 this.size = 0
// 当this.elementData为空时，只要add就必定会扩容到10，
// 其他情况扩容机制为max(1.5*当前容量,需要的最小容量)
numbers.add(1) // this.elementData的length=10,this.size=1
List<Integer> numbers = new ArrayList(1);
// this.elementData的length=1,已经分配一个元素，值是null
// this.size = 0
numbers.add(1) // this.elementData的length=1,值是1，this.size=1
// 假设a = [1,2,3]
List<Integer> numbers = new ArrayList(a);
// this.elementData的length=3
// this.size = 3
numbers.add(1) // this.elementData的length动态扩容10+10>>1=15 this.size=4
DEFAULT_CAPACITY只是为了在elementData为空时add，然后为elementData分配10个元素的空间
当elementData不为空时，当add后元素超过超过当前容量，扩容为max(1.5*当前容量,需要的最小容量)
总结：
size只和有值的元素相关，[1,2,3,null] size=3
数组length由内部算法规则改变
ArrayList中的核心方法：查get
// 返回index对应的对象
public E get(int index) {
rangeCheck(index); // 越界检查
return ArrayList.this.elementData(index);//返回该元素
}
// 这个简单
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
ArrayList中的核心方法：删remove
备注：remove后不会自动减容，用户可以调用trimToSize将对象的容量修建为列表当前大小
public E remove(int index) {
rangeCheck(index); // 越界检查
modCount++;//修改次数++
E oldValue = elementData(index);//获取即将被删除的元素
int numMoved = size - index - 1;// 需要移动的元素个数
if (numMoved > 0)//将需要移动的元素后面的依次向前移动
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 最后一个元素归为null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 移除List中指定的第一个元素，负荷条件的最低的哪个
// 如果不包含此元素，list不会改变
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++)
// equals用来判断对象的值是否相等
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 快速删除指定位置元素，不返回被删除的元素
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
// 移除List所有元素，会将数组缓冲区所有元素置为null
// 清空后，我们直接打印 list，却只会看见一个 [],
// 而不是 [null, null, ….] ==> toString() 和 迭代器进行了处理
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
// 删除列表中包含C的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);// 移除list中 c中的元素
}
// 批量删除，
// @param c是要移除的集合
// @param complement是否是补集，
// true移除list中除了C集合的所有元素，false 移除list中 c中的元素
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;//两个指针
boolean modified = false;
try {
// 遍历数组，检查这个集合是否对应值，移动要保留的值到数组前面
// 如果保留，将相同元素移动到前段，不保留，将不同元素移动到前面
for (; r < size; r++)
// 假如是remove list中的所有c
// 如果list中的该元素在c中未出现，则保留下来
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 最后的r肯定是等于size的，如果不等于说明在过程中出错了
// 需要将出错部分后面的都补到elementData末尾
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;// 然后重新计算w个数
}
// 将w以后的全部清空
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;//返回modified
}
ArrayList中的核心方法：改
// 修改指定位置的值，并返回修改前的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// 返回列表元素个数
public int size() {
return size;
}
// 求交集，和上面的删除list中包含的所有c用的一样
// 这里是删除list中和c不一样的，即求交集，与运算
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
//返回ArrayList的Object数组，不影响原来的
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
ArrayList中的核心方法：其他
// 因为remove元素不会动态调整容量
// 所以提供了一个可以调整size的方法，调整后数组缓冲区大小=ArrayList实际元素
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}