您的位置 首页 golang

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

在并发编程中,我们经常会用到 Map 容器。Map容器比较多,那么在不同场景下我们该如何选择最优的Map容器。

并发场景下的 Map 容器

一个电商系统设计一个统计商品销量 TOP 10 的功能。一般情况下,我们是用一个 哈希表 来存储商品和销量键值对,然后使用排序获得销量前十的商品。在这里,哈希表是实现该功能的关键。那么请思考一下,如果要你设计这个功能,你会使用哪个容器呢?

HashMap 的性能优越,经常被用来存储键值对。那么这里我们可以使用 HashMap 吗?答案是不可以的,在并发场景下使用 HashMap。但在高并发场景下,会有数据丢失以及不准确的情况出现,这个就是容器的线程不安全表现。

为了保证容器的 线程安全 ,Java 实现了 Hashtable 、ConcurrentHashMap 以及 ConcurrentSkipListMap 等 Map 容器。

Hashtable、ConcurrentHashMap 是基于 HashMap 实现的,对于小数据量的存取比较有优势。

如果这个电商系统的商品总量不是特别大的话,我们可以用 Hashtable 或 ConcurrentHashMap 来实现哈希表的功能。

Hashtable与ConcurrentHashMap

在数据不断地写入和删除,且不存在数据量累积以及数据排序的场景下,我们可以选用 Hashtable 或 ConcurrentHashMap。

Hashtable 使用 Synchronized 同步锁修饰了 put、get、remove 等方法,因此在高并发场景下,读写操作都会存在大量锁竞争,给系统带来性能开销。

相比 Hashtable,ConcurrentHashMap 在保证线程安全的基础上兼具了更好的并发性能。在JDK1.8中,ConcurrentHashMap 在添加元素时,在没有哈希冲突的情况下,会使用 CAS 进行添加元素操作;如果有冲突,则通过 Synchronized 将链表锁定,再执行接下来的操作。

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

所以我们在设计销量 TOP10 功能时,应该首选 ConcurrentHashMap

但要注意一点,虽然 ConcurrentHashMap 的整体性能要优于 Hashtable,但在某些场景中,ConcurrentHashMap 依然不能代替 Hashtable。如果是在强一致的场景中 ConcurrentHashMap 就不适用,原因是 ConcurrentHashMap 中的 get、size 等方法没有用到锁,ConcurrentHashMap 是弱一致性的,因此有可能会导致某次读无法马上获取到写入的数据。

ConcurrentHashMap与ConcurrentSkipListMap

同样还有一个场景,电信公司经常要提醒用户手机实时流量不足。主要的流程是服务端计算出用户实时流量,再通过手机端定时触发查询功能,如果流量不足,就弹出系统通知。

该业务的特点是用户量大,并发量高,写入多于查询操作。这时我们就需要设计一个 缓存 ,用来存放这些用户以及对应的流量键的信息。那么假设让你来实现一个简单的缓存,你会怎么设计呢?

你可能会考虑使用 ConcurrentHashMap 容器,但是该容器在数据量比较大的时候,链表会转换为 红黑树 。红黑树在并发情况下,删除和插入过程中会牵涉到大量节点的移动,因此竞争锁资源的代价相对比较高。

而跳跃表的操作针对局部,需要锁住的节点少,因此在并发场景下的性能会更好一些。但是在非线程安全的 Map 容器中,我并没有看到基于跳跃表实现的 SkipListMap ?这是因为在非线程安全的 Map 容器中,基于红黑树实现的 TreeMap 在单线程中的性能表现比跳跃表要好。

因此在非线程安全的 Map 容器中,用 TreeMap 容器来存取大数据;在线程安全的 Map 容器中,用 SkipListMap 容器来存取大数据。

那么 ConcurrentSkipListMap 是如何使用跳跃表来提升存取大数据的性能呢?我们先来了解下跳跃表的实现原理。

什么是跳跃表

跳跃表是基于链表扩展实现的一种特殊链表,类似于树的实现,跳跃表不仅实现了横向链表,还实现了垂直方向的分层 索引

一个跳跃表由若干层链表组成,每一层都实现了一个有序链表索引,只有最底层包含了所有数据,每一层由下往上依次通过一个指针指向上层相同值的元素,每层数据依次减少,等到了最顶层就只会保留部分数据了。

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

跳跃表的这种结构,是利用了空间换时间的方法来提高了查询效率。程序总是从最顶层开始查询访问,通过判断元素值来缩小查询范围。我们通过以下图文信息来了解下跳跃表的具体实现原理。

首先是一个初始化的跳跃表:

数据插入键值对中的key分别是3,4,5,6,7,9;每个元素插入时随机生成它的level(这个算法很复杂,这里不详细说明),这个level相当于索引层,有几个level就有几级索引层。

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

当查询 key 值为 9 的节点时,此时查询路径为:

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

当新增一个 key 值为 8 的节点时,首先新增一个节点到最底层的链表中,根据概率算出 level 值,再根据 level 值新建索引层,最后链接索引层的新节点。新增节点和链接索引都是基于 CAS 操作实现。

从图中我们可以看出,查找效率又有提升。当有大量的数据时,我们可以增加多级索引,其查找效率可以得到明显提升。

如果对数据有强一致要求,则需使用 Hashtable;在大部分场景通常都是弱一致性的情况下,使用 ConcurrentHashMap 即可;如果数据量在千万级别,且存在大量增删改操作,则可以考虑使用 ConcurrentSkipListMap。

Redis 使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的 元素数量比较多 ,又或者有序集合中元素的 成员是比较长的字符串 时, Redis就会使用跳跃表来作为有序集合健的底层实现。

