c - 1つのメモリブロックにデータを含むANSICハッシュテーブルの実装

Question

すべてのデータを1つのメモリブロックに保持するハッシュテーブルのオープンソースC実装を探しています。これにより、たとえばネットワーク経由で簡単に送信できます。追加されたすべてのキーと値のペアに小さなメモリを割り当てるものしか見つかりません。

よろしくお願いします。

編集：キーと値のペアのテーブルがおそらく何であれ、それは必ずしもハッシュテーブルである必要はありません。

Answer 1

このようなデータ構造をシリアル化する回数（およびネットワーク経由での送信もシリアル化）と、（プログラムで）このようなデータ構造を使用する回数はかなり少なくなります。そのため、ほとんどの実装では、「おそらくシリアル化が容易」な側面ではなく、速度に重点が置かれています。

すべてのデータが1つの割り当てられたメモリブロックにある場合、そのデータ構造に対する多くの操作は、次のことを行う必要があるため、少しコストがかかります。

• 追加操作でメモリを再割り当てします
• 削除操作で最も可能性の高い圧縮/バキューム（あなたがとても好きな1つのブロックが密集していて穴がないように）

ほとんどのネットワーク操作はとにかくバッファリングされ、キーを繰り返し処理してキーと値を送信するだけです。

Answer 2

UNIXシステムでは、おそらく共有メモリバッファを使用します（を参照shm_open()）。または、MAP_SHAREDフラグが設定されたメモリマップファイルが利用できない場合は、OS固有の違いを参照してください。http://en.wikipedia.org/wiki/Mmap

両方が利用できない場合shm_openでもmmap、ディスク上のファイルを（ある程度）使用できる場合は、適切なロックに注意する必要があります。次のプロセスにロック解除信号を送信し、おそらくファイルの更新された部分、次にそのプロセスはファイルを再度ロックし、関心のある部分を探して通常どおりに続行します（更新/削除など）。

いずれの場合も、固定幅のキーとシークのペアを使用するなど、ハッシュテーブルのレイアウトや任意のレイアウトを自由に設計できます。そうすれば、ハッシュテーブルのキーにすばやくアクセスでき、必要に応じてデータ部分を探してから、コピー/削除/変更などを行うことができます。

もちろん、このファイルはRAMディスク上にあるのが理想的です。

Answer 3

ハッシュテーブルを提供するライブラリは、詳細を隠して効率的に機能させる傾向があるため（通常、プログラマーがハッシュタブを使用するときに必要なものです）、通常、メモリの処理方法は最終的なプログラマーの目から隠されており、プログラマーは信頼すべきではありません。特定の「メモリレイアウト」については、ライブラリの次のバージョンで変更される可能性があります。

使用に最も便利な方法でハッシュテーブルをシリアル化（および非シリアル化）する独自の関数を作成します。シリアル化されたコンテンツは、必要に応じて何度も保持できます（もちろん、ハッシュテーブルが変更された場合は、メモリに保持されているシリアル化された「バージョン」を更新する必要があります）。

Answer 4

アキラ（+1）に完全に同意します。データの局所性に関するもう1つのコメント。テーブルが大きくなると、または衛星データが十分に大きい場合は、キャッシュの汚染が最も確実に発生し、テーブルの操作がさらに遅くなります。つまり、レベル1/2/3のキャッシュチェーンを使用してサービスを提供できます。衛星データにアクセスする必要がある場合（シリアル化など）、キャッシュミスに耐えながら、キーデータを迅速に送信します。