◎山口陽平・岩田茂樹（電通大）

ハッシュ表は様々なアプリケーションにおいて用いられるデータ構造であるが、ハッシュ表の大きさを超えるデータを保存することはできない。
上書きハッシュ表は、データを書き込む際にハッシュ値で与えられたスロットに常に書き込む方式のハッシュ表であり、データを保存する回数に制限は無いが、スロット上に書かれていた以前のデータは上書きされて削除される。
本稿では、駒を置いていく形式のパズルの解を深さ優先探索により求めるプログラムにおいて、上書きハッシュ表の有効性をコンピュータ実験と理論的計算とから明らかにする。