GDBM で学ぶ Extendible Hashing最近仕事で GDBM を使う機会があり、GDBM で使われている extendible hashing に興味を持ったのでまとめてみました。 なお、今回対象にしている GDBM のバージョンは 1.12 です。 アジェンダ GDBM とは ハッシュテーブルの基礎 ハッシュ関数 衝突処理 リハッシュ Extendible Hashing GDBM による Extendible Hashing ハッシュ関数 ファイルヘッダのデータ構造 バケットのデータ構造 バケット要素のデータ構造 衝突処理 ディレクトリの拡張とバケットの分割 データベースファイルは要素数が多いと肥大化する おわりに 参考 GDBM とは http://www.gnu.org.ua/software/gdbm/ 曰く GNU dbm (or GDBM, for short) is a library of database f
