C-個別のチェーンハッシュテーブルの作成-問題
私はこれを行うのにしばらく時間を費やし、理解できる変数などを配置するように努力しました。それをきれいに見せて片付けようとしました。簡単にデバッグできるように。しかし、問題が見つからないようです...端末は何も出力しません。私の間違いを特定するのを手伝ってください！
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct list_node *node_ptr;
struct list_node
{
node_ptr next;
char *key;
char *value;
};
typedef node_ptr LIST;
typedef node_ptr position;
struct hash_table
{
LIST *list_ptr_arr;
unsigned int table_size;
};
typedef struct hash_table *HASHTABLE;
unsigned long long int
hash(const char *key, unsigned int hash_size)
{
unsigned long long int hash;
for(int i = 0; key[i]; i++)
{
hash = (hash<<32)+key[i];
}
return (hash%hash_size);
}
unsigned int
next_prime(int number)
{
int j;
for(int i = number; ; i++)
{
for(j = 2; j<i; j++)
{
if(i%j == 0){break;}
}
if(i==j){return j;}
}
}
HASHTABLE
initialize(unsigned int table_size)
{
HASHTABLE H;
H = (HASHTABLE) malloc(sizeof(struct hash_table));
if(H==NULL){printf("Out of Space!"); return 0;}
H->table_size = next_prime(table_size);
H->list_ptr_arr = (position*) malloc(sizeof(LIST)*table_size);
if(H->list_ptr_arr==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr = (LIST*) malloc(sizeof(struct list_node)*table_size);
for(unsigned int i = 0; i<table_size; i++)
{
if(H->list_ptr_arr[i]==NULL){printf("Out of Space!"); return 0;}
H->list_ptr_arr[i]=NULL;
}
return H;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
node_ptr prev;
while(entry!=NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
prev = entry;
entry = prev->next;
}
entry = (position) malloc(sizeof(struct list_node));
entry->value = malloc(strlen(value)+1);
entry->key = malloc(strlen(key)+1);
strncpy(entry->key,key,strlen(key));
strncpy(entry->value,value,strlen(value));
entry->next = NULL;
prev->next = entry;
}
void
dump(HASHTABLE H)
{
for(unsigned int i = 0; i<H->table_size; i++)
{
position entry = H->list_ptr_arr[i];
if(H->list_ptr_arr[i]==NULL){continue;}
printf("slot[%d]: ", i);
for(;;)
{
printf("%s|%s -> ", entry->key, entry->value);
if(entry->next == NULL)
{
printf("NULL");
break;
}
entry = entry->next;
}
printf("\n");
}
}
int main()
{
HASHTABLE H = initialize(10);
insert("name1", "David", H);
insert("name2", "Lara", H);
insert("name3", "Slavka", H);
insert("name4", "Ivo", H);
insert("name5", "Radka", H);
insert("name6", "Kvetka", H);
dump(H);
return 0;
}
それを変更していくつかのことを少し変更しようとしましたが、何も役に立ちませんでした...
よろしくお願いします！
回答
いくつかの美しさの問題と、コードを壊す少なくとも2つのエラーがあります。ささいなことには立ち入りません。ほとんどが文体ですが、あなたinitialize()とinsert()関数は機能しません。
ではinitialize()、あなたのためにメモリを割り当てるH->list_ptr_array二回。それは正当な理由もなく最初の割り当てからメモリをリークしますが、もちろん、それはあなたのコードをクラッシュさせることはなく、ただリークするだけです。2番目の割り当てでは、間違ったサイズを割り当て、を使用しますsizeof(struct list_node) * tale_sizeが、構造体ではなくポインターの配列が必要です（構造体はポインターを保持するため、より大きくなります）。繰り返しになりますが、メモリを浪費するだけで、クラッシュすることはありません。それでも、適切なメモリを使用したほうがよいでしょう。
H->list_ptr_arr = malloc(table_size * sizeof *H->list_ptr_arr);
の結果をキャストする必要はありませんmalloc()。それはaでvoid *あり、ポインタ型にキャストする必要はありませんが、これは文体の問題です。その行の重要な部分は、割り当てた変数から基になるデータのサイズを取得できることです。これにより、ある時点でタイプを変更した場合でも、常に正しいサイズを取得できることが保証されます。私もsizeof(type)時々使う傾向がありますsizeof *ptrが、より良いパターンであり、慣れる価値があります。
とにかく、間違った量のメモリを割り当てても、十分に割り当てるので、それが原因でプログラムがクラッシュすることはありません。ただし、テーブル内の割り当てられたビンを実行すると、がである場合はエラーが返されますNULL。それらはまったく初期化されていないので、もしそうならNULL（そしてそうかもしれない）、それは純粋な運によるものです。または、それをエラーの兆候と見なす場合は、不幸です。しかし、NULLここで割り当てエラーのシグナルを検討する場合、そうNULLではないと結論付けた直後に各ビンを初期化するのはなぜですか？
現状では、NULL配列にポインタが含まれていると初期化が中止されます。また、で割り当てエラーをチェックしないためmain()（テストでは問題ありません）、プログラムがクラッシュする理由である可能性があります。これは主な問題ではなく、偶然にNULLゴミ箱の1つに入った場合にのみ発生しますが、発生する可能性があります。NULLビンを実行するときのチェックは行わないでください。ビンは初期化されていません。それぞれをに設定するだけNULLです。
それはinsert()主な問題にあります。あなたのprev変数は前に初期化されていないwhile-ループ、そしてあなたがループを入力しない場合、それはどちらかそれの後ではありません。が初期化されていないprev->next = entry場合の設定prevは問題を引き起こし、クラッシュエラーの可能性があります。特に、ビンに初めて何かを挿入するときは、にentryなることを考えると、最初にNULLエラーをトリガーします。初期化されていないポインタを逆参照するとどうなるかは定義されていませんが、何か良いことを意味することはめったにありません。クラッシュは最良のシナリオです。
私はここで論理を理解しています。prevリストに沿って移動entryして、最後に新しいものを挿入できるようにします。ビン内のエントリをループする前に、最後の要素がありません。しかし、それは、新しいエントリを挿入する場所への初期化されたポインタを持てないという意味ではありません。ポインタへのポインタを使用する場合は、テーブルの配列のエントリから始めることができます。それはではないlist_nodeので、のためにはlist_node *なりませんprevが、list_node **はうまく機能します。あなたはこのようなことをすることができます：
node_ptr new_entry(const char *key, const char *value)
{
node_ptr entry = malloc(sizeof *entry);
if (!entry) abort(); // Add error checking
entry->value = malloc(strlen(value) + 1);
entry->key = malloc(strlen(key) + 1);
strncpy(entry->key, key, strlen(key));
strncpy(entry->value, value, strlen(value));
entry->next = NULL;
return entry;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr entry = H->list_ptr_arr[slot];
// Make sure that we always have a prev, by pointing it
// to the location where we want to insert a new entry,
// which we want at the bin if nothing else
node_ptr *loc = &H->list_ptr_arr[slot];
while(entry != NULL)
{
if(strcmp(entry->key, key)==0)
{
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
return;
}
// make loc the entry's next
loc = &entry->next;
// and move entry forward (we don't need prev->next now)
entry = entry->next;
}
// now loc will hold the address we should put
// the entry in
*loc = new_entry(key, value);
}
もちろん、ビン内のリストは特定の順序で並べ替えられたり保持されたりしないため（言及していない制約がない限り）、新しいエントリを追加する必要はありません。それらを追加することもできます。そうすればloc、他の線形検索のためにそのようなものをドラッグする必要はありません。あなたは次のようなことをすることができます：
node_ptr find_in_bin(const char *key, node_ptr bin)
{
for (node_ptr entry = bin; entry; entry = entry->next) {
if(strcmp(entry->key, key)==0)
return entry;
}
return 0;
}
void
insert(const char *key, const char *value, HASHTABLE H)
{
unsigned int slot = hash(key, H->table_size);
node_ptr *bin = &H->list_ptr_arr[slot];
node_ptr entry = find_in_bin(key, *bin);
if (entry) {
free(entry->value);
entry->value = malloc(strlen(value)+1);
strncpy(entry->value,value,strlen(value));
} else {
*bin = new_entry(key, value, *bin);
}
}
この方法で初期化と挿入を修正すれば、コードは機能するはずです。それは私がそれを通過させたいくつかのテストのために行います、しかし私は何かを逃したかもしれません。
それ自体はエラーではありませんが、それでもすぐにコメントします。このnext_prime()機能は、エラトステネスのふるいの遅いバージョンのように見えます。それは問題ありません、それは素数を計算します（私が何かを逃した場合を除いて）、しかしそれはあなたが必要とするものではありません。グーグルで検索すると、かなり大きなKの最初のK素数のテーブルが見つかります。コードに簡単に埋め込むことができます。つまり、テーブルにプライムサイズを絶対に持たせたい場合です。ただし、その必要はありません。他のサイズのテーブルを使用しても問題はありません。
ハッシュのモジュロ素数にはいくつかの利点がありますが、これが機能するためにハッシュテーブルが素数のサイズである必要はありません。大きな素数PとサイズMのハッシュテーブルがある場合、（（i％P）％M）を実行すると、モジュロPを実行する利点と、テーブルサイズMを使用できるという便利さが得られます。したがって、Mが2の累乗である場合は簡単であり、最後のモジュロ演算は非常に高速なビットマスキングになります。
#define mask_k(n,k) (n & ((1 << k) - 1))
そして後で...
int index = mask_k(i % P, k); // where table size is 1 << k
i % Pかもしれないが、それはあなたのハッシュ関数がどのように良いに依存し、必要ではありませんか。乱数に近いハッシュ関数がある場合、のビットiはランダムであり、k最下位ビットもランダムであり、それ% Pを改善するために何もしません。ただし、素数を法として実行する場合は、大きな素数に対して実行し、小さいテーブルサイズにマスクすることができるため、素数であるテーブルサイズを使用する必要はありません。とにかく素数のテーブルサイズが必要な場合は、素数のテーブルを使用してください。テーブルのサイズを変更するたびに新しい素数を計算する必要があるのは遅いです。