并發資料結構-1.6 哈希表

典型可擴充的哈希表即一個可調整大小的桶數組(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)之間移動元素或重新排序清單帶來地複雜性需求。