一、ArrayList底层源码
1.1 ArrayList类成员变量
private static final int DEFAULT_CAPACITY = 10; //默认容量
private static final Object[] EMPTY_ELEMENTDATA = {};//空数组
transient Object[] elementData; //ArrayList集合中的核心数组
private int size; //记录数组中存储个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //数组扩容的最大值
1.2 ArrayList集合类的构造方法
//无参数构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //数组没有长度
//有参数的构造方法
public ArrayList(int 10) {
if (initialCapacity > 0) {
//创建了10个长度的数组
this.elementData = new Object[10];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
1.3 ArrayList集合类的方法add()
new ArrayList<>().add("abc"); //集合中添加元素
public boolean add("abc") {
//检查容量 (1)
ensureCapacityInternal(size + 1);
//abc存储到数组中,存储数组0索引,size计数器++
elementData[size++] = "abc";//数组扩容为10
return true;
}
//检查集合中数组的容量, 参数是1
private void ensureCapacityInternal(int minCapacity = 1) {
//calculateCapacity 计算容量,方法的参是数组 , 1
// ensureExplicitCapacity (10) 扩容的
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量方法, 返回10
private static int calculateCapacity(Object[] elementData, int minCapacity = 1) {
//存储元素的数组 == 默认的空的数组 构造方法中有赋值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//返回最大值 max(10,1)
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//扩容
private void ensureExplicitCapacity(int minCapacity = 10) {
modCount++;
// 10 - 数组的长度0 > 0
if (minCapacity - elementData.length > 0)
//grow方法(10) 数组增长的
grow(minCapacity);
}
//增长的方法,参数是(10)
private void grow(int minCapacity = 10) {
//变量oldCapacity保存,原有数组的长度 = 0
int oldCapacity = elementData.length; // 0
//新的容量 = 老 + (老的 / 2)
int newCapacity = oldCapacity + (oldCapacity >> 1);// 0
// 0 - 10 < 0 新容量-计算出的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; //新容量 = 10
//判断是否超过最大容量
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);
}
二、LinkedList底层源码
2.1 LinkedList集合的成员变量
transient int size = 0; //集合中存储元素个数计数器
transient Node<E> first; //第一个元素是谁
transient Node<E> last; //最后一个元素是谁
2.2 LinkedList集合的成员内部类Node (节点)
//链表中,每个节点对象
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;
}
}
2.3 LinkedList集合的方法add()添加元素
//添加元素 e 存储元素 abc
//再次添加元素 e
void linkLast(E "abc") {
//声明新的节点对象 = last
final Node<E> l = last; // l = null l "abc"节点
//创建新的节点对象,三个参数, 最后一个对象,"abc", 上一个对象null
final Node<E> newNode = new Node<>(l, e, null);
//新节点赋值给最后一个节点
last = newNode;
if (l == null)
//新存储的几点赋值给第一个节点
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2.4 LinkedList集合的方法get()获取元素
//集合的获取的方法
//index是索引, size 长度计数器
Node<E> node(int 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;
}
}
三、哈希表源码
HashSet集合本身不具备任何功能,内部调用了另一个集合对象HashMap
3.1 构造方法无参数
public HashSet() {
map = new HashMap<>();
}
3.2 HashMap类的成员变量
//哈希表数组的初始化容量,16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;//价值因子
static final int TREEIFY_THRESHOLD = 8;//阈值,转红黑树
static final int UNTREEIFY_THRESHOLD = 6;//阈值,解除红黑树
static final int MIN_TREEIFY_CAPACITY = 64;//阈值,转红黑树
3.3 HashMap内部类Node
//节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //对象哈希值
final K key; //存储的对象
V value; //使用Set的集合,value没有值
Node<K,V> next; //链表的下一个节点
}
3.4 Set集合中的add()
- Set集合存储方法add(),调用的是HashMap集合的方法put()
//HashMap存储对象的方法put,Key存储的元素,V是空的对象
public V put(K key, V value) {
//存储值,传递新计算哈希值,要存储的元素
return putVal(hash(key), key, value, false, true);
}
//传递存储的对象,再次计算哈希值
//尽量降低哈希值的碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//存储值,重写计算的哈希值,要存储值
final V putVal(int hash, K key, V value, boolean false,
boolean true) {
//Node类型数组, Node类型数组 n, i
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab =Node[]=null
if ((tab = table) == null || (n = tab.length) == 0){
//n=赋值为 tab数组=resize()方法返回数组,默认长度的数组16
n = (tab = resize()).length;// 16
//数组的长度-1 & 存储对象的哈希值,确定存储的位置
//判断数组的索引上是不是空的
if ((p = tab[i = (n - 1) & hash]) == null)
//数组索引 赋值新的节点对象,传递计算的哈希值,存储的对象
tab[i] = newNode(hash, key, value, null);
else{
//数组的索引不是空,要存储的对象,已经有了
//判断已经存在的对象,和要存储对象的哈希值和equals方法
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//遍历该索引下的链表,和每个元素比较hashCode和equals
}
}
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;