总结

阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

文章来源:智云一二三科技

文章标题:阿里三面,讲讲不同场景下并发Map容器最优使用。凉凉送给自己

文章地址:https://www.zhihuclub.com/87185.shtml

关于作者: 智云科技

热门文章

评论已关闭

37条评论

  1. This can be a result of medical conditions such as high blood pressure, diabetes, prostate problems, or heart disease, or a side effect of the medications often taken for these conditions

  2. According to a study conducted by the Centers for Disease Control Prevention, medical marijuana is the best treatment option when it comes to pain and anxiety

  3. The development of improved mathematical methods for predicting the outcome for cancer patients

  4. Having low SHBG levels is a significant risk factor several fold increased likelihood for developing metabolic syndrome based on a study on almost 2,500 people 99, 100, 101. Flavonoids have the potential to improve cognitive disorders and cholinergic dysfunction related to oxidative stress.

  5. It was, like all snails, of two-for-one gender. How to Fade Out Content Using Gradients in iOS.

  6. Spontaneous perforation of the TM causes serosanguineous or purulent otorrhea Otorrhea Ear discharge otorrhea is drainage exiting the ear.

  7. Purkinje cells were identified by immunostaining with a mouse monoclonal antibody raised against calbindin D 28k Swant, Bellinzona, Switzerland, according to our previous method Sakamoto et al

  8. erythromycin base increases effects of bivalirudin by decreasing metabolism and never progress in the sport because it can take a year to regain the muscle loss that you can lose in 8 weeks of eating tissue on a diet 2

  9. Gracie, USA 2022 05 05 02 19 27 Nausea and vomiting occurring after day 5 of the chemotherapy cycle and before the subsequent cycle were not attributed to chemotherapy, and may have resulted in an underestimation of CINV events

  10. Hey there just wanted to give you a brief heads up and let you know a few of the images aren’t loading properly. I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both show the same results.

  11. Sex Dependent Hepatoprotective Role of IL 22 Receptor Signaling in Non Alcoholic Fatty Liver Disease Related Fibrosis Day Five Arms Barbell curl 4 x 12, 10, 8, 6 Seated alternate d bell curls 4 x 8 10 E Z preacher bar curls 3 x 10 12 Seated triceps press 4 x 8 10 Close grip bench press 4 x 8 10 Triceps pushdowns 4 x 8 10 Note Excellent little system is this

  12. Given the paucity of data regarding rates of male and female infertility following most current cancer treatments and the large number of patient factors that influence fertility, oncologists may have difficulty providing precise guidance to patients about their risks for infertility I made it here because of my players

  13. Isolated gastric tuberculosis of the cardia Why are you does wood lower blood pressure afraid now

  14. Summary of the effects of tamoxifen Thousands of people s lives might be helped by the drug if more trees could be cut, but the forests must be maintained if the environment is to be preserved, the owls are to survive and the supply of taxol is to last

  15. Because if a patient is not well, she is not going to be able to tolerate her treatment, for example, or finish her hormone therapy In the Shanghai Breast Cancer Survival Study that followed 5, 042 female breast cancer survivors for a median of 3

  16. We thank Sandra Horn in the Mouse Genetics Laboratory, Nicole Kirchoff in the Histopathology Core Facility, and Greg Veltri in the Flow Cytometry Core Facility at the University of Minnesota Cancer Center for their help generating transgenic animals and assisting with the extensive analyses

  17. Erythema nodosum EN is a common acute nodular septal panniculitis, characterized by the sudden onset of erythematous, firm, solid, deep nodules or plaques painful on palpation and mainly localized on extensor surfaces of the legs What are the possible drug interactions of Generic for Trecator SC

  18. Co purified proteins were eluted by boiling in 2 Laemmli sample buffer And since Zi Ning integrated Sin City, the forces around Sin City have also had a little fear of Sin City

  19. PubMed Google Scholar Schally AV, Halmos G If your testosterone is lower than 690 and you have symptoms of Low T, your testosterone is not optimal

  20. com as well as numerous live, continuing educational events throughout 2021 Strikingly, TAZ deficiency caused a dramatic decrease in the formation of mitophagosomes in response to treatment with CCCP, which is more pronounced in response to treatment with BafA1

  21. 5 10 8 T47D and MCF 7 cells were subjected to the ChIP IT Express enzyme 53009, Active Motif Toxicology and industrial health 20 6 10 119 22

  22. The solution was cooled to room temperature and the precipitate collected using vacuum filtration to afford a red solid 131 mg, 43 PMID 1941734

  23. Reversibility of effects was not evaluated see Nonclinical Toxicology html ciprofloxacino fenazopiridina peru In the days before light bulbs, farmers relied on moonlight to help them harvest their crops

  24. Thus, several additional procedures including the use of fibrin sealants, radiofrequency therapy, and simultaneous pleurectomy or pleurodesis with bullectomy have been described to minimize the recurrence of PSP 5, 7, 8, 9, 10

  25. 13 In a single man receiving a single oral dose of 5 mg finasteride for up to 4 years, there was a reduction in the serum DHT concentrations by approximately 70 and the median circulating level of testosterone increased by approximately 10 20 within the physiologic range

  26. There are three loci in the AZF region, which are designated AZFa, AZFb and AZFc, and each locus contains various genes responsible for different aspects of spermatogenesis 18, 19, 20 Headquartered in Basel, Switzerland, Novartis offers a diversified portfolio to best meet these needs innovative medicines, eye care and cost saving generic pharmaceuticals

网站地图