Java源码阅读
List
List继承于Collection接口，有顺序，有索引，允许存储重复元素，可以放入null
接口方法：
int size(); //获取大小
boolean isEmpty(); //判断是否为空
boolean contains(Object o); //是否包含某个元素
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 addAll(int index, Collection<? extends E> c); //批量添加，指定开始的索引
boolean removeAll(Collection<?> c); //批量移除
boolean retainAll(Collection<?> c); //将c中不包含的元素移除
default void replaceAll(UnaryOperator<E> operator) {}//替换
default void sort(Comparator<? super E> c) {}// 排序
void clear();//清除所有的元素
boolean equals(Object o);//是否相等
int hashCode(); //计算获取hash值
E get(int index); //通过索引获取元素
E set(int index, E element);//修改元素
void add(int index, E element);//在指定位置插入元素
E remove(int index);//根据索引移除某个元素
int indexOf(Object o); //根据对象获取索引
int lastIndexOf(Object o); //获取对象元素的最后一个元素
ListIterator<E> listIterator(); // 获取List迭代器
ListIterator<E> listIterator(int index); // 根据索引获取当前的位置的迭代器
List<E> subList(int fromIndex, int toIndex); //截取某一段数据
default Spliterator<E> spliterator(){} //获取可切分迭代器值得一提的是里面出现了ListIterator，这是一个功能更加强大的迭代器，继承于Iterator,只能用于List类型的访问，拓展功能例如：通过调用listIterator()方法获得一个指向List开头的ListIterator，也可以调用listIterator(n)获取一个指定索引为n的元素的ListIterator,这是一个可以双向移动的迭代器。
操作数组索引的时候需要注意，由于List的实现类底层很多都是数组，所以索引越界会报错IndexOutOfBoundsException。
ArrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable继承了AbstractList接口，实现了List，随机访问，可克隆，序列化接口。线程不安全，如果需要线程安全适用其他类。低层是基于数组实现的，支持扩容。
成员变量
// 真正存取数据的数组
transient Object[] elementData;
// 实际元素个数(不是elementData的大小，是具体存放的元素的数量)
private int size;transient表示这个属性不需要自动序列化，因为element存储的不是真的元素的对象，而是指向对象的地址，所以这样的属性序列化是没有太大意义的。对地址序列化之后，反序列化的时候找不到之前的对象，所以需要手动实现对对象的序列化。这个需要我们看源码里面的readOject()和writeOject()两个方法。其实就除了默认的序列化其他字段，这个elementData字段，还需要手动序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 序列之前需要保存原本的修改的次数，序列化的过程中不允许新修改
int expectedModCount = modCount;
// 将当前类的非静态和非transient的字段写到流中，其实就是默认的序列化
s.defaultWriteObject();
// 将大小写到输出流中
s.writeInt(size);
// 按照顺序序列化里面的每一个元素，注意使用的是`writeOject()`
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 如果序列化期间有发生修改，就会抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
// 反序列化
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 读取默认的反序列化数据
s.defaultReadObject();
// 读取大小
s.readInt(); // ignored
if (size > 0) {
// 和clone()类似，根据size分配空间，而不是容量
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// 循环读取每一个元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}这个方法在对象流中，通过反射进行调用。
ArrayList默认大小为10
private static final int DEFAULT_CAPACITY = 10;定义了两个空数组，EMPTY_ELEMENTDATA名为空数组,DEFAULTCAPACITY_EMPTY_ELEMENTDATA名为默认大小空数组,用来区分是空构造函数还是带参数构造函数构造的arrayList,第一次添加元素的时候使用不同的扩容。之所以是一个空数组，不是null，是因为使用的时候我们需要制定参数的类型。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};还有一个特殊的成员变量modCount，这是快速失败机制所需要的，也就是记录修改操作的次数，主要是迭代的时候，防止元素被修改。如果操作前后的修改次数对不上，那么有些操作就是非法的。transient表示这个属性不需要自动序列化。
protected transient int modCount = 0;序列化id如下：为什么需要这个字段呢？这是因为如果没有显示声明这个字段，那么序列化的时候回自动生成一个序列化的id，这样子的话，假设序列化完成之后，往原来的类里面添加了一个字段，那么这个时候反序列化会失败，因为默认的序列化id已经改变了。假设我们给它指定了序列化id的话，就可以避免这种问题，只是增加的字段反序列化的时候是空的。
private static final long serialVersionUID = 8683452581122892189L;构造方法
构造方法有三个，可以指定容量，指定初始的元素集，可以什么都不指定。
// 指定初始化的大小
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);
}
}
// 什么都不指定，默认是空的元素集
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 传入一个集合，转成数组之后，复制一份作为显得数据集
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}常用方法
add
public boolean add(E e) {
// 确定容量是不是足够，足够就不会增加
ensureCapacityInternal(size + 1);
// size+1的地方，赋值为现在的e
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);// 检查位置是否合法
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();// 扩容
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}get
public E get(int index) {
// 检查下标
rangeCheck(index);
return elementData(index);
}
// 检查下标
private void rangeCheck(int index) {
if (index >= size)
// 数组越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(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)
// 调用native方法将后面的元素复制，移动往前一步
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将之前的元素置为空，让垃圾回收方便进行
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
// 为空的元素
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍历，如果equals,则调用删除
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 快速删除方法
private void fastRemove(int index) {
// 修改次数增加1
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
}扩容
在add()方法里面去调用的。 在最小调用的时候容量不满足的时候，会调用grow()，grow()是真正扩容的函数，每次扩容扩容为原来的1.5倍。
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// 1.5倍扩容
if (newCapacity - minCapacity <= 0) {// 超过int最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE// 容量上线 20多亿 几乎不能达到
: MAX_ARRAY_SIZE;
}LinkedList
LinkedList底层是双向链表实现的，还实现了Deque接口，继承AbstractSequentialList，AbstractSequentialList继承了AbstractList，也是线程不安全的
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable双向链表底层结构
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}成员变量
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;构造函数
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}添加
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 往头部添加元素
public void addFirst(E e) {
linkFirst(e);
}
// 往尾部添加元素
public void addLast(E e) {
linkLast(e);
}add()方法默认是在尾部添加
public boolean add(E e) {
linkLast(e);
return true;
}可以在指定位置添加元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}其中node(index)方法，当索引是在前面一半的时候，从前面开始遍历，当索引在后半部分的时候，从后面往前遍历
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 判断是在前后哪半部分
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}HashMap
HashMap使用动态数组+链表+红黑树构成，继承AbstractMap，实现了Map，Cloneable，Serializable
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, SerializableHashMap是线程不安全的，如果想使用线程安全的HashMap，可以通过Collection类的静态方法synchronizedMap获得线程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());HashMap的数据结构
HashMap通过key的hashCode计算hash值，hash值相同的挂载到一起，在相同hash值存储元素数量小于8时，使用链表存储，当元素数量大于8时，将链表转换为红黑树，当元素数量减少到小于6时，会再次由红黑树转为链表。
HashMap最上层是一个可扩容动态数组，考虑到扩容需要，该动态数组具有以下属性：
capacity：目前数组长度，值为2^n，每次扩容n会增加1，即数组容量变为之前的2倍，初始值为16
loadFactor：负载因子，默认值0.75，配合threshold使用
threshold：扩容阈值，等于capacity*loadFactor，当数组内元素达到这个阈值，就会触发扩容
初始化
HashMap初始化操作非常简单，就是确定initialCapacity，loadFactor的初始化值的过程。
平时我们调用无参构造函数时，都使用默认值。
也可以传入initialCapacity和loadFactor，进行自定义初始化
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}但是，在进行初始化操作时，只是初始化了创建数组的相关参数，没有真正的创建动态数组，真正的动态数组的创建是在第一次进行数据写入时触发的。
数据写入
向HashMap中写入数据的过程
外部方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}内部插入方法：
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次插入数据，初始化，resize()方法也是扩容方法
if ((tab = table) == null || (n = tab.length) == 0)
// n为当前动态数组长度
n = (tab = resize()).length;
// 通过hash发现要放入的元素的数组位置为null，则直接把元素放在这里
// p为赋值为当前动态数组目标位置的元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 要放入的位置已有元素
Node<K,V> e; K k;
// 判断目标位置第一个元素是否和新元素完全一致
// 先判断hash，hash不一致则直接短路
if (p.hash == hash &&
// 再判断key是否一致
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 红黑树，调用红黑树插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 列表，按照列表的方法插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 列表过长，转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key相同就跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 存在key，覆盖旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 扩容
resize();
afterNodeInsertion(evict);
return null;
}扩容：
实际上是初始化和扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 初始化oldCap设为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 旧容量大于最大容量（1<<30），扩容阈值设置为Integer最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
// 容量扩大一倍并且小于最大容量，并且旧容量大于等于默认容量
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 扩容阈值翻倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化容量被赋值扩容阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 初始化使用默认数据
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0，loadFactor或初始化容量有误
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建一个新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 轮询，对所有元素进行重哈希
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 重哈希
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 树元素重哈希
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 链表元素重哈希
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}红黑树存放
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}链表转换为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}