读集合源码
Arraylist
底层数据结构
1 | private Object[] elementData; //元素数据底层数组实现 |
默认构造函数
1 | public MyArrayList(){ |
简单实现增删改查方法
1 | // add方法 |
扩容核心
1 | private int newCapacity(int minCapacity) { |
与Vector的比较
- 与Arraylist相似,除了添加了synchronized保证线成安全,扩容自定义
1
2
3
4
5
6
7
8
9
10// 在add方法上添加了synchronizated
public synchronized boolean add(E e) {
++this.modCount;
this.add(e, this.elementData, this.elementCount);
return true;
}
// 扩容 用户可在初始化阶段指定capacityIncrement的大小
// 没指定就扩容原来的2倍
int newCapacity = oldCapacity + (this.capacityIncrement > 0 ? this.capacityIncrement : oldCapacity);LinkedList
底层数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// 被transient修饰的成员变量不参与序列化过程。
transient int size;
transient LinkedList.Node<E> first; // 记录第一个节点
transient LinkedList.Node<E> last; // 记录最后一个节点
// 构造函数
private static class Node<E> {
E item;
// 底层为双向链表
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}简单实现增删改查方法
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
74
75
76
77
78
79
80
81//add
public void add(E e){
Node l = last; // 保存最后节点
MyLinkedList.Node<E> newNode = new MyLinkedList.Node(l, e, null);
this.last = newNode;
if(l == null) // 集合中没有数据
first = newNode;
else
l.next = newNode;
size++;
}
//set
public E set(int index, E element) {
// 判断index的合理性
if(0 >= index || index >= size){
throw new RuntimeException("不存元素");
}
MyLinkedList.Node<E> x = this.get(index); // 获取当前索引节点
E oldVal = x.item;
x.item = element;
return oldVal;
}
// get
public MyLinkedList.Node<E> get(int index){
// 判断index的合理性
if(0 >= index || index >= size){
throw new RuntimeException("不存元素");
}
MyLinkedList.Node x;
int i;
if(index < size >> 1){ //判断索引在前半部分还是后半部分
x = this.first;
for(i = 0; i < index; i++){
x = x.next;
}
}else{
x = this.last;
for(i = size; i > index; i--){
x = x.prev;
}
}
return x;
}
// remove
public E remove(int index){
// 判断index的合理性
if(0 >= index || index >= size){
throw new RuntimeException("不存元素");
}
// 通过get方法得到该节点
Node<E> x = get(index);
// 保存该节点的信息
E element = x.item;
MyLinkedList.Node<E> next = x.next;
MyLinkedList.Node<E> prev = x.prev;
if(prev == null){
this.first = next;
}else{
// 让当前节点的前一个节点的下一个节点指向当前节点的下一个节点
// 1 <-> 2 <-> 3 删除2
// 1 -> 3
prev.next = next;
x.prev = null;
}
if(next == null){
this.last = prev;
}else{
// 让当前节点的后一个节点的前一个节点指向当前节点的前一个节点
// 1 <-> 2 <-> 3 删除2
// 1 <- 3
next.prev = prev;
x.next = null;
}
x.item = null;
--this.size;
return element;
}HashMap
底层数据结构
1
2
3
4
5
6//底层是 数组和链表和红黑树 结合在一起使用也就是 链表散列。
final int hash;
final K key;
V value;
HashMap.Node<K, V> next;
//HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个对 putVal 方法添加元素的分析如下:
1
HashSet
底层数据结构
1
2
3
4// 底层数据为hashMap
private transient HashMap<E, Object> map;
// HashSet的所有元素的Value值
private static final Object PRESENT = new Object();简单实现增删改查方法
1
Comment