没有合适的资源?快使用搜索试试~ 我知道了~
首页无锁Hash表:Split-OrderedLists算法详解
无锁Hash表:Split-OrderedLists算法详解
需积分: 20 3 下载量 137 浏览量
更新于2024-07-18
收藏 605KB PDF 举报
无锁Hash表的实现方式是一项关键的高性能并发数据结构研究,由ORISHALEV和NIRSHAVIT两位作者在他们的论文中提出。该论文主要关注的是在现代架构上设计并实现一个可扩展的无锁哈希表,旨在提供并发插入、删除和查找操作,且期望的时间复杂度达到O(1)。这种创新的设计挑战了传统的无锁算法,因为它并非基于"物品在桶间移动"的传统思路,而是通过递归分有序列表(Split-OrderedLists)来实现。 在无锁Hash表的设计中,核心是分有序列表的概念,它是一种特殊的链接列表,其中元素被有序排列,使得每个元素能够通过单次比较和交换操作进行"分割"。这种方法允许哈希表在扩展时,不仅将新的元素添加到已有结构中,而且可以高效地维护数据的一致性,避免了传统锁机制带来的同步开销,从而提升了并发性能。尽管无锁算法通常期望在多程序环境中发挥最佳效果,但作者们还进行了大规模的共享内存多处理器实验,结果显示即使在非多程序环境下,他们的新算法也显示出优越的性能。 值得注意的是,实现这个无锁哈希表的关键在于代码的简洁性,仅使用了加载、存储和比较与交换操作,这大大降低了开发者在实际应用中的复杂性。这对于那些追求高并发、低延迟的应用场景,如大规模分布式系统、实时数据处理等,具有很高的实用价值。然而,由于其依赖于特定的硬件特性,可能对某些老旧或特殊架构的兼容性有所限制,因此在实际部署时需要仔细评估。 这篇论文提供了一种新颖的无锁哈希表设计,不仅实现了高效的并发操作,还展示了在不同环境下的性能优势,对于理解无锁数据结构和优化高并发场景下数据结构设计具有重要的理论和实践意义。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/10491635/bg6.jpg)
384 O. SHALEV AND N. SHAVIT
perform as well as Lea’s algorithms, even in nonmultiprogrammed cases, although
lock-free algorithms are expected to benefits systems mainly in multiprogrammed
environments. Under high loads, they significantly outperform Lea’s algorithm,
exhibiting up to four times higher throughput. They also exhibit greater robustness,
for example in experiments where the hash function is biased to create nonuniform
distributions.
The remainder of this article is organized as follows: In the next section, we
describe the background and the new algorithm in depth. In Section 3, we present
the full correctness proof. In Section 4, the empirical results are presented and
discussed.
2. The Algorithm in Detail
Our hash table data structure consists of two interconnected substructures (see
Figure 1): A linked list of nodes containing the stored items and keys, and an
expanding array of pointers into the list. The array entries are the logical “buckets”
typical of most hash tables. Any item in the hash table can be reached by traversing
down the list from its head, while the bucket pointers provide shortcuts into the list
in order to minimize the search cost per item.
The main difficulty in maintaining this structure is in managing the continuous
coverage of the full length of the list by bucket pointers as the number of items in
the list grows. The distribution of bucket pointers among the list items must remain
dense enough to allow constant time access to any item. Therefore, new buckets
need to be created and assigned to sparsely covered regions in the list.
The bucket array initially has size 2, and is doubled every time the number of
items in the table exceeds size · L, where L is a small integer denoting the load
factor, the maximum number of items one would expect to find in each logical
bucket of the hash table. The initial state of all buckets is uninitialized, except
for the bucket of index 0, which points to an empty list, and is effectively the
head pointer of the main list structure. Each bucket goes through an initialization
procedure when first accessed, after which it points to some node in the list.
When an item of key k is inserted, deleted, or searched for in the table, a hash
function modulo the table size is used, that is, the bucket chosen for item k is
k mod size. The table size is always equal to some power 2
i
, i ≥ 1, so that the
bucket index is exactly the integer represented by the key’s i least significant bits
(LSBs). The hash function’s dependency on the table size makes it necessary to
take special care as this size changes: an item that was inserted to the hash table’s
list before the resize must be accessible, after the resize, from both the buckets it
already belonged to and from the new bucket it will logically belong to given the
new hash function.
2.1. R
ECURSIVE SPLIT-ORDERING. The combination of a modulo-size hash
function and a 2
i
table size is not new. It was the basis of the well known se-
quential extensible Linear Hashing scheme proposed by Litwin [1980], was the
basis of the two-level locking hash scheme of Ellis [1983], and was recently used
by Lea [2003] in his concurrent extensible hashing scheme. The novelty here is
that we use it as a basis for a combinatorial structure that allows us to repeatedly
“split” all the items among the buckets without actually changing their position in
the main list.
剩余26页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/f1d0ac16730a45268ecde3b755c12c0c_lovelylichqq.jpg!1)
榕易
- 粉丝: 58
- 资源: 9
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)