Hashmap、currentHashMap、synchronized、CAS、AQS底层实现原理

写缓冲区

entry cache

Synchronized

保证有序性的办法：1、happens-before程序次序规则：一个线程内，按照代码顺序，书写在前面的操作先行发生于书写在后面的操作volatile变量规则：对一个volatile变量的写操作先行发生于后面对这个volatile变量的读操作，volatile变量写，再是读，必须保证是先写，再读传递规则:如果操作A先行发生于操作B，而操作B又先行发生于操作C，则可以得出操作A先行发生于操作C线程启动规则：Thread对象的start()方法先行发生于此线程的每个一个动作，thread.start()，thread.interrupt()2、内存屏障每个volatile写操作前面，加StoreStore屏障，禁止上面的普通写和他重排每个volatile写操作后面，加StoreLoad屏障，禁止和下面的volatile读、写重排每个volatile读操作前面，加LoadLoad屏障，禁止上面的普通读和volatile读重排每个volatile读操作后面，加LoadStore屏障，禁止下面的普通写和volatile读重排

线程2

read消息

线程3

flag

总线

tag

cache line

可见性的硬件级别保证volatile保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。

flag的几种状态：1、share(共享)2、invalid(失效)3、exclusive(独占)4、modified(已修改)

收到invalidate消息，放入无效队列直接返回ack

处理器

为何要保证有序性？

公平锁线程3在等待 队列列排队非公平锁：线程3和线程2不一定谁先执行

收到所有的ack后取出所有的数据

1、高速缓存硬件级别原理2、EMSI缓存一致性协议硬件级别实现

synchronized(加锁保证原子性)

notifyAll唤醒操作

entrylist

机器码

无效队列

嗅探到invalidate ack消息

ReenTrantLock

数据读取

拉链散列表

waitset

数据写入

处理器1

burket

wait操作

flag(S-I-E-M)

HashMap：数组、链表、红黑树jdk1.8后：    寻址算法优化：先计算出key的hash值，将hash值向右移16位进行异或运算，让该hash值同时包含高低16位的特点之后对n-1进行与运算    hash算法优化：先计算出来key的hash值，对数组长度（n-1）取模 优化成为了计算出来的hash值进行与运算 更快hash碰撞的解决：    在hash冲突的位置加一个链表，把冲突的值放进去，当链表(o(n))长度到8后会变为红黑树结构O（logN）hashmap的扩容;   当数组的值达到数组长度的0.75时，会对数组进行2倍扩容currentHashMap:jdk1.8之后对锁粒度进行细化，对于同一个位置的put操作，先执行CAS操作，同一时刻只有一个线程能加锁。hashtable:(线程安全，不需要线程安全的场景使用hashmap  需要线程安全的场景使用currenthashmap)TreeMap: 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。LinkedHashMap: 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。    

乱序执行保证效率猜测执行

竞争锁

指令

线程

monitorenterload屏障Acquire(获取)屏障

处理器0

尝试设置为1比较旧值与内存值一致则设为1

read返回数据

classmatedataAddress

对象头

数据传输

AQSabstract queued synchnizer抽象队列同步器

count=1

cpu

尝试设置为1比较旧值与内存值不一致再次进行CAS

嗅探到invalidate消息

count=0

发送invalidate消息

CAS

owner= 线程一

加锁成功

线程 2

写缓冲器

锁优化：1、锁消除：JIT动态编译器对synchronized做的优化，在加锁时判断是否有可能只被一个线程占用，是的话编译时就不加monitorenter和monitorexit指令。2、锁粗化：JIT动态编译器对连续加锁释放锁的代码会合并为一个锁3、偏向锁：monitorenter和monitorexit需要执行cas操作，开销较大，所以对于一个线程主要竞争一把锁，则会给该锁维持一个偏好，后面的加锁和释放锁不需要cas操作。4、轻量级锁：如果偏向锁没成功实现，就会尝试轻量级锁来加锁，Mark Word里面有个轻量级锁指针，指向持有锁的线程，判断是不是自己加的锁，如果是自己加的锁那么执行代码，不是则是升级为重量级锁。5、自适应锁。因为cpu的时间片算法，线程1切换为线程二执行的时候会执行上下文切换，如果频繁的上下文切换回导致性能较差，所以会让线程一保持自旋，

主内存

CAS加锁

hello.class

对数据加锁

释放锁Release（释放）屏障moniterexitstore屏障

有可能发生指令重排

state=0

线程1

javac静态编译器

线程一

JNI动态编译器

高速缓存

原子性：加锁可见性：加锁强制reflesh操作，在机器码指令moniterenter之后加入load屏障，释放锁时强制flush操作，在monitorexit后加入store屏障有序性：Acquired（获取）屏障和Release（释放）屏障可以保证在synchronized代码块之间的代码和之前和之后的代码不进行指令重排，但是代码块之间的代码是有可能进行指令重排的

乐观锁：认为读多写少 遇到并发的可能性低，在写的时候会先判断有没有更新过着个数据，采取的是先取出这个数据的版本号然后比较和上次的版本号进行比较，一样则执行操作 反之 重复此操作（CAS操作）悲观锁：认为写多，每次操作数据时候都会加锁，别人要读写就需要先获取锁。（synchronized）

i=0i=1

对象minitor 

hello.java

AtomicInteger

read返回值

线程二

获取旧值0

加锁线程线程1

高速缓存写缓存区无效队列

发送invalidate ack消息

可能

minitor计数器        加一

LinkedeList和ArrayList的区别ArrayList是Array(动态数组)的数据结构，LinkedList是Link(链表)的数据结构。当随机访问List（get和set操作）时，ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。当对数据进行增加和删除的操作(add和remove操作)时，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。

java对象

对象类信息

Mark Word(minitor指针)

实例变量

线程三