世界上最简单的无锁哈希表 心已赠人 2022-07-31 04:51 120阅读 0赞 无锁哈希表(Lock-Free Hash Table )可以提高多线程下的性能表现,但是因为实现一个无锁哈希表本身的复杂度不小。(ps:真正的复杂在于出错之后的调试,因为多线程下的调试本身就很复杂,引入无锁数据结构之后,传统的看堆栈信息和打印log都基本上没有意义了。堆栈中的数据可能被并发访问破坏,而打印log本身可能会改变程序执行时对数据访问的时序。一个比较可行的做法是实现一个无锁版本和一个传统数据结构+锁的版本,出错后通过替换来定位是无锁数据结构本身的bug还是其他逻辑的bug)。所以对一个项目而言,无锁数据结构基本上是一把双刃剑。 据我所知,第一个用于实际开发的无锁哈希表是 [Dr. Cliff Click][] 为Java而写。在2007年他发布了这个无锁哈希表的源码并且在Google做了关于它G的报告([视频][Link 1])。我承认,在我第一次看这个报告的时候,我对它的大部分内容都不理解。Dr. Cliff Click是这个领域的先驱。([Maged M. Michael][] 在IBM做了大量关于无锁数据结构的研究。这个是2002年的一篇论文,关于哈希表,[http://www.research.ibm.com/people/m/michael/spaa-2002.pdf][http_www.research.ibm.com_people_m_michael_spaa-2002.pdf]) 很幸运,6年时间足够我理解Dr. Cliff Click所做的研究。事实上,你不必做一些前沿的探索,去实现一个完美的无锁哈希表。在这里我将分享我实现的这个版本。我相信有使用C++进行多线程开发经验的程序员,可以通过这篇博客梳理以前的经验,并且完全理解它。 ### 约束 ### 作为一个程序员,平时我们实现一个数据结构会本能的尽可能通用。这不是一件坏事,但是当我们把通用当作一个更重要的目标时,它可能会阻碍我们。在这里我走向另一个极端,实现了一个尽可能简单的,仅用于一些特殊环境的哈希表,下面是它的设计约束: 1. table 只接受类型为32位整数的key和value 2. 所有key必须非零 3. 所有的value必须非零 4. table的最大数目固定且必须是2的幂 5. 唯一可用的操作是SetItem和getItem 6. 有没有删除操作 当然你掌握了这种算法实现机制之后,可以在此基础上进行扩展,而不受这些限制的约束。(rehash,删除和遍历,这些都会增加复杂度,而且有引发新的ABA问题的可能性)。 ### 实现方法 ### 有很多种方法来实现一个哈希表。这里我选择了用我以前的帖子中描述的ArrayOfItems类做一个简单的修改,(前置扩展阅读)[ A Lock-Free… Linear Search?][A Lock-Free_ Linear Search] 这个哈希表被我称为HashTable1,和ArrayOfItems一样,它采用了一个巨大的key-value pairs数组实现。 <table style="border-collapse:collapse; border-spacing:0px; width:610px; border:0px!important; margin:0px!important; padding:0px!important; font-size:12px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <tbody style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <tr style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <td style="border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important"> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 1 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 2 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 3 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 4 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 5 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 6 </div> </td> <td style="width:582px; border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important"> <div style="margin-left:-10px; width:640px; border:0px!important; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">struct</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> Entry</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">mint_atomic32_t key;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">mint_atomic32_t value;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">};</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">Entry *m_entries;</code> </div> </div> </td> </tr> </tbody> </table> 在hashtable1中,仅仅只有数组本身而没有使用链接来处理碰撞。数组全部初始化为0,key为0时对应的节点为空。插入时,会通过线性搜索找到一个空节点。 ArrayOfItems和HashTable1之间唯一的区别是,ArrayOfItems是从0开始做线性搜索,而HashTable1使用[MurmurHash3′s integer finalizer][MurmurHash3_s integer finalizer]算法得到一个hash值,然后以这个hash值为起点开始搜索() <table style="border-collapse:collapse; border-spacing:0px; width:610px; border:0px!important; margin:0px!important; padding:0px!important; font-size:12px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <tbody style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <tr style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <td style="border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important"> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 1 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 2 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 3 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 4 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 5 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 6 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 7 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 8 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 9 </div> </td> <td style="width:582px; border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important"> <div style="margin-left:-10px; width:640px; border:0px!important; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">inline</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important"> static</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> uint32_t integerHash(uint32_t h)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">h ^= h >> 16;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">h *= 0x85ebca6b;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">h ^= h >> 13;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">h *= 0xc2b2ae35;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">h ^= h >> 16;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">return</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> h;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> </div> </td> </tr> </tbody> </table> 当我们使用相同的key做参数调用SetItem或GetItem方法时,它会在相同的index开始做线性搜索,而使用不同的key时,会在不同的index开始搜索。通过这种方式,可以提高查找到对应key所在节点的速度,并且保证多线程并发调用SetItem或GetItem的安全性。 [![hash-diagram][]][hash-diagram] HashTable1采用环形的搜索,当搜索到尾部时,会从数组头部开始继续搜索。在数组满之前,每次搜索都可以保证返回对应key所在的节点,或者是一个空节点。这种技巧被称为[open addressing][] with [linear probing][],,在我看来这无疑是对lock-free最友好的hash算法,事实上在Dr. Cliff Click为java实现的哈希表中也使用了相同的技巧。 ### 代码 ### SetItem的实现。它会扫描整个数组并且将value保存在与key对应的节点或空节点。这段代码与ArrayOfItems:: SetItem几乎相同,唯一的区别是计算了hash值并且按位与,保证index在数组边界内。 <table style="border-collapse:collapse; border-spacing:0px; width:731px; border:0px!important; margin:0px!important; padding:0px!important; font-size:12px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <tbody style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <tr style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <td style="border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important"> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 1 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 2 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 3 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 4 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 5 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 6 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 7 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 8 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 9 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 10 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 11 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 12 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 13 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 14 </div> </td> <td style="width:696px; border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important"> <div style="margin-left:-10px; width:640px; border:0px!important; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">void</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> HashTable1::SetItem(uint32_t key, uint32_t value)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">for</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (uint32_t idx = integerHash(key);; idx++)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">idx &= m_arraySize - 1;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">if</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> ((prevKey == 0) || (prevKey == key))</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">mint_store_32_relaxed(&m_entries[idx].value, value);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">return</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> </div> </td> </tr> </tbody> </table> GetItem的实现也同样和ArrayOfItems::GetItem有类似的改变。 <table style="border-collapse:collapse; border-spacing:0px; width:610px; border:0px!important; margin:0px!important; padding:0px!important; font-size:12px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <tbody style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <tr style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <td style="border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important"> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 1 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 2 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 3 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 4 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 5 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 6 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 7 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 8 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 9 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 10 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 11 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 12 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 13 </div> </td> <td style="width:575px; border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important"> <div style="margin-left:-10px; width:640px; border:0px!important; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">uint32_t HashTable1::GetItem(uint32_t key)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">for</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (uint32_t idx = integerHash(key);; idx++)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">idx &= m_arraySize - 1;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">if</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (probedKey == key)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">return</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> mint_load_32_relaxed(&m_entries[idx].value);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">if</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (probedKey == 0)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">return</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> 0; </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> </div> </td> </tr> </tbody> </table> 上述功能都是线程安全的,无锁的ArrayOfItems出于同样的原因:对数组的元素采用原子操作,使用 cas 操作修改节点的key值(使用内存栅障保证线程安全,事实上就是重新排列了内存访问指令的执行次序)。在[上一篇][A Lock-Free_ Linear Search]中有更详细的讨论。 最后,就像在以前的帖子中,我们可以优化SetItem,第一次判断是否可以避免使用CAS操作。如下这种优化,可以使示例应用程序运行快大约20%。 <table style="border-collapse:collapse; border-spacing:0px; width:759px; border:0px!important; margin:0px!important; padding:0px!important; font-size:12px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <tbody style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <tr style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <td style="border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important"> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 1 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 2 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 3 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 4 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 5 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 6 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 7 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 8 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 9 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 10 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 11 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 12 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 13 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 14 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 15 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 16 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 17 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 18 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 19 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 20 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 21 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 22 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 23 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 24 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 25 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 26 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 27 </div> </td> <td style="width:724px; border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important"> <div style="margin-left:-10px; width:640px; border:0px!important; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">void</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> HashTable1::SetItem(uint32_t key, uint32_t value)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">for</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (uint32_t idx = integerHash(key);; idx++)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">idx &= m_arraySize - 1;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Load the key that was there.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">if</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (probedKey != key)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// The entry was either free, or contains another key.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">if</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> (probedKey != 0)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">continue</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">; </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Usually, it contains another key. Keep probing.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// The entry was free. Now let's try to take it using a CAS.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">if</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> ((prevKey != 0) && (prevKey != key))</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">continue</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">; </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Another thread just stole it from underneath us.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Either we just added the key, or another thread did.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Store the value in this array entry.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">mint_store_32_relaxed(&m_entries[idx].value, value);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">return</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> </div> </td> </tr> </tbody> </table> 这个就是几乎可以精简的最简单的无锁哈希表,这里是它的代码链接: [source][] and [header][]。 一个忠告:与ArrayOfItems一样,HashTable1上的所有操作都采用了relaxed memory ordering做限制。因此,当在HashTable1中设置标记,共享一些数据供其他线程访问时,必须事先插入release fence。同样访问数据的线程在调用GetItem前需要acquire fence。 <table style="border-collapse:collapse; border-spacing:0px; width:710px; border:0px!important; margin:0px!important; padding:0px!important; font-size:12px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <tbody style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <tr style="border:0px!important; margin:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> <td style="border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; width:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important"> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 1 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 2 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 3 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 4 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 5 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 6 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 7 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 8 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 9 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 10 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 11 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 12 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 13 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 14 </div> <div style="border-width:0px 3px 0px 0px!important; border-right-style:solid!important; border-right-color:rgb(108,226,108)!important; margin:0px!important; padding:0px 0.5em 0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; text-align:right!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> 15 </div> </td> <td style="width:675px; border:0px!important; margin:0px!important; padding:0px!important; vertical-align:baseline!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; min-height:inherit!important"> <div style="margin-left:-10px; width:640px; border:0px!important; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:relative!important; right:auto!important; top:auto!important; vertical-align:baseline!important; min-height:inherit!important"> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Shared variables</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:gray!important">char</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> message[256];</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">HashTable1 collection;</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(0,102,153)!important">void</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> PublishMessage()</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">{ </code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Write to shared memory non-atomically.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; font-weight:bold!important; min-height:inherit!important; color:rgb(255,20,147)!important">strcpy</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">(message, </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:blue!important">"I pity the fool!"</code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">);</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Release fence: The only way to safely pass non-atomic data between threads using Mintomic.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">mint_thread_fence_release();</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="display:block; clear:both; border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; overflow:visible!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; color:rgb(0,130,0)!important">// Set a flag to indicate to other threads that the message is ready.</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important"> </code> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">collection.SetItem(SHARED_FLAG_KEY, 1)</code> </div> <div style="border:0px!important; margin:0px!important; padding:0px 1em!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important; white-space:pre!important"> <code style="border:0px!important; margin:0px!important; padding:0px!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; bottom:auto!important; float:none!important; height:auto!important; left:auto!important; line-height:1.1em!important; outline:0px!important; overflow:visible!important; position:static!important; right:auto!important; top:auto!important; vertical-align:baseline!important; width:auto!important; min-height:inherit!important">}</code> </div> </div> </td> </tr> </tbody> </table> ### 简单样例 ### 对HashTable1的一些测试对比,在上一篇帖子我做个一个类似的测试。它交替执行2个测试:一个采用2个线程,每个线程交替插入6000个key不同的item,另一个每个线程交替插入12000个key相同但是value不同的item。 [![sample\_application][sample_application]][sample_application] 代码放在github上,你可以自己编译和执行。编译说明见[README.md][] 在HashTable1没有满时—少于80%时—HashTable1表现的很好,我也许应该为这个说法做一些基准测试。但是以以往的常规的哈希表作为基准,我敢肯定你很难实现出性能更好的无锁哈希表。这似乎奇怪,HashTable1基于ArrayOfItems,看起来会很低效。当然,任何哈希表中,总会有发生碰撞的风险,而降阶到ArrayOfItems的风险并不为0。但是使用一个足够大的数组和类似MurmurHash3这样的hash函数,这种情况出现的很少。 在实际的工作中,我已经使用了一个和这个类似的hash-table。这是一个游戏开发的项目,我的工作是解决使用内存分配跟踪工具(memory tracker)之后对一个读写锁激烈的争用。迁移到无锁哈希表的过程非常棘手。相对HashTable1需要更复杂的数据结构,key和value都是指针而不是简单的整数。因此有必要在哈希表内部插入memory ordering。最终在此模式下运行:最坏情况下游戏的帧率提高了4-10 FPS。 [Dr. Cliff Click]: http://www.azulsystems.com/blog/cliff [Link 1]: http://www.youtube.com/watch?v=HJ-719EGIts [Maged M. Michael]: http://www.research.ibm.com/people/m/michael/pubs.htm [http_www.research.ibm.com_people_m_michael_spaa-2002.pdf]: http://www.research.ibm.com/people/m/michael/spaa-2002.pdf [A Lock-Free_ Linear Search]: http://preshing.com/20130529/a-lock-free-linear-search [MurmurHash3_s integer finalizer]: https://code.google.com/p/smhasher/wiki/MurmurHash3 [hash-diagram]: /images/20220731/f89089e469184cccb5e55b38aadfdd42.png [open addressing]: http://en.wikipedia.org/wiki/Open_addressing [linear probing]: http://en.wikipedia.org/wiki/Linear_probing [source]: https://github.com/mintomic/samples/blob/master/common/hashtable1.cpp [header]: https://github.com/mintomic/samples/blob/master/common/hashtable1.h [sample_application]: /images/20220731/988f8294d7004f0e82d67b9b262b3a06.png [README.md]: https://github.com/mintomic/samples#readme
相关 趣味算法——探索哈希表的神秘世界 文章目录 前言: 一、哈希表的魔力 二、哈希表的灵魂——哈希函数 1. 什么是哈希函数 2. 哈希函数的特性 3 怼烎@/ 2024年03月16日 21:50/ 0 赞/ 8 阅读
相关 哈希表 上一篇博客:[静态链表的介绍及实现][Link 1] > 写在前面:大家好!我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的 ╰半夏微凉°/ 2022年10月30日 07:24/ 0 赞/ 189 阅读
相关 世界上最简单的无锁哈希表 无锁哈希表(Lock-Free Hash Table )可以提高多线程下的性能表现,但是因为实现一个无锁哈希表本身的复杂度不小。(ps:真正的复杂在于出错之后的调试,因为多线程 心已赠人/ 2022年07月31日 04:51/ 0 赞/ 121 阅读
相关 哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速 系统管理员/ 2022年06月10日 01:26/ 0 赞/ 236 阅读
相关 哈希表 我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键 快来打我*/ 2022年06月05日 02:20/ 0 赞/ 338 阅读
相关 哈希表 1. 什么是哈希表 我们先来做个题(leetCode上387题) ![70][] public class Solution_387 { 朱雀/ 2022年05月16日 10:11/ 0 赞/ 277 阅读
相关 哈希表 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0 今天药忘吃喽~/ 2022年02月01日 14:36/ 0 赞/ 384 阅读
相关 【哈希表】 char FirstNotRepeatingChar(char pString) { // invalid input if(! r囧r小猫/ 2022年01月06日 11:33/ 0 赞/ 305 阅读
相关 哈希表 一、简介 如果所有的键都是小整数,那么我们可以用一个数组来实现无序的符号表,将键作为数组的索引i而数组中i(键)处储存的就是对应的值。 这样就可以快速地访问任意键的值, 旧城等待,/ 2021年12月22日 01:21/ 0 赞/ 380 阅读
相关 哈希表 【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na 傷城~/ 2021年08月11日 17:13/ 0 赞/ 534 阅读
还没有评论,来说两句吧...