## 概念回顾

ArrayList：源码难点	扩容和缩容
存放元素：有序
线程是否安全：不安全
核心方法：get（下标查询） add
底层数据结构：数组基于object类型

## 为什么get方法是index下标？

时间复杂度的原因   O(1) O(n)  O(lgn)
基于下标查询就是O(1)
基于元素值查询就是O(n)-----链表

## 扩容方法

```
private void ensureExplicitCapacity(int minCapacity) {
	// 线程同步，不能在遍历的时候进行添加或者删除操作
    modCount++;

    // 判断是否需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
```

```
private void grow(int minCapacity) {
	// 初始化容量为0
    int oldCapacity = elementData.length;
    // 新的容量还是为0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    	// 新的容量为10，只有第一次初始化会走这个判断
        newCapacity = minCapacity;
    // 这个判断正常不会走
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}
```

每次扩容，容量增加1.5倍

## 缩容方法

注意hashmap集合没有缩容，因为缩容需要重新计算index值
基于value值删除复杂度为O(n)，需要考虑缩容问题
```
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++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
```


## 快速覆盖

```
private void fastRemove(int index) {
	// 线程同步，不能在遍历的时候进行添加或者删除操作
    modCount++;
    // 计算删除index后面的所有元素有多少个
    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
}
```

arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

Object src：原数组
int  srcPos：从元数据的起始位置开始
Object dest：目标数组
int destPos：从目标数组的开始起始位置
int length：要copy的数组长度

## ArrayList与vector的区别

相同点：都是基于数组实现，默认初始容量为10
不同点：

1. ArrayList线程不安全，vector线程安全。
2. ArrayList扩容为原容量的1.5倍，vector为原来的2倍---capacityIncrement可以自定义扩容的大小

## HashSet底层实现原理

HashSet：基于HashMap实现

思考点：
HashSet为什么是无序的？因为HashMap的key不允许重复  hash+equals，hash值排  序
HashSet底层数据结构模型：基于hashmap实现，key为hashset存放的元素，value是空值
缺点：比较占用内存

## LinkedList

底层基于双向链表结构实现
查询的时间复杂度为O(n)

为什么需要一个变量记录头结点？
为了后期遍历数据知道从哪里开始！