读集合源码
每日一句诗词
loading...
loading...
Arraylist
底层数据结构
1 | transient Object[] elementData; //元素数据底层数组实现 |
默认构造函数
1 | public MyArrayList(){ |
简单实现增删改查方法
1 | // add方法 |
扩容核心
1 | private int newCapacity(int minCapacity) { |
elementData 用transient 修饰,序列化后数据会丢失吗
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}不对elementData序列化,对elementData中的元素进行循环,取出来单独进行序列化。
为什么不直接对数组序列化
一般情况下数组是没有存满的,直接序列化会造成空间浪费
与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
7
8
9
10
11
12
13
14//底层是 数组和链表和红黑树 结合在一起使用也就是 链表散列。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// get set equals方法
KEY的hash过程
1 | // 首先取 key值进行 hashcode 算出hashcode赋值给 h , 在用自己的底16位和自己的高16位进行异或 |
这里可以体现为什么HashMap的长度建议为
2的幂次
- 当数组长度为 2 的幂次是 length - 1就刚好所有的二进制全为 1
不是2的幂次,则算出的length - 1就会存在一些位置为 0,而0进行&操作,就一定为0,增加了hash冲突概率
扩容过程
1 | // 关键构造函数 |
负载因子越大则散列表的装填程度越高也就是能容纳更多的元素,元素多了,链表大了,所以此时索引效率就会降低。
负载因子越小则链表中的数据量就越稀疏,此时会对空间造成浪费,但是此时索引效率高。
扩容大小
1 | final V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
HashTable和HashMap区别
- 继承的父类不同 Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类。
- 线程安全性不同
Hashtable 中的方法是Synchronize的,而HashMap中的方法在缺省情况下是非Synchronize的。
- key和value是否允许null值
1 | #################### hashMap ##################### |
- 内部实现使用的数组初始化和扩容方式不同
Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。 Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11,增加的方式是 old*2+1。
HashSet
底层数据结构
1 | // 底层数据为hashMap |
ConcurrentHashMap
核心构造函数
1 | public ConcurrentHashMap(int initialCapacity, |
concurrencyLevel:并行级别、并发数、Segment 数,怎么翻译不重要,理解它。默认是 16,也就是说 ConcurrentHashMap 有 16 个 Segments,所以理论上,这个时候,最多可以同时支持 16 个线程并发写,只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值,但是一旦初始化以后,它是不可以扩容的。
currenthashmap是如何保证并发的
JDK8中彻底放弃了Segment转而采用的是Node,其设计思想也不再是JDK1.7中的分段锁思想。
Node:保存key,value及key的hash值的数据结构。其中value和next都用volatile修饰,保证并发的可见性。
Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样,不过保证线程安全性。
1 | // 在高版本的JDK中,抛弃了桶设计,大量使用了 CAS + Volatile + Synchronized来实现并发安全 |
LinkedHashMap实现LRU
介绍LinkedHashMap维护的两种顺序,插入顺序和访问顺序
1 | LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16,0.75f,true);; |
插入顺序:
f: =>1
s: =>2
t: =>3
访问顺序:
f: =>1
s: =>2
t: =>3
1 | LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16,0.75f,true); |
插入顺序:
f: =>1
s: =>2
t: =>3
访问顺序:
f: =>1
t: =>3
s: =>2
实现代码
1 | public class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> { |