「javacas算法」JAVA常用算法

今天给各位分享javacas算法的知识，其中也会对JAVA常用算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、jdk8中的ConcurrentHashMap究竟为什么高效？
• 2、Callable和Future
• 3、Java锁有哪些种类，以及区别
• 4、CAS原理以及CAS带来的三大问题

jdk8中的ConcurrentHashMap究竟为什么高效？

从源码来窥其一斑！

我们都知道hashMap不是线程安全的，因为在扩容方法中很容易出现死循环，hashTable使用锁的方式比较简单暴力，几乎在所有操作方法上都加了synchronized锁，导致总体性能很差，concurrentHashmap凭借线程安全且性能优异一直都是高并发中的首选key-value型数据结构；

concurrentHashmap的高性能有以下原因：

一，分段锁：jdk8中对concurrentHashmap进行了改进，抛弃了jdk7中新建segment作为分段锁的过程，jdk8中虽沿用了这种分段锁的思想，却直接使用数组中的数据作为 分段锁保证concurrentHashmap在上锁的时候只针对数组下标下的数据进行上锁 （比如如果数组长度为256，那么每次put平均只有1/256的数据被锁），而大多数其他的数据还是能进行正常的增删改操作，无需阻塞等待，这无疑极大的 降低了锁的粒度，提升了性能。

二，红黑树 ：jdk8中引入了红黑树结构，在单个数组下标内的数据达到8以后，会自动转换为红黑树进行存储， 使用大O表示法表示效率的话，红黑树的查找效率为O(log(n))，而链表的效率为O（n） ，当数据量越来越大的时候，红黑树的效率明显好于链表，所以concurrentHashmap性能得到很大提升；

现在我们主要从put方法中的主要方法来分析性能的提升：

spread(key.hashCode());//作用是再次哈希，减少冲突 ，源码如下

其中涉及到的位运算有

16：无符号右移16位，空位以0补齐 。

^:异或运算符--相同为0，不同为1； ：与运算符--全1得1，否则0；

(h ^ (h 16)) HASH_BITS; 所以这句代码的意思就是不仅消除高16位的影响，同时获得正整数的hash值

再来看后面的方法， 如上图：

1，就是判断当这个hash表还是空的时候，调用initTable进行初始化； 2，使用(n - 1) hash)计算数组下标，如果数据指定下标处为null，则直接插入，注： cas是java8中的concurrentHashmap引入的线程安全判断，CAS算法做为乐观锁 ；

3，(fh = f.hash) == MOVED，走到此处说明下标内有node，且该node的值为-1（MODED=-1),搜索全类发现MODED是在调用有参构造器ForwardingNode中默认写入的，而这个调用处刚好在transfer方法中，所以我们推断，扩容的时候先将数组下标内的node.hash置为-1！ 同时在3这一步中调用helpTransfer(tab, f)参与扩容，并把数据写入；

4，走到这说明node不是空的，也没在扩容，那么锁住该下标下的node，并把新value插入链表中； 5，如果锁住的这个node能实例化为TreeBin，则代表已经转化为红黑树进行存储，将数据插入红黑树中； 6，判断在4,5中计算得到的数组下标内所有节点总数， 如果满足转化为红黑树的条件（节点数大于8），则自动转化为红黑树进行存储！

总的来说，concurrentHashmap之所以性能高就是因为使用了分段锁和红黑树！

至于conrrentHashmap其他的方法的源码分析，后期会补上的，更多的技术分享，敬请关注！

Callable和Future

可以看到，这是一个泛型接口，call()函数返回的类型就是客户程序传递进来的V类型，且该接口往往与Future结合使用。

关于Future,源码中的注释如下：

尝试取消此任务的执行。 如果任务已完成、已被取消或由于某些其他原因无法取消，则此尝试将失败。 如果成功，并且在调用cancel时此任务尚未启动，则此任务不应该运行。 如果任务已经开始，则根据传入的参数确定是否应该中断执行该任务的线程以尝试停止该任务。

此方法返回后，对isDone的后续调用将始终返回true 。 如果此方法返回true ，则对isCancelled的后续调用将始终返回true 。

如果此任务完成，则返回true 。 完成可能是由于正常终止、异常或取消——在所有这些情况下，此方法都将返回true 。

等待计算完成，获取结果。

在给定时间范围内等待计算完成，获取结果。超过时间还未计算完成将抛出timeout异常。

下面我们来来看看Future一个常用的实现类FutureTask。

FutureTask类实现RunnableFuture接口,RunnableFuture接口继承Runnable和Future接口。到这里我们嗅到了一丝线程的味道，接着往下看。

