Cでの非常に単純なマップの実装（コーチングの目的）？
https://stackoverflow.com/questions/1234514
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ファイル内のURLを読み取り、各URLホストで gethostbyname（）を実行するプログラムがあります。この呼び出しはかなり時間がかかります。それらをキャッシュしたい。
キャッシングに使用できる非常に単純なマップベースのコードスニペットがCにありますか？ （私はただ車輪を再発明したくありません。）
次の点が必要です：
- 許容ライセンスのオープンソース（BSDまたはパブリックドメインを考えてください。）
- 非常にシンプル：理想的には100 LOC未満
- キーは
char *および値はvoid *です。それらをコピーする必要はありません。 -
remove（）を実際に実装する必要はありませんが、contains（）が必要か、またはput（）で値を置き換える必要があります。
PS： homework というタグを付けました。私はただ怠けているだけで、再実装中に遭遇する可能性のある一般的な落とし穴をすべて避けたいと思っています。
解決
これは非常にシンプルで素朴なものです
- 固定バケットサイズ
- 削除操作なし
- キーと値を挿入し、オプションでそれらを解放できます
：
#include <string.h>
#include <stdlib.h>
#define NR_BUCKETS 1024
struct StrHashNode {
char *key;
void *value;
struct StrHashNode *next;
};
struct StrHashTable {
struct StrHashNode *buckets[NR_BUCKETS];
void (*free_key)(char *);
void (*free_value)(void*);
unsigned int (*hash)(const char *key);
int (*cmp)(const char *first,const char *second);
};
void *get(struct StrHashTable *table,const char *key)
{
unsigned int bucket = table->hash(key)%NR_BUCKETS;
struct StrHashNode *node;
node = table->buckets[bucket];
while(node) {
if(table->cmp(key,node->key) == 0)
return node->value;
node = node->next;
}
return NULL;
}
int insert(struct StrHashTable *table,char *key,void *value)
{
unsigned int bucket = table->hash(key)%NR_BUCKETS;
struct StrHashNode **tmp;
struct StrHashNode *node ;
tmp = &table->buckets[bucket];
while(*tmp) {
if(table->cmp(key,(*tmp)->key) == 0)
break;
tmp = &(*tmp)->next;
}
if(*tmp) {
if(table->free_key != NULL)
table->free_key((*tmp)->key);
if(table->free_value != NULL)
table->free_value((*tmp)->value);
node = *tmp;
} else {
node = malloc(sizeof *node);
if(node == NULL)
return -1;
node->next = NULL;
*tmp = node;
}
node->key = key;
node->value = value;
return 0;
}
unsigned int foo_strhash(const char *str)
{
unsigned int hash = 0;
for(; *str; str++)
hash = 31*hash + *str;
return hash;
}
#include <stdio.h>
int main(int argc,char *argv[])
{
struct StrHashTable tbl = {{0},NULL,NULL,foo_strhash,strcmp};
insert(&tbl,"Test","TestValue");
insert(&tbl,"Test2","TestValue2");
puts(get(&tbl,"Test"));
insert(&tbl,"Test","TestValueReplaced");
puts(get(&tbl,"Test"));
return 0;
}
他のヒント
Christoper Clark'sハッシュテーブルの実装は非常に簡単です。 100行を超えていますが、それほど多くはありません。
Clarkのコードは Googleの同時実行ライブラリ。
std :: map は、ボンネットの下にある赤黒のツリーです。 Cの既存の赤黒ツリー実装を使用するのはどうでしょうか。リンクしたものは700 LOCに似ていますが、かなりよくコメントされており、大まかに見たところ正気に見えます。おそらく他の人を見つけることができます。これは「C赤黒木」でGoogleに最初にヒットしたものです。
パフォーマンスにこだわりがない場合は、不均衡なバイナリツリーや最小ヒープなどを使用することもできます。バランスの取れたバイナリツリーを使用すると、O（log n）ルックアップが保証されます。不均衡なツリーでは、ルックアップの最悪のケースはO（n）です（ノードが順序どおりに挿入される病理学的なケースの場合、リンクリストのように動作する1つの本当に長いブランチになります）メモリが正しい）平均ケースはまだO（log n）です。
次の実装を使用して試すことができます
コードスニペットではなく、高性能な分散キャッシュエンジン。
怠zyではなく、このようなものを書くことを避けるために深く賢明です。
これはライブラリが自分で使用したことはないが、何をしようと主張しているようだお願いします。
Dave Hansonの Cインターフェースと実装には、素敵なハッシュテーブルも含まれています。他の多くの有用なモジュール。ハッシュテーブルは150行で記録されますが、これにはメモリ管理、高次マッピング関数、および配列への変換が含まれます。ソフトウェアは無料で、この本は買う価値があります。
