noshi91のメモ

データ構造のある風景

2018-02-28から1日間の記事一覧

各操作とmergeをO(α(N))で行うhashmap

概要 一般的なhashmapのサポートするキーの検索と挿入/削除に加えて、2つのhashmapを併合して1つにする操作を全てO(α(N))で行うhashmapの解説です。(α()はアッカーマン関数の逆関数) 注意点として、併合する可能性のあるhashmapにおいてkeyの重複は許され…