tair & redis 的选择

tair & redis 的选择#

  1. 延迟敏感程度, 延迟敏感,说什么也得redis
  2. 数据量大的话,数据量超过100GB全内存太浪费资源,延迟没有那么敏感,使用tair
  3. 使用复杂数据结构 redis
  4. 容忍数据丢失

innodb事务隔离级别、MVCC

隔离级别#

未提交读(Read Uncommitted):允许脏读,也就是可能读取到其他会话中未提交事务修改的数据

提交读(Read Committed):只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)

可重复读(Repeated Read):可重复读。在同一个事务内的查询都是事务开始时刻一致的,InnoDB默认级别。在SQL标准中,该隔离级别消除了不可重复读,但是还存在幻象读

串行读(Serializable):完全串行化的读,每次读都需要获得表级共享锁,读写相互都会阻塞

MVCC#

InnoDB是一个多版本的存储引擎:为了支持事务的一些特性诸如并发和回滚,它保持着被修改行的旧版本信息。这些信息被存储在一个被叫做回滚段(rollback segment)的表空间中。InnoDB在回滚段中用这些信息来执行undo操作,以此支持事务回滚。它也用这些信息来构造行的更早的版本,以此支持一致性读(快照读)。

在内部,InnoDB为数据库中存储的每一行添加三个隐藏字段。

DB_TRX_ID:表明插入或者修改这一行的最后一个事务的事务标识符。如何查看行事务ID

DB_ROLL_PTR:指向回滚段中的一个undo log记录,如果行被修改了,那么这个undo log记录包含的信息必须先于行修改被重新修改。

DB_ROW_ID:单调递增的行ID。如果InnoDB自动生成了一个聚集索引,那么这个索引包含行ID值,否则DB_ROW_ID列不会出现在任何索引中。

锁类型#

共享锁(读锁,S锁):若事务T对数据对象A加上S锁,则事务T可以读A但不能修改A,其他事务只能再对A加S锁,而不能加X锁,直到T释放S锁。

排他锁(写锁,X锁):若事务T对数据对象A加上X锁,则只允许T读取和修改A,其他事务不能再对A加作何类型的锁,直到T释放A上的X锁。

意向共享锁(IS锁):事务T在对表中数据对象加S锁前,首先需要对该表加IS(或更强的IX)锁。

意向排他锁(IX锁):事务T在对表中的数据对象加X锁前,首先需要对该表加IX锁。

意向锁补充#
  • InnoDB 支持多粒度锁,特定场景下,行级锁可以与表级锁共存。
  • 意向锁之间互不排斥,但除了 IS 与 S 兼容外,意向锁会与 共享锁 / 排他锁 互斥。
  • IX,IS是表级锁,不会和行级的X,S锁发生冲突。只会和表级的X,S发生冲突。
  • 意向锁在保证并发性的前提下,实现了行锁和表锁共存且满足事务隔离性的要求。

2pl 两阶段锁#

两段锁协议,先随便加,最后commit才能一起释放.

GAP锁有何用#

其实这个多出来的GAP锁,就是RR隔离级别,相对于RC隔离级别,不会出现幻读的关键。

确实,GAP锁锁住的位置,也不是记录本身,而是两条记录之间的GAP。

所谓幻读,就是同一个事务,连续做两次当前读 (例如:select * from t1 where id = 10 for update;),那么这两次当前读返回的是完全相同的记录 (记录数量一致,记录本身也一致),第二次的当前读,不会比第一次返回更多的记录 (幻象)。

如何保证两次当前读返回一致的记录,那就需要在第一次当前读与第二次当前读之间,其他的事务不会插入新的满足条件的记录并提交。为了实现这个功能,GAP锁应运而生

快照读 & 当前读#

快照读:就是select

1
select * from table ….;

当前读:特殊的读操作,插入/更新/删除操作,属于当前读,处理的都是当前的数据,需要加锁。

1
2
3
4
5
select * from table where ? lock in share mode;
select * from table where ? for update;
insert;
update ;
delete;

聊天讨论#

全快照、全当前,不幻读, 先快照,再当前,幻读

