プレーンCの単一文字からポインターへのマッピングの実装

Question

私は高水準言語のプログラミング経験があり、数週間前に（学術的理由で）プレーンCでコーディングを開始しました。私はmap<char,myStruct*>のようなデータ構造を実装したいと思います。

これで十分ではない場合：可能なすべてのSINGLE charのどこかで定義した構造体へのポインタへの「マッピング」が必要です。 2 charが同じstructを指し示すことができないようにする方法があれば（地図上に新しい要素を挿入するときはcharをチェックせずに）、それはきちんとしていますが、それは厳密には必要ではありません。また、マップからペアリングを削除し、同じキーであるが異なるポインターでペアリングを再挿入できるようにする必要があります。

私はこれを考えて、すべての可能な文字の長さをポインタ配列として作成し、配列インデックスとしてcharを使用して対応するポインタを格納することができたと考えました。これはうまくいくかもしれませんが、私のアプリケーションで2つの文字だけを使用すると、そのアドレスに多くのスペースを割り当てるのは非効率的です。

まだ、私は他の解決策は考えられませんでした（私はC初心者だと考えていますが、驚くことではありません）。私は、たとえあいまいであっても、正しい方向への提案には感謝します。

Answer 1

、最も簡単な方法は、単に文字データ型の最大値に等しい静的なサイズの配列を行うことです。

64と仮定すると

#include <limits.h> 
void * mapping[1u << CHAR_BIT]; 

8ビットのポインタと8ビットのcharの場合、これはマップ全体の8 * 256 = 2,048バイトのメモリを占有します（あなたが格納している "ユーザーデータ"は除く）。 64ビットシステム上で動作するプログラムでは、2 KBのメモリが簡単です。この実装の容易さとスピードは、無駄なメモリのバランスをよく取る必要があります。

配列の "物理的な"サイズを制限したい場合に最も簡単なことは、1文字をハッシュすることですが、次にハッシュの衝突を扱う必要があります。

struct ValueChain 
{ 
    struct ValueChain *next; 
    void *value; 
    char key; 
} 

#define MAP_SIZE 127 /* This should be prime. */ 
struct ValueChain* mapping[MAP_SIZE]; 

は、ここでは、ポインタ配列のサイズを半分にしましたが、各値のコストが増加している：

あなたのような何かを行うことができます。また、衝突した値を挿入するときに動的な割り当てが必要になります。

さらにコンパクトにすることができます。

#define MAP_SIZE 31 
struct ValueChain mapping[MAP_SIZE]; 

ここで、アレイ内の各値は、完全ValueChain「リストヘッダ」ではなく一方にだけポインタです。 64ビットマシンでは、mapping配列の場合はおそらく約558バイトが使用されますが、衝突を検出するまで動的割り当てを行う必要はありません。

これらのハッシュは、ちょうどconst char key = myChar % MAP_SIZE;に近似することができます。

Answer 2

あなたのキーは文字列であると仮定します。

まあ...自分で実装する必要がない場合は、don'tとしてください。

理論的にはそれほど難しいことではありません。

キーと値とオプションのリンクリストへのポインタを含む配列を作成します。

ハッシュマップにアクセスすると、ハッシュされたキーのモジュロをとります。これは、配列内の位置です。次に、ハッシュされていないキーと格納されたキーを比較して、衝突を検出する必要があります。彼らがあなたと一致すれば、それを見つけました。そうでない場合は、リンクされたリストをループし、一致するまでキーを比較する必要があります。

明らかにこれは簡単な実装であり、メモリを節約してパフォーマンスを改善するためにはるかに多くのことが可能です。 （コメンターが示唆されているようにして）あなたが言うのと同じように

Answer 3

struct myStruct array[1u << CHAR_BIT]; 

#define uchar_to_mystruct_ptr(c) (c >=0 && c < (1u << CHAR_BIT) ? &array[c] : NULL)