リンクされたリストではなく (2 次元) 配列にオブジェクトを格納する C でのハッシュテーブルの実装を探しています。つまり、衝突が発生した場合、衝突を引き起こしているオブジェクトは、リンクされたリストの先頭と最初の要素にプッシュされるのではなく、次の空き行インデックスに格納されます。
さらに、ポインターによって参照されるのではなく、オブジェクト自体をハッシュテーブルにコピーする必要があります。(オブジェクトはプログラムの存続期間全体にわたって存続するわけではありませんが、テーブルは存続します)。
そのような実装には深刻な効率上の欠点がある可能性があり、「標準的なハッシュ方法」ではないことはわかっていますが、非常に特殊なシステムアーキテクチャに取り組んでいるため、これらの特性が必要です。
ありがとう
非常に単純な実装:
char hashtable[MAX_KEY][MAX_MEMORY];
int counts[MAX_KEY] = {0};
/* Inserting something into the table */
SomeStruct* some_struct;
int hashcode = compute_code(some_struct);
int size = sizeof(SomeStruct);
memcpy(hashtable[hashcode] + counts[hashcode] * size, some_struct, size);
++counts[hashcode];
に対するチェックを忘れないでくださいMAX_MEMORY。
私の推測では、あなたのシステムは動的メモリ割り当てを許可していません。したがって、データ (オブジェクトの合計数と予想される衝突の最大数) に適した配列の境界を事前に定義し、さらにオブジェクトのカスタム ハッシュ関数を定義する必要があるため、独自のハッシュ テーブルを実装するのが最適な場合があります。
これは C ではなく C++ ですが、Google Sparse Hashを見てください。いくつかのアイデアが得られるかもしれません。重要な要件は、格納されているオブジェクトが存在する方法を持っていることnullです。