FutureTask对于任务运行的状态使用volatile关键字去修饰保证了线程的安全性，至于volatile关键字为何能保证线程安全后续文章解答。

同时定义了0、1、2、3、4、5、6七个连续大小的整型变量来表示任务的状态变化，具体代码如下：

FutureTask成员变量

将要执行的任务

Object类型，表示通过get()方法获取到的结果数据或者异常信息。

运行Callable的线程，运行期间会使用CAS保证线程安全，这里大家只需要知道CAS是Java保证线程安全的一种方式， 后续文章中会深度分析CAS如何保证线程安全。

WaitNode是一个静态内部类，表示等待线程的堆栈中的链表节点，在FutureTask的实现中，会通过CAS结合此堆栈交换任务的运行状 态。

WaitNode的定义如下：

类中定义了一个Thread成员变量和指向下一个WaitNode节点的引用。其中 通过构造方法将thread变量设置为当前线程。

FutureTask构造方法

接收一个Callable变量，同时设置任务状态为NEW

接受一个Runnable线程变量以及返回结果类型，同时设置任务状态为NEW

如果任务状态state不等于NEW则直接return。如果state等于NEW，则调用UNSAFE.compareAndSwapObject方法执行CAS算法判断当前对象与当前线程是否一致，不一致则直接return。

如果当前任务不等于null且状态等于NEW，则执行call方法同时调用set方法设置返回结果。最后将当前运行线程runner设置为null,如果任务状态=INTERRUPTING会执行handlePossibleCancellationInterrupt方法将状态为INTERRUPTING的任务线程设置为就绪状态，但该任务线程不会被CPU再次执行调度。因为state没有被重置。

handlePossibleCancellationInterrupt方法

CAS算法计算NEW偏移一个变量是否等于COMPLETING(2)，是则将返回结果复制给outcome成员变量，同时设置stateOffset=NORMAL(2)为正常状态。

最后调用finishCompletion()方法。

在finishCompletion()方法中，首先定义一个for循环，循环终止因子为waiters为null，在循环中，判断CAS操作是否成功，如果成功 进行if条件中的逻辑。首先，定义一个for自旋循环，在自旋循环体中，唤醒WaitNode堆栈中的线程，使其运行完成。当WaitNode 堆栈中的线程运行完成后，通过break退出外层for循环。接下来调用done()方法。

默认实现什么也不做，子类可以覆盖此方法以调用完成回调。

判断任务状态是否运行中，如果是调用awaitDone()方法等待任务完成。否则调用report方法返回结果。

如果任务状态等于NORMAL(3)则返回正常计算结果。如果任务状态大于等于CANCELLED(4)则返回异常结果。

看到这里我们大致对Callable和Future的源码有了大致的了解。但是对于它们二者是怎么与多线程关联的，我们在下一个章节讲解

Java锁有哪些种类，以及区别

一、公平锁/非公平锁

公平锁是指多个线程按照申请锁的顺序来获取锁。

非公平锁是指多个线程获取锁的顺序并不是按照申请锁的顺序，有可能后申请的线程比先申请的线程优先获取锁。有可能，会造成优先级反转或者饥饿现象。

对于Java ReentrantLock而言，通过构造函数指定该锁是否是公平锁，默认是非公平锁。非公平锁的优点在于吞吐量比公平锁大。

对于Synchronized而言，也是一种非公平锁。由于其并不像ReentrantLock是通过AQS的来实现线程调度，所以并没有任何办法使其变成公平锁。

二、可重入锁

可重入锁又名递归锁，是指在同一个线程在外层方法获取锁的时候，在进入内层方法会自动获取锁。说的有点抽象，下面会有一个代码的示例。

对于Java ReentrantLock而言, 他的名字就可以看出是一个可重入锁，其名字是Re entrant Lock重新进入锁。

对于Synchronized而言,也是一个可重入锁。可重入锁的一个好处是可一定程度避免死锁。

synchronized void setA() throws Exception{

Thread.sleep(1000);

setB();

}

synchronized void setB() throws Exception{

Thread.sleep(1000);

}

上面的代码就是一个可重入锁的一个特点，如果不是可重入锁的话，setB可能不会被当前线程执行，可能造成死锁。

三、独享锁/共享锁

独享锁是指该锁一次只能被一个线程所持有。

共享锁是指该锁可被多个线程所持有。

对于Java

ReentrantLock而言，其是独享锁。但是对于Lock的另一个实现类ReadWriteLock，其读锁是共享锁，其写锁是独享锁。

读锁的共享锁可保证并发读是非常高效的，读写，写读 ，写写的过程是互斥的。

独享锁与共享锁也是通过AQS来实现的，通过实现不同的方法，来实现独享或者共享。

