【Java高性能数据结构】

1 ThreadLocal

多线程环境常用

1.1简介

1. 误认为“本地线程”，其实其并不是一个Thread，而是Thread局部变量，也许命名 ThreadLocalVariable更好
2. 其维护变量，为每个使用变量的线程提供独立副本，因此每个线程能独立改变自己的副本，不会影响其它线程所对应的副本
3. 从线程角度看，目标变量像线程本地变量，正如“local”表达意思

1.2接口方法

1. void set(Object value)
   设置当前线程的线程局部变量的值
2. public Object get()
   该方法返回当前线程所对应的线程局部变量
3. pubilc void remove()
   删除当前线程局部变量值，目的为了减少内存的占用，JDK5.0新增。
   当线程结束之后，该线程局部变量自动被垃圾回收，所以显示调用该方法清除线程的局部变量不是必须得操作，但可以加快内存回收的速度
4. protected Object initalValue()
   返回该线程局部变量的初始值，该方法是一个protected方法，显然是为了让子类覆盖而设计的，ThreadLocal中的缺省实现直接返回null

1.3 实现原理

set和get源码

1. get源码
   
   
2. set源码
   
   

1.4 代码分析

• ThreadLocal都是先获得当前线程的引用，然后得到线程局部变量，最后以ThreadLocal作为key，设置或者获取value
• 线程本地变量是ThreadLocalMap变量，其为一种哈希表
• 整个过程没有任何同步操作，因此性能很高

1.5 与其它同步机制的比较

1. 都是为了解决多线程中变量访问冲突的问题
2. 同步机制通过对象锁机制保证同一时间只有一个线程访问变量，此时该变量多个线程共享。同步机制要求程序员分析何时对变量进行读写，何时锁定对象，何时释放锁，设计和编写难度较大
3. ThreadLocal从另一个角度来解决多线程的并发访问，它为每一个线程提供独立变量副本，从而隔离多个线程对数据的访问冲突，因此每个线程都有自己的独立变量副本，也就没有必要对该变量进行同步

1.6 ThreadLocal和同步机制适用范围

• ThreadLocal不能替代同步机制，两者面向问题不同。
• 同步机制是为了同步多个线程对相同资源的并发访问冲突，是为了多个线程之间进行通信的有效方式
• ThreadLocal是隔离多个线程的数据共享，从根本上就不在多个线程之间共享资源，当然无需对多个线程进行同步
• 如果你想进行多线程通信，则使用同步机制；如果需要隔离多个线程间共享冲突，可以使用ThreadLocal，这将极大简化你的程序，使其更加易读、简洁

1.7 ThreadLocal的应用场景

➢ 订单处理包含一系列操作：减少库存量、增加一条流水台账、修改总账，这几个操作要在同一个事务中完成，通常也即同一个线程中进行处理，如果累加公司应收款的操作失败了，则应该把前面的操作回滚，否则，提交所有操作，这要求这些操作使用相同的数据库连接对象，而这些操作的代码分别位于不同的模块类中
➢ 银行转账包含一系列操作： 把转出帐户的余额减少，把转入帐户的余额增加，这两个操作要在同一个事务中完成，它们必须使用相同的数据库连接对象，转入和转出操作的代码分别是两个不同的帐户对象的方法
➢ 例如Strut2的ActionContext，同一段代码被不同的线程调用运行时，该代码操作的数据是每个线程各自的状态和数据，对于不同的线程来说，getContext方法拿到的对象都不相同，对同一个线程来说，不管调用getContext方法多少次和在哪个模块中getContext方法，拿到的都是同一个​​

1.8 综述

对多线程资源共享问题，同步机制采用“以时间换空间”方式，而ThreadLocal采用“以空间换时间”方式。前者仅提供一份变量，让不同线程排队访问，后者为每一个线程提供一份变量，因此可以同时访问不受影响

2 CopyOnWriteArrayList

2.1 简介

• CopyOnWriteArrayList是ArrayList的一个线程安全的变体，即可在并发环境中使用。而它的可变操作都是通过对ArrayList中存储的数组通过一次新的复制来实现的。
• 当列表进行修改（add、remove等）操作时，先lock，然后copy一份，也就是先复制一份当前的数据存储结构，然后进行相应的操作。
• 让get操作从同步中释放出来，因为对数据的改变会在副本中进行，所以不需要同步，只是有可能读到脏数据，但对于某些应用来说，问题不大，适合于少量写大量读取的情况

2.2 出现背景

• ArrayList是比较常用的一个可变大小的数组集合，但是不能同步。如果多个线程同时访问一个ArrayList实例，其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。
• ⼀般通封装对象进⾏同步操作来完成，如果不存在这样的对象，则应该使⽤ Collections.synchronizedList ⽅法将该列表“包装”起来：List list = Collections.synchronizedList(new ArrayList(…));
• 此类的 iterator 和 listIterator ⽅法返回的迭代器是快速失败的：在创建迭代器之后，除⾮通过迭代器⾃身的 remove或 add ⽅法从结构上对列表进⾏修改，否则在任何时间以任何⽅式对列表进⾏修改，迭代器都会抛出ConcurrentModificationException。因此，⾯对并发的修改，迭代器会完全失败，⽽不是冒着在将来某个不确定时间发⽣任意不确定⾏为的⻛险

2.3 内部实现

• 内部的存储结构采用的是数组，且操作时用ReentrantLock进行锁操作
  
  
• Arrays.copyOf内部使⽤System.arraycopy函数拷⻉数据，因为System,arraycopy函数是native的，效率⽐⾃⼰写的数组拷⻉，效率更⾼
• CopyOnWriteArrayList的add函数add函数添加之前，先加锁创建⼀个数组，数组⻓度在当前基础上加1，同时复制所有旧数组数据到新数组，然后在新数组的最后⼀个位置，添加新数据。然后将该新数组的引⽤赋予当前数组，最后解锁
  
• CopyOnWriteArrayList的remove函数remove函数跟add函数过程相似：先创建⼀个新的数组（⻓度为 原来⻓度-1），然后复制元素两边的数据元素, 然后将该新数组的引⽤赋予当前数组，整个过程也是有锁的
  

2.4 ArrayList和CopyOnWriteArrayList的比较

• 单线程：在元素较少的情况下，两个类的性能接近，当元素很多时，CopyOnWriteArrayList增长元素的操作会差一点
• 多线程：跟着元素数量和线程数量增长，CopyOnWriteArrayList在添加和删除元素的机能就会降落，并且比ArrayList机能低。但在查找元素时在元素数量和线程数量的增长情况下性能比ArrayList好。
• 在读多写少的并发场景中，CopyOnWriteArrayList比ArrayList是更好的选择