概览
List
- ArrayList 实现了RandomAccess，可随机读取。可指定初始空间大小，默认为10，超过此空间，数组空间增加以前的一半
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
//数组的定义
transient Object[] elementData;
//初始化 默认大小 是10
private static final int DEFAULT_CAPACITY = 10;
//有意思的是 也定义了最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//初始化
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//实现原理是 创建一个Object类型的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
transient 一个对象只要实现了Serilizable接口，这个对象就可以被序列化,某个属性不需要序列化，就可以用这个关键字
image
- 扩容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//扩容大小是右移一位，比如初始化是10 即1010(10)右移一位变成0101(5)
//新的容量=old容量+old/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 然后把原来的数据复制到
elementData = Arrays.copyOf(elementData, newCapacity);
}
其他方法比较简单，这里不写了。
LinkedList：通过实现AbstractSequentialList来实现随机的索引读取。每个节点是Node,存有两个指针Next，Prev,是个双向链表。初始size=0，动态增加，不需预先分配空间，且实现了queue接口，可以查看首（first）尾(last)元素.
public class LinkedList<E> extends AbstractSequentialList<E>
//实现了deque接口
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
//初始化为0
transient int size = 0;
- 比较一下两个
| 0 | ArrayList | LinkedList |
|---|---|---|
| 算法 | 数组 | 链表 |
| 优势 | 随机读取效率高 | 头尾节点插入、删除效率高 |
| 内存占用 | 需要预留空间和扩容，内存占用大 | 内存占用小 |
| 遍历 | 效率接近 | 需要用iterator遍历 |
-
获取线程安全的list
- 普通版
/**
* 获取一个线程安全的LinkedList
*/
List synLinkedList = Collections.synchronizedList(new LinkedList());
/**
* 获取一个线程安全的ArrayList
*/
List synArrayList = Collections.synchronizedList(new ArrayList());
或者
- Vector (ArrayList线程安全低配版 )
- 效率比arrayList差，一般不用，大部分方法都用synchronized修饰
- CopyOnWriteArrayList (ArrayList线程安全高配版 )
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
/** 加锁 */
final transient ReentrantLock lock = new ReentrantLock();
/** 数组定义 用 volatile */
private transient volatile Object[] array;
- 插入
public boolean add(E e) {
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//先复制一个新的数组 然后插入到新的数组中
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
- 对比
- 读没有加锁，所以不是绝对线程安全的。类似读写分离
- 读性能比vector高，所以适合读多写少的场景。
Map
HashMap
- 理想状态的hash算法是哈希表中的元素都是正常分布(不存在冲突)的,get,put操作时间复杂度都是O(1)
- K,V都可为null，所以get() 为null,不能判断k为null，有可能是v为null,所以需要用containskey判断
- 支持fail-fast
- 当集合迭代时，其他线程修改了该线程，会抛出这个错误。
- 迭代器 Iterator
- 结构图
- HashMap采用数组链表的结构<拉链法>来处理冲突，将散列到同一位置的数据头插法插入一个链表。
- 在java8中，当链表的长度大于8的时候将这个链表重构成红黑树。
image
- 两个影响性能的重要因素。初始容量initial capacity:16和负载因子local Factor:0.75：两个影响性能的重要因素。
/**
* 默认初始容量16，指的是桶的数量(数组的长度)，必须是2的N次幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
/**
* 最大的容量，可以在构造的时候传入参数，但是必需是小于2的30次幂=1073741824
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的负载因子0.75，即使用容量超过初始容量*0.75必须扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表转红黑树的阈值，大于这个值转换
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树转链表的阈值，小于这个值转换
*/
static final int UNTREEIFY_THRESHOLD = 6;
- hashMap结构
/**
* 哈希表，每个节点是Node<K,V>结构，容量总是保持2的N次幂。
*/
transient Node<K,V>[] table;
- 节点 Node<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
/**
* 1 这个Next仍然是个Node 这种结构决定了头插法来链接链表的节点。
* 2 也说明了get()时它连K，V一起存**储的，碰撞的时候hash值相同，我们也可以比较K的值来确定要返回的Value
*/
Node<K,V> next;
……
}
- 扩容
final Node<K,V>[] resize() {
……
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;
}
……
- get()
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 每次都需要一直检查 first node
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) { //如果不是 则往下找
if (first instanceof TreeNode) //如果是树形Node，则调用TreeNode的get方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//否则直接查询Next比较Key值。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
hashTable
线程安全
K,V都不允许为null
迭代器：Enumeration（枚举类）
定义
//类型
private transient Entry<?,?>[] table;
//Entry<K,V>定义
private static class Entry<K,V> implements Map.Entry<K,V> {
// hashMap是node<> 但是结构都是一样的
static class Node<K,V> implements Map.Entry<K,V> {
- 初始化
//初始容量：11，负载因子：0.75f
public Hashtable() {
this(11, 0.75f);
}
- get()
//是线程安全的
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//索引位置计算
int index = (hash & 0x7FFFFFFF) % tab.length;
//实现方式和hashMap有很大的不同
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
ConcurrentHashMap
- HashMap的线程安全版
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
//与hashMap不同的地方 用了volatile修饰
//保证了val被修改时线程可见性,无需加锁便能实现线程安全的读操作。
volatile V val;
volatile Node<K,V> next;
-
比Hashtable更高效的并发性能
- 使用分离锁的思路解决并发性能，其将Entry数组拆分至16个Segment中，以哈希算法决定Entry应该存储在哪个Segment。在写操作时只对一个Segment加锁（hashMap对整个Entry加锁），大幅提升了并发写的性能。
-
缺点 :不能保证读操作的绝对 一致性
- 如果写操作在创建一个Entry,在写操作完成之前(会加锁)，读操作不一定可以读到这个Entry。
| 对比 | HashMap | Hashtable | Hashtable |
|---|---|---|---|
| 线程安全 | 否 | 是 | 是(不能保证数据绝对一致) |
| 性能 | 最好 | 最差 | 中间 |
TreeMap
- TreeMap是基于红黑树实现的Map结构，其Entry类拥有到左/右叶子节点和父节点的引用，同时还记录了自己的颜色
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
- 适合需要对key进行有序操作的场景。
- 提供了一系列方便的功能，比如获取以升序或降序排列的KeySet()、获取在指定key()之前/之后的key()等等
TreeSet
- 基于TreeMap构造的Set，基本操作都是TreeMap的操作
HashSet 基本上就是用了hashTable
- 结构
public HashSet() {
//直接就用了HashMap 真省事
map = new HashMap<>();
}
- add() 就是做了不能存储重复value的操作
// Dummy value to associate with an Object in the backing Map 这个是不会重复的
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
- 存储单值选hashSet（前提是数据不重复，否则就会丢失数据）查找速度理想是O(1)
结构类似 只是简单封装
graph LR
HashMap-->HashSet
graph LR
TreeMap-->HashSet