「 球球: 其实产生幻读的原因,就是以为读走了mvcc的副本, 」


读如果也加gap锁,就真的不会幻读了,但代价太大

「 宏伟: 张三账户余额有10000元;要转账给李四9000元,转给王五5000元;这两次转账肯定有一次因余额不足转账失败;如果在 rr 下,可重复读, 两次update 张三都会成功? 」


这个如果两个事务并发,都先读的1w元快照读,然后第1个事务直接update张三减钱, commit, 第2个事务 接着update张三减钱,都会成功,除非
1 用数据库乐观锁
2 自己搞个分布式锁,将读写操作原子化
3 用kafka让同一用户操作串行化

敏: 交易相关的就不要快照读了, 交易要算钱,select的时候就要锁,不然这条数据之后未必可用

总结#

RR级别下,通过MVCC, 解决了两个快照读的幻读问题,
通过next-key锁,解决了两个当前读的幻读问题,但是快照读后的当前读是会幻读的.

netty模型

定义#

netty是一个高性能、异步事情驱动的网络通信框架
NIO IO多路复用 、事情驱动模型

1.设置主从reactor模式
2.指定IO类型
3.指定handler
4.绑定端口

netty优点#

  1. API使用简单,开发门槛低;

  2. 功能强大,预置了多种编解码功能,支持多种主流协议;

  3. 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展;

  4. 性能高,通过与其他业界主流的NIO框架对比,Netty的综合性能最优;

  5. 成熟、稳定,Netty修复了已经发现的所有JDK NIO BUG,业务开发人员不需要再为NIO的BUG而烦恼;

  6. 社区活跃,版本迭代周期短,发现的BUG可以被及时修复,同时,更多的新功能会加入;

  7. 经历了大规模的商业应用考验,质量得到验证。在互联网、大数据、网络游戏、企业应用、电信软件等众多行业得到成功商用,证明了它已经完全能够满足不同行业的商业应用了。

高性能三要素#

  1. reactor模型
  2. IO多路复用
  3. 协议

reactor模型#

单线程模型#

多线程模型#

主从线程模型#

组件#

Bootstrap/ServerBootstrap#

顾名思义就是启动类,分别负责启动客户端和服务器端。这个类用来配置相关参数,比如设置EventLoopGroup,IO类型,handler等等,Netty的一切都从这里开始

EventLoopGroup#

主从多线程Reactor模型,分别有两个线程池: EventLoopGroupA和EventLoopGroupB。一个用于接收请求,另一个用于处理IO操作。

一个EventLoopGroup就相当于一个线程池,而每一个EventLoop就是一个线程,当新的Channel被创建时(有新的请求进来),就会在EventLoopGroup里注册一下,同时会分配一个EventLoop给这个Channel,

从此开始直到这个Channel被销毁,这个Channel只能被它绑定的这个EventLoop执行,这也就是为什么Netty可以不用考虑并发的原因。

EventLoop是处理各个event的具体线程。除了处理IO读写等event外,EventLoop还需要进行系统任务和定时任务进行执行

Channel#

Netty的Channel接口所提供的的API,大大降低了直接使用Socket类的复杂性

ChannelPipeline & ChannelHander#

Netty采用了一种叫做数据流(data flow)的处理机制,类似于Unix中的管道。即每一个Channel都有一个自己的ChannelPipeline,每一个pipeline里会有多个ChannelHandler。数据会像水流一样依次通过每一个handler被逐一处理。
流处理是双向混合的,分为Inbound和Outbound, 分别对应request和response。

这个handler被分成两类:ChannelOutboundHandler和ChannelInboundHandler。当服务器处理进来的请求时,则只会调用实现了ChannelInboundHandler的handler;当服务器返回信息给客户端时,则只会调用实现了ChannelOutboundHandler的handler

Encoders & Decoders#

我们在解析处理请求时通常需要对数据格式进行转换,比如把字节变成对象,或者把对象转换为字节。针对这种常见的场景,Netty提供了编码和解码的接口:MessageToByteEncoder和ByteToMessageEncoder。

