導入
実務で複雑な木構造やシンボリックなデータを扱う際、メモリ使用量が急増してGC（ガベージコレクション）が頻発した経験はありませんか？データの内容が同じであっても、プログラム上で別々に生成されれば、メモリ上では異なる領域を占有してしまいます。今回紹介する「Hash-consing（ハッシュコンシング）」は、構造が同一のデータをメモリ上で一意な実体に集約することで、メモリ消費を劇的に抑え、さらには構造の比較をポインタ比較（O(1)）にまで高速化できる強力なテクニックです。
基礎知識
Hash-consingとは、一言で言えば「データの正規化」です。通常、プログラミング言語では `A = {x: 1}`、`B = {x: 1}` と定義すると、メモリ上には異なる2つのオブジェクトが生成されます。これを、「構築時にハッシュテーブルを参照し、同じ内容のデータが既に存在すればその参照を返し、なければ新しく生成してテーブルに登録する」という仕組みに置き換えます。これにより、論理的に同じデータはメモリ上の物理的なアドレスも同一になります。
実装/解決策
実装の肝は「スマートコンストラクタ」です。通常のデータ構築処理を直接呼ぶのではなく、キャッシュ（ハッシュテーブル）を介する関数を経由させます。Haskellのような純粋関数型言語では、StateモナドやIORef/MVarを用いてハッシュテーブルの状態を管理し、データ生成の過程を隠蔽するのが一般的です。
サンプルプログラム
ここでは、Haskellで単純な整数式をHash-consingする例を示します。
import qualified Data.Map as M
import Data.IORef
import System.IO.Unsafe
— 整数式のデータ型
data Expr = Val Int | Add Expr Expr deriving (Show, Eq, Ord)
— グローバルなハッシュテーブル（実務ではReaderT等で保持することを推奨）
{-# NOINLINE cache #-}
cache :: IORef (M.Map Expr Expr)
cache = unsafePerformIO (newIORef M.empty)
— スマートコンストラクタ：ここを通すことで共有を強制する
mkAdd :: Expr -> Expr -> IO Expr
mkAdd e1 e2 = do
let newExpr = Add e1 e2
c <- readIORef cache
case M.lookup newExpr c of
Just existing -> return existing — 既存のポインタを返す
Nothing -> do
modifyIORef cache (M.insert newExpr newExpr) — 新規登録
return newExpr
— 使用例
main :: IO ()
main = do
a <- mkAdd (Val 1) (Val 2)
b <- mkAdd (Val 1) (Val 2)
-- aとbはメモリ上で同一の実体（ポインタ比較が可能）
print (a == b)
応用・注意点
注意点1：メモリリークの温床
ハッシュテーブルに全てのデータが残り続けるため、放置すると逆にメモリを圧迫します。実務では Weak Pointer（弱参照） を活用し、どこからも参照されなくなったデータはキャッシュからも自動的に削除される仕組みを組み込むのが定石です。
注意点2：スレッドセーフ
並行処理を行う場合は、ハッシュテーブルへのアクセスにロック（MVarやSTM）が必要です。オーバーヘッドとメモリ節約効果のトレードオフを慎重に計算してください。
Hash-consingは、コンパイラや数式処理系のような「同じ構造が大量に発生する」ドメインでは非常に強力です。まずは、繰り返し生成される小さなデータ構造から適用を検討してみてください。
コメント