0.零散知识点
- 一般在使用java的集合的时候，需要使用接口类型来存放引用，方便后续修改
- HashSet是基于散列表的集
- TreeSet是基于红黑树的集
一.collection
集合接口继承图
1. Set
-
TreeSet
- 基于红黑树，查找效率O(logn)
- 实现了SortedSet接口
-
HashSet
- 基于Hash表实现，支持快速查找，但失去了插入的顺序
-
LinkedHashSet
- 具有HashSet的查找效率，且内部使用双向链表维护插入顺序
2.List
- Arraylist
- 使用Collection.synchronizedList(list)来保证线程安全
- Vector
- 线程安全
- LinkedList
- 双向链表，顺序访问，用于stack以及Queue
3.Queue
- LinkedList
- Deque
- 是实现LinkedList以及ArrayDeque的双端队列
- PriorityQueue
- 是基于heap（小根堆）实现的优先级队列
二.Map
Map接口继承
- TreeMap
- HashMap
- HashMap底层是用数组+双向链表+红黑树实现的
- 线程不安全
- 替代方法，HashTable，ConcurrentHashMap,前者是遗留类不使用，后者是引入了分段锁的安全类(1.7)
- JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。
- HashMap的插入
- 如果数组还没有初始化（数组长度是0），则先初始化
- 通过hash方法计算key的hash值，进而计算得到应该放置到数组的位置
- 如果该位置为空，则直接放置此处
- 如果该位置不为空，而且元素是红黑树，则插入到其中
- 如果是链表，则遍历链表，如果找到相等的元素则替换，否则插入到链表尾部
- 如果链表的长度大于或等于8，则将链表转成红黑树
- LinkedHashMap
- 双向链表的HashMap,顺序为插入顺序以及LRU
- 其中的removeEldestEntry()方法可以维持LinkdeHashMap的大小，当大于容量的时候，就把最远未访问的值删除
public class LRUCache<K, V> extends LinkedHashMap<K,V> {
/**
*
*/
private static final long serialVersionUID = 1L;
private static final int MAX_LEN = 3; //LRUCache的最大容量
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { //覆盖掉LinkedHashMap当中的方法
return size()>MAX_LEN; //大于缓存容量的时候就删除最老的
}
LRUCache(){
super(MAX_LEN,0.75f,true); //实现父类的构造方法，true的话是LRU，访问到某个元素就会将该元素的位置提到Map前
//当参数未false或者为默认参数，则按照进入Map的顺序进行进行排序，访问某个元素并不会改变其位置
}
}
- WeakHashMap
- WeakHashMap 的 Entry 继承自 WeakReference，被WeakReference 关联的对象在下一次垃圾回收时会被回收。
- WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。