其实两个抽象类分别继承了ChannelInboundHandlerAdapter和ChannelOutboundHandlerAdapter,说白了,使用起来和普通的handler没什么区别。自己写的类只要重写decode()或者encode()方法对数据进行处理即可

BIO NIO AIO 阻塞 非阻塞

BIO:同步阻塞IO(面向流的)#

特点:一个连接建立一个线程,连接如果没有IO请求时,则会浪费线程资源开销,可以通过线程池技术来改善

适用场景:连接数小,并发数小,架构固定(java1.4之前唯一的IO)

NIO:同步非阻塞(面向Buffer的)#

特点:客户的发送的连接请求会注册到多路复用器上,多路复用器轮询到连接存在有效请求时才会启动一个线程来进行处理
适用场景:连接数目多,且连接比较短的架构,比如聊天服务器(java1.4开始支持)

AIO:异步非阻塞#

特点:针对客户端连接发出的IO请求,会由OS先完成IO操作后,在通知服务器启动线程进行处理
适用场景:连接数目多,连接比较长,比如相册服务器,充分调用OS参与并发操作(java1.7开始支持)

同步、异步(关注点:消息通信机制、IO请求发送)#

同步:发送一个请求后,会不断的去轮询、等待请求结果返回后再发送下一个请求,可以避免死锁,脏读的发生

异步:发送一个请求后,不需要等待结果返回也可以发送下一个请求,可以提高效率,保证并发,OS执行完成后会通过回调函数通知应用程序获取结果

阻塞、非阻塞(关注点:程序在等待调用结果时的状态、IO操作结果获取)#

阻塞:程序在等待请求结果的时候,线程会被挂起,调用线程只有在得到结果之后才会返回

非阻塞:虽然不能立马得到结果,但是该调用不会阻塞当前线程,此线程还可以干其他事

NIO IO多路复用#

NIO是概念,IO多路复用是一套方案

当某个连接发送请求到服务器,服务器把这个连接请求当作一个请求“事件”,并把这个“事件”分配给相应的函数处理。我们可以把这个处理函数放到线程中去执行,执行完就把线程归还,这样一个线程就可以异步的处理多个线程

而阻塞式 I/O 的线程的大部分时间都被浪费在等待请求上了

对于同步非阻塞,一个线程可以执行多个连接中的请求,而同步阻塞则时一个线程对应一个连接,所以阻塞会很严重, 线程浪费严重

红黑树、AVL树、B树代价分析与比较

一、各种树简介#

红黑树#

它可以在 O(logn) 时间内完成查找,插入和删除,这里的n是树中元素的数目.

常考五个性质

自编顺口溜:有红有黑,头黑尾黑,红后黑,任尾同黑

  1. 结点是红色或黑色
  2. 根结点始终是黑色
  3. 叶子结点(NIL 结点)都是黑色
  4. 红色结点的两个直接孩子结点都是黑色(即从叶子到根的所有路径上不存在两个连续的红色结点)
  5. 从任一结点到每个叶子的所有简单路径都包含相同数目的黑色结点

保证了红黑树在满足平衡二叉树特征的前提下,还可以做到 从根到叶子的最长路径最多不会超过最短路径的两倍。

AVL树#

AVL树定义:
二叉排序树,其中每一个结点的左子树和右子树的高度差不超过1(小于等于1)。

二叉树的平衡因子 (Balance Factor) 等于该结点的左子树深度减去右子树深度的值称为平衡因子。平衡因子只可能是-1,0,1。

红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。

红黑树和AVL树都是从树的平衡性出发,找到合适的平衡方式,一个通过颜色标识限定,一个通过树高差限定,使树都处于平衡状态。

AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树。

B树#

B树相对于红黑树的区别

在大规模数据存储的时候,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。为什么会出现这样的情况,我们知道要获取磁盘上数据,必须先通过磁盘移动臂移动到数据所在的柱面,然后找到指定盘面,接着旋转盘面找到数据所在的磁道,最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上,树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,B树可以有多个子女,从几十到上千,可以降低树的高度。

