概要
一般的なhashmapのサポートするキーの検索と挿入/削除に加えて、２つのhashmapを併合して１つにする操作を全てO(α(N))で行うhashmapの解説です。(α()はアッカーマン関数の逆関数)
注意点として、併合する可能性のあるhashmapにおいてkeyの重複は許されません。
謝辞
本記事の執筆にあたって、核となる原案をはむこさん(twitterアカウント:@hamko_intel)に頂きました。ここに感謝の意を表します。
基本的なアイデア(というか全て)
※以降、挿入をinsert、削除をerase、検索をfind、併合をmergeと書きます
複数あるhashmapに存在するkeyを別に管理するのではなく、大きな１つのhashmapで管理します。これをMと呼ぶことにします。また、各key及び各hashmapに番号を振り、それをノードとしてUnion-Find-Tree(以降Uと呼びます)でそれらを管理します。
あるkeyがあるhashmapに属しているとき、またその時に限ってUでそれらは同じ集合に属しているという条件を常に維持するようにしましょう。すると、各操作は以下のように表現することが出来ます。
・find
M内でkeyを探索し、それと探索したいhashmapそれぞれの番号をUで同一集合か判定します。同じ集合に属していれば値を、さもなくば無効値を返せばよいです。
・insert
M内に値を挿入し、値と一緒にkeyに振る番号を格納します。Uでhashmapの番号とkeyの番号を併合します。後述しますが、erase操作のために常にkeyの番号の方を子にするようにします。keyの方は集合のサイズが1なのでこれはUnion-Find-Treeの併合操作の条件を満たすものであり、計算量はα(N)から悪化しません。
・erase
M内で値を削除し、その際に削除したkeyに振られている番号も取得します。U内で対応するノードを切り離します。ここで、insertの際の条件よりkeyの番号のノードには子が存在しません。つまり、特殊な操作は必要なく単純に切り離せばよいです。また、この操作は定数時間で実行されるためこれも計算量を悪化させることはありません。
・merge
U内で２つのhashmapに振られている番号のノードの集合を併合すればよいです。１つになったhashmapに振る番号はもとの２つの番号のどちらか適当な一方にすればよいです。
時間計算量はMでの操作がO(1)、Uでの操作が償却O(α(N))となるので全体で償却O(α(N))となります。空間計算量はO(N)です。Union-Find-TreeはO(N)で再構築ができるので、リハッシュによる動的拡張にも対応可能です。
実装例
上手い実装が思いついていないため完成していませんが、完成したら追記する予定です。
その他
mergeの際にkeyの重複を許したい場合、データ構造をマージする一般的なテクと呼ばれる方法で償却O(logN)で可能になります。
