-
题名基于优化的CAS算法实现线程安全的HashMap
被引量:2
- 1
-
-
作者
吴恩慈
-
机构
上海淇毓信息科技有限公司
-
出处
《软件》
2019年第6期185-190,共6页
-
文摘
HashMap内存数据结构存在相当广泛的应用场景,通过Hash函数的Key直接获取对应的值,能够确保搜索的时间复杂度为O(1)。HashMap数据结构存在哈希冲突与线程安全问题,悲观锁机制实现线程安全的方法存在很大的性能开销。本文提出了基于优化的CAS算法,实现线程安全的哈希映射数据结构,内部采用数组、链表和红黑树实现了高并发环境下读写操作。通过增加版本戳避免CAS算法的ABA问题,CAS算法实现的无锁方式避免了锁竞争的开销,使用红黑树来优化链表,确保大规模数据集的检索时间复杂度保持O(logn)。支持多线程扩容操作,在执行效率方面有良好的表现。通过大规模的并发压力测试,验证了该数据结构在性能上有稳定的提升。
-
关键词
无锁机制
分段锁
cas算法优化
红黑树
线程安全
-
Keywords
Lock-free
Segment Lock
Optimized cas
Red-black Tree
Thread-safe
-
分类号
TP311.12
[自动化与计算机技术—计算机软件与理论]
-