B树的数据结构就是为内外存的数据交互准备的。
外存(如硬盘)是将 所有的信息分割成相等大小的页面,每次硬盘读写的都是一个或多个完整的页面 。如果要处理的硬盘数据量很大,无法一次全部装入内存中,就要对B树进行调整,是的B树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。比如一棵B树的阶为1001(1个结点可以包含1000个元素),高度为2,它可以存储超过10亿(1000X1000X1000)个关键字,我们只要让根结点持久的保留在内存中,那么在这棵树上,寻找某一个关键字至多需要两次硬盘的读取。通过这种方式,在有限内存的情况下,每一次磁盘的访问都可以获得最大数量的数据。

二、各树操作代价#

整个红黑树的查找,插入和删除都是O(logN)的,原因就是整个红黑树的高度是logN,查找从根到叶,走过的路径是树的高度,删除和插入操作是从叶到根的,所以经过的路径都是logN。

RBT 的操作代价分析#

(1) 查找代价:由于红黑树的性质(最长路径长度不超过最短路径长度的2倍),可以说明红黑树虽然不像AVL一样是严格平衡的,但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比AVL要略逊色一点。

(2) 插入代价:RBT插入结点时,需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转,这一点和AVL的插入操作一样。虽然变色操作需要O(logN),但是变色操作十分简单,代价很小。

(3) 删除代价:RBT的删除操作代价要比AVL要好的多,删除一个结点最多只需要3次旋转操作。

RBT 效率总结 :

查找 效率最好情况下时间复杂度为O(logN),但在最坏情况下比AVL要差一些,但也远远好于BST。
插入和删除操作改变树的平衡性的概率要远远小于AVL(RBT不是高度平衡的)。因此需要的旋转操作的可能性要小,而且一旦需要旋转,插入一个结点最多只需要旋转2次,删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN),但是实际上,这种操作由于简单所需要的代价很小。

AVL 的操作代价分析#

(1) 查找代价: AVL是严格平衡的BST(平衡因子不超过1)。那么查找过程与BST一样,只是AVL不会出现最差情况的BST(单支树)。因此查找效率最好,最坏情况都是O(logN)数量级的。

(2) 插入代价: AVL必须要保证严格平衡(|bf|<=1),那么每一次插入数据使得AVL中某些结点的平衡因子超过1就必须进行旋转操作。事实上,AVL的每一次插入结点操作最多只需要旋转1次(单旋转或双旋转)。因此,总体上插入操作的代价仍然在O(logN)级别上(插入结点需要首先查找插入的位置)。

(3) 删除代价:AVL删除结点的算法可以参见BST的删除结点,但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要O(logN)次旋转。因此,删除操作的时间复杂度为O(logN)+O(logN)=O(2logN)

AVL 效率总结

查找的时间复杂度维持在O(logN),不会出现最差情况
AVL树在执行每个插入操作时最多需要1次旋转,其时间复杂度在O(logN)左右。

AVL树在执行删除时代价稍大,执行每个删除操作的时间复杂度需要O(2logN)。

B树的操作代价分析#

(1) 查找代价: B-Tree作为一个平衡多路查找树(m-叉)。B树的查找分成两种:一种是从一个结点查找另一结点的地址的时候,需要定位磁盘地址(查找地址),查找代价极高。另一种是将结点中的有序关键字序列放入内存,进行优化查找(可以用折半),相比查找代价极低。而B树的高度很小,因此在这一背景下,B树比任何二叉结构查找树的效率都要高很多。而且B+树作为B树的变种,其查找效率更高。

(2)插入代价: B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时,磁盘访问的次数为h(读取搜索路径上的节点)+2s(回写两个分裂出的新节点)+1(回写新的根节点或插入后没有导致分裂的节点)。因此,所需要的磁盘访问次数是h+2s+1,最多可达到3h+1。因此插入的代价是很大的。

(3)删除代价:B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h=(找到包含被删除元素需要h次读访问)+(获取第2至h层的最相邻兄弟需要h-1次读访问)+(在第3至h层的合并需要h-2次写访问)+(对修改过的根节点和第2层的两个节点进行3次写访问)

