如何实现一个线程安全的数据结构

一. 如何实现一个线程安全的数据结构

1.饿汉模式

public class Singletan {
    private static Singletan instance = new Singletan();    
    public Singletan(){}    
    public static Singletan getInstance() {
        return instance;
    }
}

2.静态内部类

//加载内部类SingletanHolder,从而实例化instance
public class Singletan {
    private static class SingletanHolder {
        private static final Singletan INSTANCE = new Singletan();
    }
    public Singletan(){}
    public static final Singletan getInstance() {
        return SingletanHolder.INSTANCE;
    }
}

3.CAS:Compare and Swap(比较和交换)

  • 乐观锁,无锁算法。CAS有3个参数:内存值V、旧值A、要修改的新值B,当且仅当旧值 A 和内存值 V 相同时,才将内存值 V 修改为 B,否则会尝试重新获取 V 的当前值,重新比较。
  • 优点:没有线程切换和阻塞的额外开销,支持较大并行度。
  • 缺点:①在并发量较高时,如果许多线程反复尝试去更新一个变量,却又一直更新失败,会消耗很多CPU资源。②银行取款 ABA 问题,所以不仅要比较旧值和内存值,还要比较变量的版本号是否一致,只有一致才进行操作。

银行取款ABA问题:假如账户开始有100元,在取款机上取走50,取款机出现问题一共提交了两次请求(线程1,线程2),第二次请求(线程2)在执行时因为某种原因被阻塞了,这时候有人往你的账户打了50元,线程2恢复了可执行状态,这个时候就会出现问题,原本线程2应该执行失败的,但是比较后仍然与旧值一致,这样就造成了账户实际上扣款了两次!

二.Java中满足线程安全的数据结构

所谓 线程安全 就是:一段操纵共享数据的代码能够保证在同一时间内被多个线程执行而仍然保持其正确性的,就被称为是线程安全的。

线程安全是保证执行业务逻辑正确的基本前提,为此在多线程开发中,我们尽量采用能保证线程安全的数据结构。

JDK已经为大家准备好了一批好用的线程安全容器类,可以大大减少开发工作量,例如HashTable,ConcurrentHashMap,CopyOnWriteArrayList,CopyOnWriteArraySet,ConcurrentLinkedQueue,Vector,StringBuffer等。本文主要对这些数据结构的功能及其常见使用场景进行说明与比较。

在这里插入图片描述

1、HashTable

HashTable实现了Map接口,为此其本身也是一个散列表,它存储的内容是基于key-value的键值对映射。

HashTable中的key、value都不可以为null;具有无序特性;由于其方法函数都是同步的(采用synchronized修饰),不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性。

HashTable使用synchronized来修饰方法函数来保证线程安全,但是在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时,其他线程也访问同步方法就会粗线阻塞状态。比如当一个线程在添加数据时候,另外一个线程即使执行获取其他数据的操作也必须被阻塞,大大降低了程序的运行效率。

2、ConcurrentHashMap

我们知道HashMap是线程不安全的,ConcurrentHashMap是HashMap的线程安全版。

但是与HashTable相比,ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升。

ConcurrentHashMap允许多个修改操作并发运行,其原因在于使用了锁分段技术:首先讲Map存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。这样就保证了每一把锁只是用于锁住一部分数据,那么当多线程访问Map里的不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效提高并发访问效率。

上述的处理机制明显区别于HashTable是给整体数据分配了一把锁的处理方法。为此,在多线程环境下,常用ConcurrentHashMap在需要保证数据安全的场景中去替换HashMap,而不会去使用HashTable,同时在最新版的JDK中已经推荐废弃使用HashTable。

3、CopyOnWriteArrayList

CopyOnWriteArrayList实现了List接口,提供的数据更新操作都使用了ReentrantLock的lock()方法来加锁,unlock()方法来解锁。

当增加元素的时候,首先使用Arrays.copyOf()来拷贝形成新的副本,在副本上增加元素,然后改变原引用指向副本。读操作不需要加锁,而写操作类实现中对其进行了加锁。因此,CopyOnWriteArrayList类是一个线程安全的List接口的实现,在高并发的情况下,可以提供高性能的并发读取,并且保证读取的内容一定是正确的,这对于读操作远远多于写操作的应用非常适合(注意: 如上述更新操作会带来较大的空间与性能开销,如果更新操太过频繁,反而不太合适使用)。

4、CopyOnWriteArraySet

CopyOnWriteArraySet是对CopyOnWriteArrayList使用了装饰模式后的具体实现。所以CopyOnWriteArrayList的实现机理适用于CopyOnWriteArraySet,此处不再赘述。

Java里的List和Set的之间的特性比较结论同样适用于CopyOnWriteArrayList与CopyOnWriteArraySet之间的比较;此外,CopyOnWriteArrayList与CopyOnWriteArraySet都是线程安全的。

5、ConcurrentLinkedQueue

ConcurrentLinkedQueue可以被看作是一个线程安全的LinkedList,使用了非阻塞算法实现的一个高效、线程安全的并发队列;其本质是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当添加一个元素时会添加到队列的尾部;当获取一个元素时,会返回队列头部的元素。

ConcurrentLinkedQueue应该算是在高并发环境中性能最好的队列,没有之一。

6、Vector

Vector通过数组保存数据,继承了Abstract,实现了List;所以,其本质上是一个队列。

但是和ArrayList不同,Vector中的操作是线程安全的,它是利用synchronized同步锁机制进行实现,其实现方式与HashTable类似。

7、StringBuffer与StringBuilder

在Java里面,字符串操作应该是最频繁的操作了,为此有必要把StringBuffer与StringBuilder两个方法类比较一下。

首先,对于频繁的字符串拼接操作,是不推荐采用效率低下的“+”操作的。一般是采用StringBuffer与StringBuilder来实现上述功能。但是,这两者也是有区别的:前者线程安全,后者不是线程安全的。

StringBuffer是通过对方法函数进行synchronized修饰实现其线程安全特性,实现方式与HashTable、Vector类似。

总结:

  1. HashTable是线程安全类;通过对其方法函数进行synchronized修饰实现其特性,效率低下,目前已被jdk废弃,不再推荐使用。
  2. 在多线程环境下,我们常用ConcurrentHashMap在需要保证数据安全的场景中去替换HashMap;此外ConcurrentHashMap也有不错的性能表现
  3. CopyOnWriteArrayList类是一个线程安全的List接口的实现,在高并发的情况下,可以提供高性能的并发读取,并且保证读取的内容一定是正确的,这对于读操作远远多于写操作的应用非常适合。
  4. CopyOnWriteArraySet是对CopyOnWriteArrayList使用了装饰模式后的具体实现,可理解为线程安全的Set。
  5. ConcurrentLinkedQueue应该算是在高并发环境中性能最好的队列;在多线程的队列应用场景中,强烈推荐使用。
  6. Vector中的操作是线程安全的,它是利用synchronized同步锁机制进行实现,其实现方式与HashTable类似。
  7. StringBuffer与StringBuilder常用于字符串拼接;前者线程安全,后者不是线程安全的;在多线程环境中下,考虑数据安全使用前者,否则使用后者。
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容