常用实现类.png
一 Collection
1.1 集合和数组得区别
- 1:⻓度的区别
数组的⻓度固定
集合的⻓度可变 - 2:元素的数据类型
数组可以存储基本数据类型,也可以存储引⽤类型
集合只能存储引⽤类型(你存储的是简单的int，它会⾃动装箱成Integer)
1.2
继承关系.png
常用方法.png
Collection继承了Iterable接口，该接口有Iterator，而它也是个接口，有三个方法
1）hasNext
2）next
3）remove
iterator在实现类中以内部类方式实现
以内部类实现.png
image.png
二 List接口
Collection接口主要有三个接口，分别是List、Map、Queue，下面讲List接口：
特点：有序（存入顺序和取出顺序一致），可重复
在Collection得Iterator接口基础上重新实现了ListIterator接口
多出了一些特有得方法
ListIterator.png
常用的三个子类：
1.ArrayList
- 首先时该类得成员属性：
ArrayList得成员属性.png
可以看出底层还是一个名为Object数组，初始容量为10，使用CopyOf来扩容 -
成员方法3个：
构造方法.png
1）无参构造：返回一个空数组
2）带int initialCapacitpy初始容量的构造函数，会设置为指定容量
3）参数时Collection类型就把他转化为elementData数组 - add方法：
1）add（E e）：分为两步
public boolean add(E e) {
1.判断是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
2.插入元素
elementData[size++] = e;
return true;
}
如果当前数组为空，那么比较DEFAULT_CAPACITY=10，
和size+1，取max；
如果指定了长度那就返回size+1；
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
中介函数
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);
}
grow方法：用来扩容：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
用右移操作，扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
如果仍然小于最小容量，拿直接拿最小容量作为新容量
if (newCapacity - m
inCapacity < 0)
newCapacity = minCapacity;
如果超出了Integer最大值-8这个阈值，转到huge
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);
}
private static int hugeCapacity(int minCapacity) {
长度小于0抛异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
否则直接用最大长度Integer.MAX_VALUE作为新长度
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
底层用Arrays得静态方法copyOf方法复制转移得到新数组：
T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)
2）add(int index, E element)
public void add(int index, E element) {
先判断index是否越界
rangeCheckForAdd(index);
扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
底层c++编写得arraycopy方法插入
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
- get方法
public E get(int index) {
先判断索引是否越界，是否超过size
rangeCheck(index);
数组返回对应索引得元素
return elementData(index);
}
- set方法
public E set(int index, E element) {
同样先判断是否越界
rangeCheck(index);
保留旧值，作为返回值
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- remove方法
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;
}
-
细节
能存null值，删除时容量不变.png
如果size和容量不一致，得到新得匹配size得数组
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
2 Vector和ArrayList区别
1）Vector扩容1倍，ArrayList扩容1.5倍
2）Vector线程安全，都加了synchronized关键字，导致效率低。ArrayList线程不安全；
3）其实可以用Collections得静态方法synchronizedList(new ArrayLIst(..))来得到同步得ArrayList
3 LinkedList
同样实现了Queue、Deque接口
-
成员变量：
双向链表，直到头尾节点即可.png -
构造方法：
同样有一个转换Collection对象得构造方法.png -
add：
其实就是双向链表得尾节点添加.png -
remove：
image.png
image.png
image.png -
get：
优化了一下，看是否从头或从尾部遍历.png -
set：
image.png -
总结：
image.png
