LinkedHashMap 原理及源码分析
- 设计简介
- 思考问题
- 源码分析-变量定义
- 源码分析-构造方法
- 源码分析-插入数据
- 源码分析-删除数据
- 源码分析-获取数据
- 源码分析-fail-fast
设计简介
先来看一下它的继承体系
可以看到
- 实现了 RandomAccess 接口表示它支持随机访问
- 实现了 Serializable 接口表示可以序列化
- 实现了 List 接口
- 继承了 AbstractList 的基础功能并且对部分功能其进行了重写
- 最终 Collection 都实现了 Iterable 接口意味着可以迭代
上面看到了实现了很多接口也继承了很多类，那么对于 ArrayList 来说就需要提供这些的默认实现方式。
我们再来看看 ArrayList 的数据结构，ArrayList 的数据结构很简单就是采用的数组来存储数据的
思考问题
1、 ArrayList 底层采用什么数据结构实现
2、 ArrayList 如何进行扩容，扩容后当数据清空掉的时候会进行缩容吗
3、 ArrayList 适用于怎样的应用场景，什么地方使用比较高效，什么地方使用比较低效，如何选择
4、 new ArrayLisy() 默认使用 EMPTY_ELEMENTDATA 初始化，new ArrayList(0) 使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来进行初始化，他们都是 {} 空数组为什么要做这样的区别？
5、 什么是浅拷贝和深拷贝
6、 clone 是浅拷贝还是深拷贝
7、 默认的最大容量为 MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8; 当发现容量已经超出这个限制之后，会进行超容处理就是将容量扩大到 Integer.MAX_VALUE 这么做有什么意义？
问题 5：什么是浅拷贝和深拷贝
浅拷贝
可以看到如果拷贝的是基本类型的值就是对值就行一份复制互不影响，如果拷贝的是引用类型那么拷贝的是他的引用的地址，拷贝前后引用指向同一个地址，那么可能就存在数据被窜写修改的风险，看下面这段代码
public static void main(String[] args) throws CloneNotSupportedException {
B b = new B(100);
A a = new A(10, b);
A a2 = (A) a.clone();
b.val = 20;
a.val = 15;
System.out.println(a2); // A{val=10, b=B{val=20}}
}
static class A implements Cloneable {
int val;
B b;
public A(int a, B b) {
this.val = a;
this.b = b;
}
@Override
protected Object clone() throws CloneNotSupportedException {
return super.clone();
}
@Override
public String toString() {
return "A{" +
"val=" + val +
", b=" + b +
'}';
}
}
static class B {
int val;
public B(int val) {
this.val = val;
}
@Override
public String toString() {
return "B{" +
"val=" + val +
'}';
}
}
深拷贝
在拷贝基本类型的时候没有什么区别，区别在于拷贝引用类型的时候会新建开辟一块新的内存用于存储引用类型指向的数据，看下面这段代码
public static void main(String[] args) throws CloneNotSupportedException {
B b = new B(100);
A a = new A(10, b);
A a2 = (A) a.clone();
b.val = 20;
a.val = 55;
System.out.println(a2); // A{val=10, b=B{val=100}}
}
static class A implements Cloneable {
int val;
B b;
public A(int a, B b) {
this.val = a;
this.b = b;
}
@Override
protected Object clone() throws CloneNotSupportedException {
A a = (A) super.clone();
a.b = (B) b.clone();
return a;
}
@Override
public String toString() {
return "A{" +
"val=" + val +
", b=" + b +
'}';
}
}
static class B implements Cloneable {
int val;
public B(int val) {
this.val = val;
}
@Override
public String toString() {
return "B{" +
"val=" + val +
'}';
}
@Override
protected Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
我们可以看到上面这段代码描述和浅拷贝不同的在于，深拷贝在拷贝引用类型的时候，去创建了一个新的对象去存储它，那么这样引用地址就不会和拷贝元数据的一样了
protected Object clone() throws CloneNotSupportedException {
A a = (A) super.clone();
a.b = (B) b.clone();
return a;
}
其它的我们从源代码中找出答案
变量定义
这里给出我们关注的部分变量的定义，暂时有的不理解没有关系源码分析会挨个讲解
// 数组默认容量为 10
private static final int DEFAULT_CAPACITY = 10;
// 空数组，当指定了容量并且容量为 0 的时候用其初始化 elementData
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组，使用无参沟站默认创建的的时候用其初始化 elementData
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 集合的元素数据
transient Object[] elementData; // non-private to simplify nested class access
// 数组数据数量
private int size;
/**
* 可以看到集合数组的最大容量为 Integer.MAX_VALUE - 8;
* 如果数组元素数量超出了这个限制那么就将采用 Integer.MAX_VALUE 作为数组的容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造方法
// 指定初始化容量创建 ArrayList
// 容量为 0 使用 EMPTY_ELEMENTDATA 初始化元素空数组
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 默认使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 初始化元素空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 传入集合创建 ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// c.toArray 可能返回的不是 Object[].class
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
这里可以看到
- new ArrayList() 默认使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组来初始化集合元素组
- new ArrayList(initialCapacity) 当容量为 0 的时候使用 EMPTY_ELEMENTDATA 空数组来初始化
- 传入集合来创建一个新的集合
这里来我们来看下这段代码
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
这里需要注意两点
- toArray() 可能返回的不是 Object[] 类型数组
List<String> data = Arrays.asList("a");
System.out.println(data.toArray().getClass()); # class [Ljava.lang.String;
System.out.println(data.toArray().getClass() != Object[].class); # true
- Arrays.copyOf()
- 如果是基本类型不用考虑
- 如果存储的是其它对象需要考虑引用修改对应的值被修改的风险
public static void main(String[] args) {
A a = new A(1);
// 存储的是对象
List<A> list1= new ArrayList<>();
list1.add(a);
// 通过 Arrays.copyOf() 之后（toArray() 也是调用的 copyOf()）
// 这里仅仅是复制了传入集合数组元素的值
// 如果这个值是基本类型无需其它考虑
// 如果这个值是引用类型就可能存在风险
List<A> list2 = new ArrayList<>(list1);
// 这里修改了原集合某个元素的值，发现新的集合元素值也被改变了
a.val = 100;
System.out.println(list2.get(0).val); // 输出 100
}
static class A {
int val;
public A(int val) {
this.val = val;
}
}
插入数据
/**
* 往集合中添加数据
* @param e
* @return
*/
public boolean add(E e) {
// 确保容量能够容新的纳数据调用时候传入 size + 1 如果发现容量不够了就需要进行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 在指定位置添加数据
* @param index
* @param element
*/
public void add(int index, E element) {
// 检查添加位置的合法性
rangeCheckForAdd(index);
// 确保容量能够容新的纳数据调用时候传入 size + 1 如果发现容量不够了就需要进行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将 index 到最后的数据向后移动一个位置，空出的 Index 设置默认值即可
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
这里可以看到有两种添加数据的方式
- add(val) 直接添加数据到集合
- add(index, val) 将数据添加到指定的位置
- 这两者都需要通过这个方法 ensureCapacityInternal() 保证内部容量能够容纳数据
- 不同的是 add(index, val) 在指定位置添加数据后，需要移动其它数据的位置
ensureCapacityInternal(size +1)
/**
* 确保容量能够容新的纳数据
* 如果没有初始化要初始化
* 如果发现容量不够用就需要进去扩容
* @param minCapacity
*/
private void ensureCapacityInternal(int minCapacity) {
// 如果是采用的无参构造方式指定的空数组
// 采用一个 DEFAULT_CAPACITY 和 minCapacity 的最大值作为 minCapacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 使用 minCapacity 检测如果需要进行扩容的话进行扩容
ensureExplicitCapacity(minCapacity);
}
在这里就能看到如果初始化数组类型是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空数组，采用 DEFAULT_CAPACITY 和 minCapacity 的最大值作为初始化容量，而对于 EMPTY_ELEMENTDATA 就没有这样的处理，只用传入的 minCapacity 做为初始化容量。
- 所以调用 new ArrayList() 构建的 ArrayList 初次调用 add 的时候发现没有初始化，设置初始化容量为 minCapacity = 10
- 调用 new ArrayLisy(n) 是采用了指定的容量 n 来进行初始化的
- n == 0，初次调用 add(val) 的时候 minCapacity = 1
该处设置好了 minCapacity 之后，就会继续调用 ensureExplicitCapacity 进一步进行检测是否需要进行扩容
ensureExplicitCapacity()
/**
* 根据 minCapacity 看是否需要进行扩容
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
// 修改次数 + 1 用于迭代器 fail-fast
modCount++;
// overflow-conscious code
// 如果传入的最小容量 minCapacity 大于当前元素数据的长度了
// 就说数据不够存放了
if (minCapacity - elementData.length > 0)
// 扩容数组
grow(minCapacity);
}
这里可以看到如果传入要求的最小容量已经大于了集合元素数组可以容纳的数量了，那么久要进行扩容，此处 grow() 就是扩容的真正逻辑
grow(minCapacity)
/**
* 扩容
* @param minCapacity
*/
private void grow(int minCapacity) {
// 记录扩容前的容量
int oldCapacity = elementData.length;
// 每次进行 1.5 倍的扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容后容量还是小于 minCapacity 那么久用 minCapacity 作为扩容的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新的容量大于最大数组容量了
// 容量超出了 MAX_ARRAY_SIZE 就将 Integer.MAX_VALUE 作为最大数组容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 超容处理
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// copyOf 返回新的数据
elementData = Arrays.copyOf(elementData, newCapacity);
}
这里可以看到
- 扩容是对之前容量进行 1.5 倍的扩容
- 如果扩容后容量超出了 MAX_ARRAY_SIZE 这个最大限制会调用 hugeCapacity(minCapacity) 进行处理
hugeCapacity(minCapacity)
/**
* 容量超出了 MAX_ARRAY_SIZE 就将 Integer.MAX_VALUE 作为最大数组容量否则最大值就是 MAX_ARRAY_SIZE
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
这里就有个问题为什么不直接 Integer.MAX_VALUE 做为集合元素最大容量，而是使用 Integer.MAX_VALUE – 8 作为 MAX_ARRAY_SIZE 集合元素最大容量呢？这是因为需要留 8 个位置用于存储集合的数组的对象头数据
删除数据
/**
* 删除指定位置的数据
* @param index
* @return
*/
public E remove(int index) {
// 检查删除位置的合法性是否越界
rangeCheck(index);
// 修改次数 + 1
modCount++;
// 获取到删除的数据
E oldValue = elementData(index);
// 需要移动的数量
int numMoved = size - index - 1;
// 需要移动的数量大于 0
// 只有在删除的是尾部的数据的时候不需要移动
if (numMoved > 0)
// 将删除位置+1 到尾部的数据依次向前移动一个
// 那么当前数据就被删除了
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将原先数组元素的最后一个数据设置为 null 帮助 gc 工作
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 删除元素集合中满足条件的第一个值
* @param o
* @return
*/
public boolean remove(Object o) {
if (o == null) { // 如果要删除的值是 null
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else { // 如果要删除的数据不为 null 注意自定义对象可能需要重写 equals 和 hashcode 方法
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/**
* 删除指定位置的数据
* @param index
*/
private void fastRemove(int index) {
// 修改次数 + 1
modCount++;
// 删除数据后需要移动的次数
int numMoved = size - index - 1;
// 如果需要移动
if (numMoved > 0)
// 将 index + 1, size - 1 的数据都向前移动一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
可以看到删除分为两种
- 删除指定位置的数据
- 删除指定的值的数据
- remove(Object o) 只会删除第一个满足条件的值
- 如果是其它对象的话由于调用的是 equals 判断相等，注意重写 equals 和 hashCode 方法
获取数据
public E get(int index) {
// 检查是否越界
rangeCheck(index);
// 检查数据是否被修改
checkForComodification();
return java.util.ArrayList.this.elementData(offset + index);
}
由于底层是数组所以可以根据指定的位置直接索引到对应的值，不过这里需要注意的一点是 checkForComodification()，因为我们之前的修改操作都会将 modCount++，所以可以根据它检查当前集合是否被其它线程修改过了，如果是的话要抛错也就是 fail-fast
private void checkForComodification() {
if (java.util.ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
trim数据
/**
* 如果集合元素数量大于 size 了返回一个紧凑的集合
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
indexof
/**
* 遍历检索是否存在对应的数据
* 返回的是第一个满足条件的数据
* @param o
* @return
*/
public int indexOf(Object o) {
if (o == null) {
// 返回第一个满足条件的 null 数据
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 返回第一个满足条件的数据
// 需要注意的是这里调用的是 equals 方法
// 如果是自定义的对象，可能需要重写对应的 equals 和 hashcode 方法
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 和 indeof 方法类似，返回最后一个满足条件的数据
* 重数组尾部开始倒序遍历返回满足条件的第一个数据
* @param o
* @return
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
clone
public Object clone() {
try {
// clone 父类的基础信息
java.util.ArrayList<?> v = (java.util.ArrayList<?>) super.clone();
// 拷贝数组注意我们前面分析过这里只是拷贝了集合元素的引用地址
v.elementData = Arrays.copyOf(elementData, size);
// 将修改次数重置为 0
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
我们上面分析过 Arrays.copyOf 这个方法，所以 ArrayList 的 clone 是个浅拷贝，那么我们在日常使用的时候就需要注意，如果使用了它的 clone 方法注意修改原数组集合中某个数据的引用对象值的时候注意可能给 clone 后集合带来的影响。