image.png
Arraylist
ArraayList的结构和源码相对简单，是一个由数组组成的类，其查询快，增删慢,数据可重复，能保证数据的顺序性，线程不安全，初始化容量为10，扩容为1.5，不多BB直接看源码
Arraylist继承自AbstractList,
构造方法
这几Object数组就是arraylist的装载数据的媒介
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; //ArrayList实际的操作数组
//Arraylist默认的长度，如果数组超过10则发生第一次扩容
private static final int DEFAULT_CAPACITY = 10;
//有参构造函数，返回指定大小数组的集合
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);
}
}
//无参构造函数是返回一个空的数组集合，当add()会给数组容量赋为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//返回一个与c长度大小及元素一样的集合
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//将参数集合转化为数组
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
常用核心方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); //判断是否需要扩容
elementData[size++] = e;//往数组中最后的一个元素末尾追加元素，size是记录了数组中的元素个数，而不是数组的长度
return true;
}
上图的ensureCapacityInternal(size + 1)的实现：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY=10，这里是取两个值中较大的一个，如果elementData 是空数组，则取minCapacity =10
//这里获取DEFAULT_CAPACITY和minCapacity中最大的那个值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//记录数组修改的次数
modCount++;
//判断是否超过当前容量
if (minCapacity - elementData.length > 0)
//核心方法扩容机制
grow(minCapacity);
}
//刨根问底终于看到ArrayList最核心的方法
private void grow(int minCapacity) {
//oldCapacity为当前数组的容量
int oldCapacity = elementData.length;
//原来数组的容量扩大到1.5倍，如果数组是空的则newCapacity =0
int newCapacity = oldCapacity + (oldCapacity >> 1);
//一般扩容的逻辑都在走这里，同时初始化时会用到，将minCapacity赋值给新容量变量newCapacity，如果不是初始化一般不进去这个if语句，
//add()方法数组添加数据，数组一般都是+1，oldCapacity+1不会比oldCapacity+0.5*oldCapacity 扩容一般是是按照15,22,33,49,73......以此类推扩容1.5倍下去
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果容量扩大到1.5倍后 大于（Integer.MAX_VALUE -8）=2147483639则扩容至2147483639，这个情况一般没有，没有那么大的内存
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
get方法先检查索引范围是否超出实际现有数据的容量
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Arraylist的操作其实是对数组的操作，包括取元素，删元素基本是和数组一个特点，但是扩容操作，在添加的元素没有超过其容量时，增加元素不影响其性能，如果超过了其容量，则会对集合的数组进行扩容，性能因此受到影响，查询性能和数组一样非常高效
HashSet
底层是基于HashMap的，由于HashSet存储数据的方法调用的是HashMap的put方法，其存储的数据是存到HashMap的Key值中,key通过哈希函数可以算出HashMap的数组下标，所以相同key在HashMap对应的元素只有一个,而每一个类都有相应的hashCode方法，所以相同的类得到的哈希值是一样，所以hashSet的值是不重复的，hashSet无序性也是因为key通过哈希函数计算出HashMap的数组下标，由于是通过哈希计算，所以hashSet无法决定加入元素时的顺序性，但是却能保证这些元素是按照内部的顺序存储的，所以hashSet是一个无序的有序集合。。。
HashSet不重复性
从探究HashSet的不重复性，可以看到很多东西
private transient HashMap<E,Object> map
//将PRESENT 作为hashmap的value存储，可以使hashmap每一个value值都指向这个PRESENT，所以节省了堆空间
private static final Object PRESENT = new Object();
//从HashSet的构造函数我们看到HashSet，其实底层就是HashMap
public HashSet() {
map = new HashMap<>();
}
//HashMap的add调用的是HashMap的put方法，并且是以存储的元素为key，PRESENT为value
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
我们看看HashMap的put方法，其核心是putVal，我们先看看参数hash(key)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//这里调用了key这个对象的hashCode方法，如果两个对象相同，那么它们的hashCode值一定要相同
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//这是HashMap最核心的方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//这里是适用于HashMap首次put元素或者是容器被清空后，首次put table=null
if ((tab = table) == null || (n = tab.length) == 0)
//这里的resize()在首次put时候会将table的容量设置为16，而哈希桶的扩容条件为0.75*16=12，
//哈希桶元素超过12则进行扩容，扩容为原来的两倍,下面会开始分析resize()具体源码
n = (tab = resize()).length;
// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
//p为本次要插入的数组位置上的元素，判断是否发生了数组下标冲突，发生了冲突可能有两种情况：
//1、数组冲突，即key的通过hashcode和equals方法判断key值是同一个，则进行覆盖
//2、哈希冲突：即通过(n - 1) & hash计算在最大数组容量内（初始值是16）计算索引值，判断数组中此索引对应的数组位置是否被占用，然后在通过数组是否为树的结构，是则为哈希冲突
//【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//从这里我们看到了hashcode和equals方法，则判断key值是重复的，重复的则覆盖key在数组相应位置的v值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果哈希，判断数组p是否为树，为TreeNode的话，证明数组上的数据已经是红黑树结构了
else if (p instanceof TreeNode)
//为树的结构，则按照红黑树的方式插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//这里是判断了数组不为树而且哈希冲突的情况
//整个for的逻辑是转化为单链表的数组形式
for (int binCount = 0; ; ++binCount) {
//链表p的下一个值e为null时将下个元素指向value
if ((e = p.next) == null) {
//将元素排成单链表
p.next = newNode(hash, key, value, null);
//TREEIFY_THRESHOLD 为8，可以得出结论，如果链表元素超过了8则转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
// 链表转化为红黑树
treeifyBin(tab, hash);
break;
}
//如果链表p的下一个值e和要插入的key是一摸一样的，则直接结束，等下面的步骤进行value值的覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//将链表p指向下个不为空的值e,继续循环遍历
p = e;
}
}
//判断存在了重复的key值(依据hashcode和equals方法判断，上面已经判断过了)，则进行v值的覆盖
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断数组是否超过了加载因子*扩容前数组长度的值，超过则进行扩容，执行 resize()方法
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//我们看看这个扩容的核心方法
final Node<K,V>[] resize() {
//获取旧的数组将其赋值到oldTab
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//当旧的数组容量不为0时，也就是不是第一次执行put方法时
if (oldCap >= MAXIMUM_CAPACITY) {
// 原数组长度大于最大容量(1073741824) 则将threshold设为Integer.MAX_VALUE=2147483647
// 接近MAXIMUM_CAPACITY的两倍
threshold = Integer.MAX_VALUE;
return oldTab;
}
//将新数组的容量设置为旧数组的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; //新阈值也设置为旧阈值的两倍
}
else if (oldThr > 0)
newCap = oldThr; // 新阈值赋值给新数组容量
else {
// 这里是初始化时调用的，hashmap初始化默认设置阈值为12，哈希桶为16，阈值=加载因子（默认0.75）*哈希桶容量（默认16）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新阈值赋值赋值给threshold
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;
//将老数组赋值给e，并判断老数组是否为空
if ((e = oldTab[j]) != null) {
//将老数组的引用置空
oldTab[j] = null;
// 如果元素没有有下一个节点，说明该元素不存在hash冲突
if (e.next == null)
// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】
newTab[e.hash & (newCap - 1)] = e;
//如果数组为树，则构造红黑树
else if (e instanceof TreeNode)
//构造红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
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;
}
LinkedHashMap
LinkedHashMap是继承了HashMap,其特点和hashMap差不多，其加载因子，扩容机制，初始化容量都是一样的，但是LinkedHashMap装载数据的节点Entry是在hashMap的Node节点的基础上增加了before, after用于指向前后添加的节点，保证LinkedHashMap的顺序性
LinkedHashMap的节点类
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
LinkedHashMap并没有重写继承HashMap的put方法，只是重写了put方法中的putVal方法调用的newNode方法，newNode方法保证了插入的顺序性
/**
* 使用LinkedHashMap中内部类Entry
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
/**
* 将新创建的节点p作为尾结点tail，
* 当然如果存储的第一个节点，那么它即是head节点，也是tail节点，此时节点p的before和after都为null
* 否则，建立与上一次尾结点的链表关系，将当前尾节点p的前一个节点（before）设置为上一次的尾结点last,
* 将上一次尾节点last的后一个节点（after）设置为当前尾结点p
* 通过此方法实现了双向链表功能，完成before,after,head,tail的值设置
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
LinkedHashSet
LinkedHashSet继承了HashSet，底层的结构是使用的LinkedHashMap的结构，其
//LinkedHashSet 的构造函数，super里是初始化LinkedHashSet
public LinkedHashSet() {
super(16, .75f, true);
}
super的方法是HashSet的有参构造，返回的是LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
但是LinkedHashSet使用的add方法是使用从HashSet继承过来的方法，但是这个put方法使用的LinkedHashMap的put方法，由上面LinkedHashMap的分析我们知道LinkedHashMap的put方法是使用父类hashMap的，hashMap的put方法中调用了putVal方法，putVal方法调用了newNode方法，LinkedHashMap只是重写了newNode方法保证了其插入有序性，LinkedHashSet调用put方法是value值设置为了PRESENT，PRESENT是一个object对象，在hasmap源码中定义put(e, PRESENT)中的key值相等，并且hash相等就会将其覆盖，而只要key相等那么hash值必然是相等的，hashMap中是会将其进行覆盖，保证了唯一性
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
