java包为我们提供了很多线程安全（部分安全）的数据集合，涉及线程安全就必然会遇到锁争用和效率上的平衡，其实就是读和写的平衡，读是没有问题的，问题在于写，具体就是如何在写的时候，既不影响读的操作，又能安全地写。
对于并发线程中共享和使用对象的策略，一般可以分为四种：
- 线程封闭
对象仅在线程内部可以访问，如线程内部的封闭变量，或ThreadLocal。 - 只读安全
在读对象时可以保证安全，如不变性的Final对象，或CopyOnWriteArrayList读写分离对象。 - 线程安全共享
对象开放了线程安全的访问方式，如HashTable，这种形式仅能保证单个方法是安全的，而且性能与粒度有关，HashTable是整张表加锁，性能不佳；ConcurrentHashMap是分段加锁，各分段可以并行，性能就好很多。 - 保护对象
需要在在调用代码中通过对象锁来保证安全，这可以保证整个逻辑操作是安全的。
从具体的技术实现来看，concurrent、Collections、android.util等，为我们提供了很多设计思路。
- 加锁处理
实现线程安全，容易想到的就是加锁，例如Hashtable加函数锁，Collections.synchronizedList加对象锁，这种方式的读写性能相对平衡。
这几种加锁并不能保证绝对的线程安全，比如
if(map.containsKey("key")){
map.remove("key");
}
在多线程中，虽然两个函数都加了锁，但是整个“检查-删除”操作并没有加锁，不是原子操作，可能出现线程A和线程B都通过了检查，都做删除操作导致出错（ConcurrentModificationException）的问题。这需要我们在编写代码时自己视情况加锁。
完全锁在性能上最大的问题是无法并行处理，只能串行处理，效率低下。
-
部分加锁
为了优化并行处理效率，有一种思路是把锁的粒度变小，只锁数据集合的一部分，比如ConcurrentHashMap，EventBus就使用了ConcurrentHashMap。
ConcurrentHashMap也是数组+链表的组合，和HashMap不同的是，ConcurrentHashMap有两级数组，第一级数组是16个分段锁，每个分段segment其实是个ReentrantLock可重入锁，相当于16个桶，每个桶里有一个小型的HashMap。
这样，在操作部分数据时，只需要锁一个分段，这样可以并行处理16个分段，只有在全局处理所有数据时，才需要锁定所有16个segment。
因为ConcurrentHashMap的结构更复杂，所以需要使用三个HashKey，根据Key生成第一个key1，根据key1的高位hash出key2，key2决定在哪个segment；根据key1的全值hash出key3，key3决定在哪个HashEntry。
（Java8以后，CurrentHashMap不再使用Segment可重入锁，而是采用transient volatile HashEntry<K,V>[] table数组元素加锁，这样可以对每行数据加锁，更细；同时改为使用数组+红黑树的CAS结构，当数组超过8时，改用红黑树管理） -
重复尝试
不论是整体锁还是部分锁，都是用monitorenter和monitorexit屏障来禁止多线程并行，这是个很重量级的操作，因为线程数量的屏障和上下文的切换都会造成损耗。
所以，有很多“不加锁”的优化思路
自旋
很多场景下，获取锁的时候可能就差一点点时间，所以可以重试几次获取锁，也就是自旋，如果没有拿到锁，就自旋等待一小会儿，这可以避免线程上发生大的开销。当然，自旋需要有自旋次数上限。
concurrentHashMap（Java7）在获取segment锁时，就使用了自旋的概念。
CAS
有些运算，并行出错的可能很小，而且规则固定（比如自增1），这时可以尝试在“不安全”的环境下去做运算，然后对照前后的数据是否符合运算规则，这就是Compare And Swap，从CPU指令基本实现了Compare And Swap。
AtomicInteger等类型就是典型的CAS
其他重复尝试
我们可以自己扩展重复尝试的思路，比如在concurrentHashMap里做size时，如果要锁整个表，代价太大，实际上是分别从每个segment获取数量，再求和，这显然是不安全的，但是如果连续取三次，数据都一致地话，就说明这期间没有数量变化，认为是安全的；如果没有取得一致，再锁整个表。 -
读写分离
除了缩小锁的粒度，还有一种优化方法是从操作维度上，把读操作和写操作分开。
在很多场景下，数据集合主要用来读，很少用来写（比如缓存），这时候可以做一个副本，在副本里写，在原集合里读，读和写不是同一个对象，就是读写分离。
读操作的对象是不变的，不需要加锁，不影响并行效率；
写操作虽然需要加锁，但是使用频率很低，所以综合起来能达到一个较好的平衡。
集合对象不需要加锁，虽然制作副本集合需要复制整个数组，会消耗大量时间，但是只需要对写函数加锁即可（同时把集合做成volatile对象，写之前先刷新一次）；而在写回原集合时，只需要修改原集合的引用，改为指向副本集合，做一个=赋值操作即可，=赋值是个原子操作，也不用加锁。
读写分离的一种典型做法是COW，在Concurrent包里就是CopyOnWriteArrayList和CopyOnWriteArraySet。
如果把CopyOnWriteArrayList视为对象，还可以做复合的数据结构，例如：
Map<Class<?>, CopyOnWriteArrayList<Object>>
这种方式有很明显的读性能好，写性能差的问题，仅适用特定场景。
-
负载因子
任何数据集合都要考虑读和写的平衡问题，HashMap在写的时候，内存越紧凑越好，但是读的时候最好能直接从数组中取到，这两者很难平衡，有时候需要我们根据自己的业务区动态设置，为此，HashMap提供了一个参数load factor负载因子，默认0.75，就是默认在容量达到75%时进行扩容，这其实给我们自己调整要时间还是要内存，留下了操作入口。 -
数组提速
数组提速其实和并行处理没有关系。
android提供了内存更紧凑的数据集合，如SparseArray、ArrayMap等，这些数据集合其实就是用数组代替HashMap实现了键值对的读写，但是数组最大的问题是插入和删除会导致大范围的移动，为尽量提速，android采用了假删除的设计，就是用空对象去替换被删除的对象，这样能避免移动数据带来的开销。 -
key值转换
一般在数据集合中，我们存储key值都是原样存储，虽然数据集合会根据key计算hashcode，也是只是为了把数据打散，均匀存储起来，对key值没有影响。
某些情况下，我们要存储的对象可能不容易对比，比如是个较长的String，用equals判断比较耗时，甚至可能有特殊字符，会带来意外情况。
这时候，直接存储key的原值可能不是个好主意，可以考虑把key做个md5，或者sha-1，转换为一个更安全也更容易对比的key。 -
空队列
有时候队列只是用来快速传递元素，例如okhttp的dispatcher使用的SynchronousQueue，它的容量其实是0，因为它在插入/移除时会等待另一个线程去移除/插入（需要两个线程合作，一个put，另一个take，必须同时操作），这种设计下，元素能以最快的速度从生产者传递到消费者。
SynchronousQueue在OkHttp和CachedThreadPool中都有使用，例如：
public static ExecutorService newCachedThreadPool() {
return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
60L, TimeUnit.SECONDS,
new SynchronousQueue<Runnable>());
}
不同的是，CachedThreadPool是为了尽快new出新的线程，OkHttp则另外用内置参数限制了线程数(共64，每个host不超过5)
- 复用
很多瓶颈的在于资源不足，资源不足的一种常见解决思路是资源的复用，针对IO资源我们会做IO复用（例如Http的KeepAlive），针对内存我们会做内存池复用（例如Fresco的内存池），针对CPU资源，我们一般会做线程复用（例如线程池）。
参考：
ConcurrentHashMap原理分析
网友评论