B-Tree效率总结: 由于考虑磁盘储存结构,B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。

三、AVL与红黑树的对比#

AVL 和RBT 都是二叉查找树的优化。其性能要远远好于二叉查找树。他们之间都有自己的优势,其应用上也有不同。

结构对比: AVL的结构高度平衡,RBT的结构基本平衡。平衡度AVL > RBT.

查找对比: AVL 查找时间复杂度最好,最坏情况都是O(logN)。

RBT 查找时间复杂度最好为O(logN),最坏情况下比AVL略差。

插入删除对比: 1. AVL的插入和删除结点很容易造成树结构的不平衡,而RBT的平衡度要求较低。因此在大量数据插入的情况下,RBT需要通过旋转变色操作来重新达到平衡的频度要小于AVL。

如果需要平衡处理时,RBT比AVL多一种变色操作,而且变色的时间复杂度在O(logN)数量级上。但是由于操作简单,所以在实践中这种变色仍然是非常快速的。

当插入一个结点都引起了树的不平衡,AVL和RBT都最多需要2次旋转操作。但删除一个结点引起不平衡后,AVL最多需要logN 次旋转操作,而RBT最多只需要3次。因此两者插入一个结点的代价差不多,但删除一个结点的代价RBT要低一些。

AVL和RBT的插入删除代价主要还是消耗在查找待操作的结点上。因此时间复杂度基本上都是与O(logN) 成正比的。

总体评价:大量数据实践证明,RBT的总体统计性能要好于平衡二叉树。

AQS原理解析

谈谈你对AQS的理解#

AQS是JUC(java.util.concurrent)中很多同步组件的构建基础,简单来讲,它内部实现主要是状态变量state和一个FIFO队列来完成,同步队列的头结点是当前获取到同步状态的结点,获取同步状态state失败的线程,会被构造成一个结点(或共享式或独占式)加入到同步队列尾部(采用自旋CAS来保证此操作的线程安全),随后线程会阻塞;释放时唤醒头结点的后继结点,使其加入对同步状态的争夺中。

AQS的内部实现#

  • state 资源状态
  • exclusiveOwnerThread 持有资源的线程
  • CLH 同步等待队列。

AQS维护一个共享资源state,内置的同步队列由一个一个的Node结点组成,每个Node结点维护一个prev引用和next引用,分别指向自己的前驱和后继结点。

AQS维护两个指针,分别指向队列头部head和尾部tail

继承自AQS的常见类#

CountDownLatch、ReentrantLock、Semaphore等

AQS的两种实现方式#

独占式&共享式, 这样方便使用者实现不同类型的同步组件,独占式如ReentrantLock,共享式如Semaphore,CountDownLatch,组合式的如ReentrantReadWriteLock。

AQS定义的以下可重写的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
独占式获取同步状态,试着获取,成功返回true,反之为false
protected boolean tryAcquire(int arg)

独占式释放同步状态,等待中的其他线程此时将有机会获取到同步状态
protected boolean tryRelease(int arg)

共享式获取同步状态,返回值大于等于0,代表获取成功;反之获取失败
protected int tryAcquireShared(int arg)

共享式释放同步状态,成功为true,失败为false
protected boolean tryReleaseShared(int arg)

是否在独占模式下被线程占用
protected boolean isHeldExclusively()

独占式

1.tryAcquire方法尝试获取锁,如果成功就返回,如果不成功,走到2.

2.把当前线程和等待状态信息构造成一个Node节点,并将结点放入同步队列的尾部

3.该Node结点在队列中尝试获取同步状态,若获取不到,则阻塞结点线程,直到被前驱结点唤醒或者被中断.

以ReentrantLock为例,state初始化为0,表示未锁定状态。A线程lock()时,会调用tryAcquire()独占该锁并将state+1。此后,其他线程再tryAcquire()时就会失败,直到A线程unlock()到state=0(即释放锁)为止,其它线程才有机会获取该锁。当然,释放锁之前,A线程自己是可以重复获取此锁的(state会累加),这就是可重入的概念。但要注意,获取多少次就要释放多么次,这样才能保证state是能回到零态的