对于Synchronized而言，当然是独享锁。

四、互斥锁/读写锁

上面讲的独享锁/共享锁就是一种广义的说法，互斥锁/读写锁就是具体的实现。

互斥锁在Java中的具体实现就是ReentrantLock

读写锁在Java中的具体实现就是ReadWriteLock

五、乐观锁/悲观锁

乐观锁与悲观锁不是指具体的什么类型的锁，而是指看待并发同步的角度。

悲观锁认为对于同一个数据的并发操作，一定是会发生修改的，哪怕没有修改，也会认为修改。因此对于同一个数据的并发操作，悲观锁采取加锁的形式。悲观的认为，不加锁的并发操作一定会出问题。

乐观锁则认为对于同一个数据的并发操作，是不会发生修改的。在更新数据的时候，会采用尝试更新，不断重新的方式更新数据。乐观的认为，不加锁的并发操作是没有事情的。

从上面的描述我们可以看出，悲观锁适合写操作非常多的场景，乐观锁适合读操作非常多的场景，不加锁会带来大量的性能提升。

悲观锁在Java中的使用，就是利用各种锁。

乐观锁在Java中的使用，是无锁编程，常常采用的是CAS算法，典型的例子就是原子类，通过CAS自旋实现原子操作的更新。

六、分段锁

分段锁其实是一种锁的设计，并不是具体的一种锁，对于ConcurrentHashMap而言，其并发的实现就是通过分段锁的形式来实现高效的并发操作。

我们以ConcurrentHashMap来说一下分段锁的含义以及设计思想，ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap(JDK7与JDK8中HashMap的实现)的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表;同时又是一个ReentrantLock(Segment继承了ReentrantLock)。

当需要put元素的时候，并不是对整个hashmap进行加锁，而是先通过hashcode来知道他要放在那一个分段中，然后对这个分段进行加锁，所以当多线程put的时候，只要不是放在一个分段中，就实现了真正的并行的插入。

但是，在统计size的时候，可就是获取hashmap全局信息的时候，就需要获取所有的分段锁才能统计。

分段锁的设计目的是细化锁的粒度，当操作不需要更新整个数组的时候，就仅仅针对数组中的一项进行加锁操作。

七、偏向锁/轻量级锁/重量级锁

这三种锁是指锁的状态，并且是针对Synchronized。在Java

5通过引入锁升级的机制来实现高效Synchronized。这三种锁的状态是通过对象监视器在对象头中的字段来表明的。

偏向锁是指一段同步代码一直被一个线程所访问，那么该线程会自动获取锁。降低获取锁的代价。

轻量级锁是指当锁是偏向锁的时候，被另一个线程所访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，不会阻塞，提高性能。

重量级锁是指当锁为轻量级锁的时候，另一个线程虽然是自旋，但自旋不会一直持续下去，当自旋一定次数的时候，还没有获取到锁，就会进入阻塞，该锁膨胀为重量级锁。重量级锁会让其他申请的线程进入阻塞，性能降低。

八、自旋锁

在Java中，自旋锁是指尝试获取锁的线程不会立即阻塞，而是采用循环的方式去尝试获取锁，这样的好处是减少线程上下文切换的消耗，缺点是循环会消耗CPU。

典型的自旋锁实现的例子，可以参考自旋锁的实现

CAS原理以及CAS带来的三大问题

参考：

CAS ：Compare and Swap，即比较再交换。

CAS算法理解 ：CAS是一种无锁算法，CAS有3个操作数，内存值E，旧的预期值V，要修改的新值N。当且仅当预期值V和内存值E相同时，将内存值E修改为N，否则什么都不做。

CAS算法图解 ：

上图描述了CAS的原理，以及带来的三大问题以及问题出现的位置。

1.ABA问题

因为CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么CAS进行检查的时候发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面加上版本号，每次变量更新的时候把版本号加1，那么A-B-A就会变成1A-2B-3A。从Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前的标志是否等于预期标志，如果全部相等，则以原子方式将该应用和该标志的值设置为给定的更新值。

2.循环时间长开销大

自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销，如果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用：第一，它可以延迟流水线执行指令（de-pipeline），使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零；第二，它可以避免在循环的时候因内存顺序冲突（Memory Order Violation）而引起CPU流水线被清空，从而提高CPU的实行效率。

3.只能保证一个共享变量的原子操作

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候可以用锁。还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i=2,j=a,合并一下ji=2a,然后用CAS来操作ij。从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之前的原子性，就可以把多个变量放在一个对象里来进行CAS操作。

javacas算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于JAVA常用算法、javacas算法的信息别忘了在本站进行查找喔。