ArrayList
ArrayList基于可变数组： Object[] ={ }，初始容量为10。private static final int DEFAULT_CAPACITY = 10;
1.扩容
newCapacity = oldCapacity + (oldCapacity >> 1) 正整数 向下取整
10 15 22 33elementData = Arrays.copyOf(elementData, newCapacity);新建一个更大的数组，将旧的数组数据copy，如果数据很多，尽量初始化时设定容量大小，不用在添加的过程中不断扩容。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!size从0开始的
elementData[size++] = e;
return true;
}
//
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity); //如果添加
}
return 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);
}
//
2. 删除
System.arraycopy(elementData, index+1, elementData, index, numMoved)将Index+1后的元素复制到index上，这里用的是System.arraycopy，add(E e)用的Arrays.copyof，Arrays.copyof内部新建一个数组，然后用System.arraycopy来实现，
1 | public E remove(int index) { |
2.1 序列化
序列化：一个对象可以被表示为一个字节序列，包括该对象的数据、对象的类型信息和存储在对象中数据的类型。序列化对象可以写入文件，读取文件，进行反序列化。需要实现Serializable接口，这个接口是个空的，只是用来表明改类可以序列化，在writeObject方法中，用来检测是否是Serializable实例if (obj instanceof Serializable)。用关键字transient来表明类中的属性不必序列化。public final void writeObject(Object x) throws IOException方法序列化对象，在ObjectOnputStream中public final Object readObject() throws IOException, ClassNotFoundException方法反序列化对象，在ObjectInputStream类中。
ArrayList中elementData是变化的，不一定都会被使用，用transient修饰，不用全部序列化
Vector
vector是线程安全的，使用了synchronized来实现同步，因此速度相对较慢。扩容与ArrayList类似，不过每次扩容增加一倍1
2
3
4
5
6
7
8
9
10
11private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);//这里是*2
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList也能实现线程安全1
2List<Integer> list=new ArrayList<>();
List<Integer> synList=Collections.synchronizedList(list);
或者使用concurrent并发包List<Integer> list=new CopyOnWriteArrayList<>();
LinkedList
简单的双向链表来实现，初始size=0，有两个引用，first,last指向链表的首尾，
只能顺序访问，ArrayList是随机访问，更快
节点：1
2
3
4
5
6
7
8
9
10
11private 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;
}
}
1. 插入
有三个方法：linkFirst(E e), linkLast(E e), linkBefore(E e, Node<E> succ)
2. 查找
1 | Node<E> node(int index) { |
3. 删除节点
1 | Node<E> node(int index) { |
HashMap
数组、链表、红黑树(1.8开始的，链表长度阈值为8，大于时转换为红黑树)
key可以是 null，放在了 table[0] 上，key的hash方法：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
得到hash值后，判断在 table 上的位置：hash % n == (n - 1) & hash，因为这个原因使容量是2的倍数。在初始化时，若输入的不是2的倍数，自动转化为2的倍数。1
2
3
4
5
6
7
8
9static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
几个属性：
int threshold; //阈值，超过会扩容(capacity * load factor).
final float loadFactor; //加载因子，可以理解为现有数据比上总容量，
transient int size; //键值对数量
transient Node<K,V>[] table; //数组
Node<K, V> 数组，包含四个字段，K key，V value, Node<K, V> next, int hash, 数组中每个数据是一个链表的头节点，next 指向下一个。
put And get
- put方法。插到链表尾部
a. 若 table 为 null，初始化 table 数组； b. 通过 hash 找出数组下标。若为空，插入。 c. 如数组非空，沿着链表找尾部并插入，链表太长，转成红黑树。 d. 如果链表有结点和要插入的相同，根据规则是否覆盖旧值。 e. 数量大于阈值，则扩容。 - get方法
和put方法中类似，先散列到表中，再根据 key 和 Hashvalue 找节点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //数组table为空的时候，resize()
if ((p = tab[i = (n - 1) & hash]) == null) //hash % n == (n - 1) & hash，散列在表中的位置
tab[i] = newNode(hash, key, value, null);
else { //存在链表
Node<K,V> e; K k; //e指向查找到的节点或者（没有）新建一个
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //和插入的新Node在table[i]上
else if (p instanceof TreeNode) //红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //链表
for (int binCount = 0; ; ++binCount) { //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;
}
if (e.hash == hash && //链表中有该key
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
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;
}
扩容
- 如果 oldCapacity （ table.length ）>0，
- 大于 MAXIMUM_CAPACITY = 1 << 30; 新阈值取最大值 Integer.MAX_VALUE;
- 小于 MAXIMUM_CAPACITY = 1 << 30；
2.1. 新容量（oldCapacity 的2倍）若小于 MAXIMUM_CAPACITY 并且大于等于 DEFAULT_INITIAL_CAPACITY=16，则阈值变为2倍
- 如果 oldCapacity =0
- 如果 oldThr > 0, 新容量等于 oldTHr
- 如果 oldThr=0, 新容量等于 DEFAULT_INITIAL_CAPACITY（16）; 新阈值等于 16*0.75=12，这个是初始化。
(e.hash & oldCap) 得到的是 元素的在数组中的位置是否需要移动,示例如下
示例1：
e.hash=10 0000 1010
oldCap=16 0001 0000
& =0 0000 0000 比较高位的第一位 0
元素位置在扩容后数组中的位置没有发生改变
示例2：
e.hash=17 0001 0001
oldCap=16 0001 0000
& =1 0001 0000 比较高位的第一位 1
元素位置在扩容后数组中的位置发生了改变，新的下标位置是原下标位置+原数组长度
将一个[j]链表上的所有结点，转到新的上面，同一链表rehash不一定是相同的，如果扩容后不需要该表数组位置，用lohead、lotail在原下标组成新的链表，换位置的用hihead、hitail组成新的链表。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74final 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; //oldCapacity=0,但是oldThr>0,让新容量等于oldThr
else { // zero initial threshold signifies using defaults
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 = 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) { //原先的值进行重新计算hash
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//只在table[i]上有值
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;//低位，即原table[i]
Node<K,V> hiHead = null, hiTail = null;//高位，table[i+OldCapacity]
Node<K,V> next;
//链表上的节点rehash
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;
}
remove
先找到 table[i]：条件p = tab[index = (n - 1) & hash，
然后判断是否是 table[i]，条件：p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
如果不是，从树中或者链表中查找。判断条件：node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { //table非空，长度大于0，table[i]非空
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //table[i]是要移除的
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //从红黑树找
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//树中移除
else if (node == p) //在table[i]上
tab[index] = node.next;
else //p在Node之前
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}