并发数据结构-1.6 哈希表

原文链接，译文链接，译者：iDestiny，校对：周可人

典型可扩展的哈希表即一个可调整大小的桶数组(buckets), 每一个桶存放预期数量的元素，因此哈希表平均在常量时间内进行插入，删除，查询操作。哈希表调整大小的主要成本—–在于新旧桶(buckets)之间进行重新分配操作，该操作被分摊到所有表操作上，所以平均操作时间也是常量的。哈希表调整大小就是扩容，在实践中，哈希表仅需要增加数组大小即可。

Michael实现了一个可并发，不可扩展的哈希表(通过对哈希表中每个桶进行读写锁约束)。然而，为了保证元素数量增长时的性能，哈希表必须可扩展。

在80年代，Ellis和其他人基于二级锁机制，为分布式数据库设计了一个可扩展且并发的哈希表。Lea的可扩展的hash算法在非并发环境下表现出了高性能，该算法是基于Litwin的线性序列hash算法，它用了不同的加锁方案：用少量的独占锁代替原本对每一个桶都加锁，并且当调整哈希表大小时，允许并发查询操作，但不能并发插入或删除。当哈希表大小需要扩展为2倍时，调整大小表现为对所有内部桶(buckets)进行重构。

正如之前讨论的，基于锁的可扩展的哈希表算法同样具有阻塞同步所带来的典型的缺点。这些问题会由于对哈希表所有新添加桶(buckets)进行重分配变得更严重。因此无锁可扩展的哈希表是一个既实际又理论的问题。

如1.5节描述的，Michael在Harries工作之上，提供了一个有效的，基于CAS，无锁的链表实现。然后将此原理运用到并发环境下性能不错的无锁的hash结构中：一个固定大小的hash桶数组，每个桶由无锁链表实现。但是，要使一个无锁的链表数组可扩展很困难，因为当桶(buckets)数组扩展时，要在无锁方式下重新分配元素不是很容易的。在两个不同桶链表之间移动元素需要两个CAS操作同时原子地完成，这点在目前的体系结构中是不可能做到的。

Greenwald展示了怎么用他的双手模拟技术(two-handed emulation)来实现一个可扩展的哈希表。然而，这种技术使用了DCAS同步操作，该操作在当今的架构中不可用，并且在全局调整大小时会带来过多的工作。

Shalev和Shavit在当今架构下提出了一种无锁可扩展的哈希表。他们的核心思想在于将元素放在单个无锁链表中，而不是每个桶(bucket)中的链表。为了让操作能够快速访问链表, Shalev-Shavit算法维护了一个可调整大小的hints数组(指向链表的指针)，相关操作通过hints数组中的指针找到接近相关元素的位置，然后顺着该指针找到元素位置。为了保证每个操作平均能在常量步骤内完成，当链表中的元素个数增长时，细粒度的hints数组必须要添加。为了使hints数组能简单有效地被装配，链表由一个递归分割顺序来维护。该技术使得新的hints能够增量装配，从而消除了原子地在桶(bucket)之间移动元素或重新排序列表带来地复杂性需求。