容器主要包括Collection和Map两种，Collection存储着对象的集合，而Map存储着键值对（KV）的映射表。
Collection：
- Set
- SortedSet(Interface)--->TreeSet
- 基于红黑树实现，支持有序性操作，查找时间复杂度O(logn)
- HashSet
- 基于哈希表实现，支持快速查找，时间复杂度O(1)，但不支持有序性操作，散列表无序
- LinkedHashSet
- 具有hashSet的查找效率，内部使用双向链表维护元素的插入顺序。
- SortedSet(Interface)--->TreeSet
- List
- ArrayList
- 基于动态数组实现，但它是线程不安全。支持随机访问。
- Vector
- 跟ArrayList类似，线程安全，是java遗留类，性能太低。
- LinkedList
- 基于双向链表实现，只能顺序访问，可以快速插入删除元素，还可以实现队列，栈，双向队列。
- ArrayList
- Queue
- LinkedList
- 可以实现双向队列
- PriorityQueue
- 基于优先级堆的无界队列，分为大顶堆，小顶堆
- LinkedList
Map
- TreeMap
- 基于红黑树实现。
- HashMap
- 基于哈希表实现
- HashTable
- 跟HashMap类似，但线程安全，遗留类。可以使用Collections的Synchronized的方法
- ConcurrentHashMap也可以解决线程安全问题
- LinkedHashMap
- 基于双向链表，来维护元素的顺序，顺序一般为插入顺序，或者LRU（最近最少未使用）顺序。
容器中的设计模式
- 迭代器模式
- Collections继承了Iteatable接口，其中iteator方法能够产生一个iteator对象，通过这个对象可以迭代遍历Collection中的元素。
- 使用foreach可以遍历实现了Iteatable集合中的对象
- 适配器模式
- java.util.Arrays#asList()
- 将数组类型转换成List类型
- 一般建议这样
- List list=new ArrayList<>(Arrays.asList("a","b"));
ArrayList详解
- ArrayList基于动态数组实现，支持快速随机访问，RandomAccess接口标识着支持随机访问。
- 数组默认大小为10
- private static final int DEFAULT_CAPACITY=10
- 扩容
- 添加元素时使用ensureCapacityInternal()，保证容量足够。如果不够，使用grow进扩容
- 新容量是oldCapacity+oldCapacity<<1也就是原来的1.5倍。
- 扩容需要调用Arrays.copyOf，把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建ArrayList就指定大小。
- 删除元素
- 需要调用System.arraycopy(),将index+1后面的元素都复制到index上，时间复杂度O(N)
- 可以看到ArrayList删除元素的代价贼大。
- 序列化
- ArrayList基于数组实现，并且具有动态扩容，因此保存元素的数组不一定都会被使用。么必要全部序列化
- 保存元素的数组elementData使用transient修饰，该关键字声明数组不会被序列化。
- ArrayList实现了WriteObject和ReadObject来控制序列化的内容。
- 序列化时需要使用ObjectOutputStream中的WriteObject将对象转为字节流输出，而writeObject方法在传入对象存在writeObject（）时，会去反射调用该对象的writeObject。
- 反序列化readObject一样。
- Fail-Fast
- ArrayList是快速失败的。modcount用来记录ArrayList结构发生变化的次数，在进行序列化或者迭代等操作时，需要比较操作前后modcount是否改变，如果改变了需要抛出ConcurrentModificationException.并发修改异常。
- ArrayList安全方案
- Collections.synchronizedList()
- ConcurrentHashMap()
Vector详解
- 同步
- 他的实现跟ArrayList类似，但是使用了synchronized同步。
- 扩容
- 每次扩容是原来的二倍。
CopyOnWriteArrayList
- 读写分离
- 写操作在一个复制数组上进行，读操作还是在原来数组进行，读写分离。
- 写操作需要加锁，防止并发写入，导致数据丢失。
- 写操作结束之后需要把原始数组指向新的复制数组。
- 适用场景
- CopyOnWriteArrayList在写操作的同时，允许读操作，大大提高读操作的性能
- 适用于读多写少的场景
- 缺点
- 内存占用：复制数组，双倍内存
- 实时性得不到保障
- 不适合在内存敏感以及对实时性要求很高的场景。
LinkedList详解
- 双向链表使用Node存储节点信息
- 每个链表节点存储着first指针，last指针。
- 与ArrayList比较
- ArrayList基于动态数组，LinkedList基于双向链表实现。
- 数组支持随机访问，插入删除代价大
- 链表不支持随机访问，插入删除代价小，改变指针。
HashMap详解
- JDK1.7版本
- 存储结构：数组+链表：内部包含了一个Entry类型的数组table，Entry存储着键值对，它包含了四个字段，Entry是一个链表，即数组中的每个位置被当成一个桶，一个桶存放一个链表。
- HashMap使用拉链法来解决冲突，同一个链表中存储着哈希值和散列桶取模相等的Entry
- 拉链法的工作原理：
- 新建HashMap，默认大小是16
- 插入键值对，先计算hashCode值，使用除留余数法得到桶下标
- 若桶内有元素，使用头插法插入到链表头部。
- 查找需要分两步
- 计算键值对所在的桶
- 在链表上顺序查找。JDK1.8以后优化成了红黑树
- put操作
- 需要注意的是HashMap允许插入键为null的键值对，但是因为无法调用null的hashcode方法，也就无法确定下标，只能通过强制指定一个桶下标来存放。hashmap使用第0个桶存放键为null的键值对。
- 判空完之后确定桶的下标
- int hash=hash（key）
- int i=indexFor(hash,table.length)
- 计算hash值
- h&(length-1)，位运算速度更快。只要能确定capacity是2的次数。
- 扩容
- 为什么要动态扩容？
- HashMap的table长度M，需要存储的键值对N，如果哈希函数满足均匀性要求，则每条链表长度为N/M，查找复杂度O(N/M)，为了让查找速度快，尽可能是M大，所以要动态扩容。
- 和扩容相关的主要参数有：
- capacity：table容量大小，默认16,2的n次方。
- size：键值对的数量
- threshold：size的临界值，当size大于等于threshold就必须进行扩容。
- loadFactor:装载因子，threshold=capacity*loadFactor.默认0.75.
- 扩容，变为原来的两倍。
- 使用resize，需要把原来的数据全部移入到新表中，很耗时。
- 需要重新计算桶的下标，由于容量都是2的n次方，所以原来是16的现在是32
- 计算数组容量
- HashMap允许传入容量不是2的n次方，他可以自动变成2次方。
- 链表转红黑树
- 当链表长度大于等于8，就会将链表转成红黑树，小于等于6就会将红黑树转成链表。
- HashTable比较
- hashTable使用synchronized同步，线程安全。
- HashMap可以插入键为null的entry
- HashMap是fail-fast
- HashMap不能保证map中元素次序不变。
- ConcurrentHashMap
- ConcurrentHashMap和 HashMap类似，最主要的差别是使用了分段锁
- Segment，每个分段锁维护几个桶，多个线程可以同时访问不同分段锁上的桶，并发度更高，并发度取决于segment的个数。
- segment继承与ReentrantLock，因此具有锁的特性。
- 默认并发级别16，默认创建16个分段锁。
- 每个Segment维护一个count来统计该segment上的键值对个数。
- 在执行size操作时，需要遍历segment然后把count加起来。
- ConcurrentHashMap在进行size操作时，先尝试不加锁，如果连续两次不加锁操作得到的结果一致，那就说明结果正确。
- 尝试次数可以用RETRIES_BEFORE_LOCKS定义初始值-1，若该值为2，次数为3.
- 如果尝试次数超过三次就加锁。
- 为什么要动态扩容？
- JDK1.8的改动
- 1.7采用的是分段锁机制，核心类为Segment
- 1.8采用的是CAS+synchronized,在CAS失败后，采用内置锁synchronized。
- 链表长度超过8，采用红黑树。
LinkedHashMap
- 继承自HashMap，因此具有快速查找的特性。
- 内部维护了一个双向链表，用来维护插入顺序，或者LRU顺序。
- accessOrder决定了顺序，默认为false，此时维护的是插入顺序。
- LinkedHashMap用以下两个函数维护顺序。
- void afterNodeAccess(Node<K,V> p){}
- void afterNodeInsertion(boolean evict){}
- afterNodeAccess()
- 当AccessOrder为true，就会将节点移到链表尾部，也就是说指定LRU顺序以后，每次访问一个节点，就将这个节点移动到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未访问。
- afterNodeInsertion()
- 在put操作后，当removeEldestEntry()方***返回true，会移除最晚的节点，也就是链表首部的节点。
- LRU缓存
- 需要继承LinkedHashMap实现LRU缓存，通过移除最近最久未使用达到缓存空间释放，存储的都是热点数据。
- 实现如下：
- 设定最大缓存空间，MAX_ENTRIES=3
- 使用LinkedHashMap的构造函数将AccessOrder设置为true，开启LRU顺序。
- 覆盖removeEldestEntry，在节点多余最大空间数，就LRU移除。
class LRUCache<K,V> extends LinkedHashMap<K,V>{ private static final int MAX_ENTRIES=3; protected boolean removeEldestEntry(Map.Entry eldest){ return size()>MAX_ENTRIES; } LRUCache(){ super(MAX_ENTRIES,0.75f,true); } }
WeakHashMap
- weakHashMap的Entry继承自weakReference，被weakReference关联的对象在下一次垃圾回收会被回收。
- WeakHashMap主要用来实现缓存，通过WeakHashMap来缓存对象，JVM回收缓存。
ConcurrentCache
- Tomcat中的ConcurrentCache使用了WeakHashMap来进行缓存。
- ConcurrentCache 使用的是分代缓存。
- 经常使用的对象放入Eden区，Eden区使用的是ConcurrentHashMap实现，不同担心被回收
- 不经常使用的放到longterm,使用WeakHashMap实现，这些老对象被垃圾回收。
- 当调用get方法，先从Eden找，找不到去longterm找，然后放入Eden，保证Eden是经常被访问的
- 如果Eden大小超过size，就将Eden所有对象放入longterm，然后利用虚拟机回收一部分。
public final class ConcurrentCache<K, V> { private final int size; private final Map<K, V> eden; private final Map<K, V> longterm; public ConcurrentCache(int size) { this.size = size; this.eden = new ConcurrentHashMap<>(size); this.longterm = new WeakHashMap<>(size); } public V get(K k) { V v = this.eden.get(k); if (v == null) { v = this.longterm.get(k); if (v != null) this.eden.put(k, v); } return v; } public void put(K k, V v) { if (this.eden.size() >= size) { this.longterm.putAll(this.eden); this.eden.clear(); } this.eden.put(k, v); } }
京公网安备 11010502036488号