结构
ArrayList:数组Object[]
LinkedList：链表Node
HashSet：HashMap<E,Object>
HashMap：（数组+链表）Node<K,V>[]+红黑树TreeNode
根据结构就能看出ArrayList使用索引在数组中搜索和读取数据是很快的，可以直接返回数组中index位置的元素，随机访问快，但是删除、插入需要移动后面的元素，开销大。LinkedList每次都要遍历查找，所以查询慢，但是因为存储位置是用指针指向，插入删除快，也因为指针所以内存大一些。
HashSet本质就是基于HashMap，只是插入删除一个键，值默认是Object，而HashMap存的是键值对。利用的是hashCode每次找到bucket来存储和查询，不碰撞的情况就时间复杂度O(1)。
初始化
ArrayList默认大小10,默认数组为空数组
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
LinkedList啥也没有，size是0，头尾节点是null。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
HashSet直接new一个HashSet。
public HashSet() {
map = new HashMap<>();
}
HashMap默认负载因子0.75，为什么是0.75，注释说是是在时间和空间成本的权衡。
默认容量16。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
数据检索-forEach
ArrayList：
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
modCount == expectedModCount用表示这个list只能在当前方法被需修改，ArrayList是线程不安全的，用这种方式保证list在遍历的时候不会别其他线程所修改。这也表示，不能在foreach的时候执行删除，不然也会抛出异常。
LinkedList和HashSet
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
LinkedList和HashSet都没有重写forEach，用的是Iterable的默认实现，直接循环执行，通俗易懂。
HashMap
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
先遍历数组，再遍历链表。也进行modCount判断。由于数组时键值对，所以也有只对键或者只对值遍历的方法。
扩容
ArrayList
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
扩容后的新数组大小是（ oldCapacity + (oldCapacity >> 1)），就是在原数组的长度加上原数组的长度大小的一半(位运算，右移一位相当于整体/2)。
LinkedList不需要扩容。
HashSet就HashMap的。
HashMap
/**
1、初始化，设置容量、阈值，list
2、
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 扩容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
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，进行赋值。容量*负载因子
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 void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this; // 这个this是HashMap的内部类TreeNode的对象，是桶里装的红黑树
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 高低位异或
if ((e.hash & bit) == 0) { // 低位
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else { // 高位
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 拆树
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
// 拆树
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
扩容大小是newThr = oldThr << 1，是原来的两倍。
其实对于数据量小来说，这些对比性能从差异可以忽略不计。
|