以下源码来自JDK11

ArrayList集合源码

创建ArrayList集合

/*
无参构造,返回一个空数组
参数:elementData - ArrayList集合维护的数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/*
* 有参构造
* 构造一个具有指定初始容量的空数组。
* 参数：initialCapacity - 列表的初始容量
* 抛出：IllegalArgumentException – 如果指定的初始容量为负
* */
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 boolean add(E e) {modCount++;//记录集合被修改的次数,防止多个线程同时修改/*第一个参数:添加的元素第二个参数:数组名第三个参数:集合长度/现在元素的插入位置索引*/add(e, elementData, size);return true;}private void add(E e, Object[] elementData, int s) {//如果集合长度与数组长度相同,则需要扩容if (s == elementData.length)elementData = grow();elementData[s] = e;//赋值size = s + 1;//集合长度加一,亦表示下个元素插入位置}private Object[] grow() {return grow(size + 1);//传入参数表示添加完当前元素后的最小容量}private Object[] grow(int minCapacity) {/*copyOf方法会创建一个长度为newCapacity(minCapacity)的新数组,并将elementData数组中的元素全部复制到新数组当中去*/return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));}private int newCapacity(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//记录老容量//新容量等于老容量加上老容量的一半,即老容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);//作新容量是否小于等于最小容量判断if (newCapacity - minCapacity <= 0) {//如果数组是初始的空数组(即第一次添加元素),返回默认容量大小10和最小容量值两者中的最大值if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)return Math.max(DEFAULT_CAPACITY, minCapacity);/*如果最小容量值小于0,抛出内存溢出异常,最小容量超过整数最大值Integer.MAX_VALUE时就会内存溢出*/if (minCapacity < 0) // overflowthrow new OutOfMemoryError();//返回最小容量值return minCapacity;}/*新容量值大于最小容量值时,判断新容量值是否小于等于数组容量最大值,满足则返回新容量值,否则使用hugeCapacity方法确保不会扩容得太大*/return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);}private static int hugeCapacity(int minCapacity) {/*如果最小容量值小于0,抛出内存溢出异常,最小容量超过整数最大值Integer.MAX_VALUE时就会内存溢出*/if (minCapacity < 0) // overflowthrow new OutOfMemoryError();//判断最小容量值是否超过了数组最大容量值,超过则返回整数最大值,否则返回数组最大值return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;}

LinkedList集合源码

添加数据

    public boolean add(E e) {linkLast(e);return true;}void linkLast(E e) {//记录尾指针所指向的元素final Node<E> l = last;//创建新节点,将l作为新节点的前一个节点,指向后一个节点的指针赋值为nullfinal Node<E> newNode = new Node<>(l, e, null);//将新节点赋值给尾指针last = newNode;//如果尾指针初始为null,说明当前插入的节点是第一个节点,让first指向它if (l == null)first = newNode;else//当前插入的不是第一个节点,将新节点赋值给插入前的尾结点的next指针l.next = newNode;size++;modCount++;}//Node类是LinkedList的静态内部类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;}}

迭代器源码

    ArrayList<String> strings = new ArrayList<>();strings.add("aaa");strings.add("bbb");strings.add("ccc");//获取迭代器对象Iterator<String> iterator = strings.iterator();//调用Itr的无参构造,返回一个迭代器对象public Iterator<E> iterator() {return new Itr();}//ArrayList的内部类private class Itr implements Iterator<E> {int cursor;       // 光标,迭代器的指针,初始值为0int lastRet = -1; // 上一个被遍历元素的索引int expectedModCount = modCount;//创建迭代器时,集合被添加/删除的总次数// 无参构造Itr() {}//光标不等于集合元素总数时,光标所指位置有值public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {//检查此时集合有没有被修改(添加/删除)checkForComodification();int i = cursor;//当前光标的值超过集合总元素个数,抛出不存在此元素异常if (i >= size)throw new NoSuchElementException();//获取集合存储数据的数组Object[] elementData = ArrayList.this.elementData;//当前光标的值超过数组长度,抛出并发修改异常if (i >= elementData.length)throw new ConcurrentModificationException();//移动光标位置,指向下一个元素cursor = i + 1;//返回光标移动前位置的元素,并将其索引赋值给lastRetreturn (E) elementData[lastRet = i];}final void checkForComodification() {//当前集合的被操作次数与创建迭代器时不一致,抛出并发修改异常if (modCount != expectedModCount)throw new ConcurrentModificationException();}}

HashSet底层原理

创建HashSet集合时,创建一个默认长度16,默认加载因子为0.75的数组,数组名为table

添加元素时,根据元素的哈希值跟数组长度计算出应存入位置的索引值

若该位置为null,直接将元素插入进去,若不为null,比较当前元素与该位置元素是否相等,相等则不插入

JDK8以前,不相等的情况 使用头插法,将新元素插入到数组中,旧元素挂在新元素下面,形成链表

JDK8以后,不相等时使用尾插法,即直接将新元素挂在旧元素下面,形成链表

且在JDK8以后,当链表长度超过8并且数组长度大于等于64时,将链表转换为红黑树

若集合中存储的时自定义对象,必须要重写hashCode()和equals()方法

当数组中的元素个数达到数组长度的75%(加载因子)时,数组将扩容为原来的2倍

HashMap源码

创建HashMap对象

//HashMap的三个重要成员变量
//数组默认初始长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
//数组默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;//无参构造
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

添加元素

考虑三种情况

1. 数组位置为null
2. 数组位置不为null,键不重复,挂在数组下面形成链表或红黑树
3. 数组位置不为null,键重复,覆盖原来的值

//put方法传入当前添加元素的key和value
/*
调用putval()方法
第一个参数:调用hash()方法,hash方法使用hashCode()方法得到了key对应的hash值,并进行了一定的处理
简单理解:第一个参数就是根据key获取的hash值
第二个参数:key
第三个参数:value
第四个参数:key相同时是否覆盖,true表示不覆盖,false表示覆盖
第五个参数:不相关,不做解释
*/
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {int h;//h = key.hashCode()计算key的hash值return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}//核心方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//定义一个局部变量,用于记录hash表中table的地址值Node<K,V>[] tab;//第三方变量,用于记录集合中元素的地址值Node<K,V> p;//n用于记录数组长度,i用于记录索引int n, i;//第一次添加元素时,table为nullif ((tab = table) == null || (n = tab.length) == 0)//resize方法创建一个默认长度为16,加载因子为0.75的数组赋值给tab,并将数组长度赋值给nn = (tab = resize()).length;/*使用当前插入元素的key和数组长度减一做与运算得到应该插入的位置索引,并获取该位置的元素赋值给p,判断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值是否相等,若相等再次判断该位置的元素与新元素的key是否相等,若也相等,将该位置元素交由e保存,留待进行值覆盖操作*/if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;/*判断获取到的数组元素是否是红黑树中的节点,若是,则调用putTreeVal方法将新元素按照红黑树规则添加到树当中去*/else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//获取到的数组元素是链表节点,使用binCount记录数组中的元素个数for (int binCount = 0; ; ++binCount) {/*获取p所指向节点的下一个节点,赋值给e(第一次判断时,p代表的是从数组中获取到的元素,即判断该元素下面是否还有节点),判断是否为空*/if ((e = p.next) == null) {//为空,则创建一个新的节点挂在下面p.next = newNode(hash, key, value, null);//判断链表长度是否超过8,超过则调用treeifyBin方法//treeifyBin方法底层还会继续判断数组长度是否大于等于64//如果两个条件同时满足,就会将数组转为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//跳出循环break;}//不为空,判断e与要插入的节点hash值是否相同,key是否相同if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))//相同,跳出循环,留待进行值覆盖操作break;//不相同,将e赋值给p,继续往下遍历p = e;}}//判断e是否为空,若为空,表示本次插入没有元素被覆盖,若不为空说明需要做覆盖操作if (e != null) { //记录e的存储的值V oldValue = e.value;//判断是否做覆盖操作if (!onlyIfAbsent || oldValue == null)//将新元素的值赋值给ee.value = value;//不相关,不做解释afterNodeAccess(e);//返回被覆盖的值return oldValue;}}++modCount;//判断数组中的元素是否达到了扩容阈值,未达到阈值,不做操作if (++size > threshold)//达到扩容阈值(16*0.75=12),resize方法会将数组扩容为原来的两倍,并将旧数组中的元素全部复制到新数组中去resize();//不相关,不做解释afterNodeInsertion(evict);//返回null表示没有元素被覆盖return null;
}

TreeMap源码

基本属性与构造器

	//比较器private final Comparator<? super K> comparator;//根节点private transient Entry<K,V> root;//节点个数private transient int size = 0;//空参构造public TreeMap() {comparator = null;}//有参构造,传入构造器赋值public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}//使用静态常量表示节点颜色,增加代码可读性private static final boolean RED   = false;private static final boolean BLACK = true;//静态内部类,Entry,集合中的元素都以Entry的类型存储static final class Entry<K,V> implements Map.Entry<K,V> {//键K key;//值V value;//左节点Entry<K,V> left;//右节点Entry<K,V> right;//父节点Entry<K,V> parent;//节点颜色boolean color = BLACK;...}

添加元素

public V put(K key, V value) {//记录根节点Entry<K,V> t = root;//判断根节点是否为空if (t == null) {compare(key, key); //为空,将插入的节点作为根节点root = new Entry<>(key, value, null);size = 1;modCount++;return null;}//用于记录两个元素键比较的差值int cmp;//用于记录新插入节点的父节点Entry<K,V> parent;//获取集合的比较器Comparator<? super K> cpr = comparator;if (cpr != null) {//集合指定了比较器do {//第一次循环,将根节点作为父节点parent = t;//比较新插入元素的key和根元素的key,将差值赋值给cmpcmp = cpr.compare(key, t.key);if (cmp < 0)//cmp小于0,说明新元素要放在t节点的左边,故将t节点的左节点赋值给tt = t.left;else if (cmp > 0)//cmp大于0,说明新元素要放在t节点的右边,故将t节点的右节点赋值给tt = t.right;else//cmp等于0,说明新元素与t节点键相同,做值覆盖操作return t.setValue(value);} while (t != null);}else {//集合未被指定比较器,使用默认比较规则//如果传入的key为null,抛出空指针异常if (key == null)throw new NullPointerException();//压制未检查警告@SuppressWarnings("unchecked")//将新元素的key强转为Comparable类型,要求key必须实现了Comparable接口,否则报错Comparable<? super K> k = (Comparable<? super K>) key;do {//下列代码与上面相同,不做解释parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}//遍历完红黑树,没有覆盖元素,做插入操作,创建新节点Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;//从新插入节点开始调整红黑树fixAfterInsertion(e);size++;modCount++;return null;
}private void fixAfterInsertion(Entry<K,V> x) {//将当前节点颜色设为红色,红黑树节点默认为红色x.color = RED;//按照红黑树规则调整节点//判断当前节点是否为根节点,父节点是否为红色,若父节点为黑色则不需要调整while (x != null && x != root && x.parent.color == RED) {//判断当前节点的父节点是否为爷爷节点的左节点if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//当前节点的父节点是爷爷节点的左节点//获取当前节点的叔叔节点,即当前节点爷爷节点的右节点Entry<K,V> y = rightOf(parentOf(parentOf(x)));//判断叔叔节点的是否为红色if (colorOf(y) == RED) {//叔叔节点为红色//将父节点设为黑色setColor(parentOf(x), BLACK);//将叔叔节点设为黑色setColor(y, BLACK);//将爷爷节点设为红色setColor(parentOf(parentOf(x)), RED);//将爷爷节点赋值给当前节点x = parentOf(parentOf(x));} else {//叔叔节点为黑色//判断当前节点是否为父节点的右节点if (x == rightOf(parentOf(x))) {//当前节点是父节点的右节点//将父节点作为当前节点x = parentOf(x);//以父节点为当前节点进行左旋rotateLeft(x);}//将父节点设为黑色setColor(parentOf(x), BLACK);//将爷爷节点设为红色setColor(parentOf(parentOf(x)), RED);//以爷爷节点为当前节点右旋rotateRight(parentOf(parentOf(x)));}} else {//当前节点的父节点是爷爷节点的右节点,以下代码与上面相同,不再解释Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}//将根节点颜色设为黑色root.color = BLACK;
}