集合
Collection
ArrayList
- 实现了List接口
- 底层数据结构为数组
- 允许存储null值
- 线程不安全
- 可以通过Collections.synchronizedList转换为线程安全的list，就是为各个操作上锁，通过构造函数可以自定义加锁对象
- 插入非尾部数据时，会移动对象，导致插入效率低
- 插入前会检查数组大小，当数组大小不足时会进行扩容操作，扩容时创建一个新的数组，容量为旧数组的1.5倍左右
newCapacity = oldCapacity + (oldCapacity >> 1)，扩容后旧数组数据被复制到新数组
LinkedList
- 实现了List和Deque接口
- 底层数据结构为链表
- LinkedList既可以当做有序列表，也能当做队列和栈使用
Queue && Strack
- Queue是一个接口，Strack是一个类
- Queue和Strack目前都推荐使用ArrayDeque, 次选LinkedList，Strack已经不推荐使用了
- ArrayDeque基于循环数组实现
- ArrayDeque不能添加null元素
ProrityQueue
- ProrityQueue实现Queue接口
- 不允许存储null
- 每次返回权重最小的节点
- 权重计算根据元素自然顺序或构造器传入的比较器计算
- 底层实现为完全二叉树（任意一个非叶子节点的权值都不大于其左右节点的权值）
- 数据存储使用的数组，
leftNode = parent * 2 + 1，rightNode = parent * 2 + 2，parent = (child - 1) / 2
HashMap && HashSet
- HashSet仅是对HashMap的一层封装，内部实现基本一致
- HashMap数据结构为Entry，每个Entry包含一个key，一个value
- HashMap有两个构造参数，初始容量和负载因子，当存储的数据个数达到两者的乘积时触发扩容，扩容大小为原来的2倍，扩容后会重新计算key的位置
- HashMap JDK7底层为数组+链表(冲突链表方式)，JDK8为数组+链表+红黑树(链表长度大于等于8时会转为红黑树)
- HashMap put元素时，如果有Hash冲突，采用头插法添加新元素
- HashMap的内存是在第一次put操作时分配的
LinkedHashSet && LinkedHashMap
- LinkedHashSet仅是对LinkedHashMap的一层封装，内部实现基本一致
- LinkedHashMap是HashMap的直接子类，只是采用双向链表将node连接在了一起，遍历的时候直接从头开始
- LinkedHashMap可用于实现LRU缓存
/**
* 基于LinkedHashMap实现的LRU
* @author fan
*/
public class LinkedHashMapCache<K, V> extends LinkedHashMap<K, V> {
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private final int initialCapacity;
/**
* 初始化大小
* @param initialCapacity 初始值大小
*/
public LinkedHashMapCache(int initialCapacity) {
// 当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
super(initialCapacity, DEFAULT_LOAD_FACTOR, true);
this.initialCapacity = initialCapacity;
}
/**
* 是否移除最旧的数据
* @param eldest 最旧的节点
* @return 是否移除最旧的节点
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return this.size() > initialCapacity;
}
}
TreeSet && TreeMap
- TreeSet只是对TreeMap的一层封装
- TreeMap实现了SortedMap接口，可以按照key的大小顺序对其中的元素排序
- 排序默认按照key的自然顺序，也可以在构造器中传入自定义的比较器
- TreeMap底层实现为红黑树
