Split-ordered linked list: lock free hash table
ロックを使わず共有できるハッシュテーブル
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.7132&rep=rep1&type=pdf
の論文のスライド資料を作りました。
Hashmapは大きく分けてオープンアドレッシングとクローズドアドレッシングの2種類に分かれ、こちらは後者です。
Linear-probingなどを行う物と異なり、ハッシュ値が必ず1つのバケットのみと対応するからでしょうか？
Lock-free linked-listを利用することでバケット内部での競合を解決すると共にバケットの拡張でお互いを邪魔することもありません。