自我实现独占锁示例,待重写方法提供更新state等操作.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.concurrent.locks.AbstractQueuedSynchronizer;

public class MyLock {


private final Sync sync = new Sync();

public void lock() {
sync.acquire(1);
}

public void unlock() {
sync.release(1);
}

public boolean isLocked() {
return sync.isHeldExclusively();
}


private static class Sync extends AbstractQueuedSynchronizer {
@Override
protected boolean tryAcquire(int arg) {

//首先判断状态是否等于=0,如果状态==0,就将status设置为1
if (compareAndSetState(0,1)) {
//将当前线程赋值给独占模式的onwer
setExclusiveOwnerThread(Thread.currentThread());
return true;
}

return false;

}

@Override
protected boolean tryRelease(int arg) {
if (getState() == 0) {
throw new IllegalMonitorStateException();
}
setExclusiveOwnerThread(null);
setState(0);
return true;
}

@Override
protected boolean isHeldExclusively() {
return getState() == 1;
}
}
}

共享式

CountDownLatch:
任务分为N个子线程去执行,state也初始化为N(注意N要与线程个数一致)。这N个子线程是并行执行的,每个子线程执行完后countDown()一次,state会CAS减1。等到所有子线程都执行完后(即state=0),会unpark()主调用线程,然后主调用线程就会从await()函数返回,继续后余动作。

Semaphore:
AQS通过state值来控制对共享资源访问的线程数,有线程请求同步状态成功state值减1,若超过共享资源数量获取同步状态失败,则将线程封装共享模式的Node结点加入到同步队列等待。有线程执行完任务释放同步状态后,state值会增加1,同步队列中的线程才有机会获得执行权。公平锁与非公平锁不同在于公平锁申请获取同步状态前都会先判断同步队列中释放存在Node,若有则将当前线程封装成Node结点入队,从而保证按FIFO的方式获取同步状态,而非公平锁则可以直接通过竞争获取线程执行权。

一般来说,自定义同步器要么是独占方法,要么是共享方式,他们也只需实现tryAcquire-tryRelease、tryAcquireShared-tryReleaseShared中的一种即可。但AQS也支持自定义同步器同时实现独占和共享两种方式,如ReentrantReadWriteLock。

volatile可见性、内存屏障

总结

volatile关键字具有许多特性,其中最重要的特性就是保证了用volatile修饰的变量对所有线程的可见性。利用内存屏障使得读写、读读、写写 都不能同时发生, 且不能指令重排。

可见性

当一个线程修改了变量的值,新的值会立刻同步到主内存当中。而其他线程读取这个变量的时候,也会从主内存中拉取最新的变量值。

得益于java语言的先行发生原则(happens-before)
对于一个volatile变量的写操作先行发生于后面对这个变量的读操作。

内存屏障

内存屏障(Memory Barrier)是一种CPU指令。禁止重排序,控制执行顺序,刷新缓存与获取最新主存数据。

hashtable and concurrenthashmap1.7、1.8

hashtable&concurrenthashmap1.7&1.8 总结

CAS原理、缺点、AtomicInteger使用解析

cas原理

CAS(Compare and Swap),即比较并替换, 是设计并发算法时用到的一种技术。简单来说,比较和替换是使用一个期望值和一个变量的当前值进行比较,如果当前变量的值与我们期望的值相等,就使用一个新值替换当前变量的值。

CAS有三个操作数:内存值V、旧的预期值A、要修改的值B,当且仅当预期值A和内存值V相同时,将内存值修改为B并返回true,否则什么都不做并返回false。

在CAS中,比较和替换是一组原子操作,不会被外部打断,且在性能上更占有优势。

Hashmap源码解析-总览&目录

HashMap:

它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。

HashMap最多只允许一条记录的键为null,允许多条记录的值为null。

HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

结构: 数组 + 链表, 链表长度达到8转化成红黑树

扩容: hashMap的容量达到threshold会触发扩容。扩容前后,哈希桶的长度一定会是2的次方, 这样在根据key的hash值寻找对应的哈希桶时,可以用位运算替代取余操作,更加高效。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×