二重ハッシュの実装のルックアップ関数を書くのに助けが必要です

Question

私は二重ハッシュを実装して、整数を格納して見つけました。格納されるアイテムの総数は〜5kです。これを行うには、まず〜10Kのデータベースをmallocします。エントリを作成するには、まずfind関数を呼び出します。返されたアドレスが値 '0'、すなわち空のスロットを有する場合、項目が挿入される。挿入が機能します。ただし、削除と変更のために、ルックアップ関数がいつか失敗します。これは、以下の一連のイベントが発生した場合に発生します。

entry1を10. ENTRY2が entry3インデックス20で、次いで、インデックス10に秒の衝突を第1の衝突を持って、最終的entry3は次いでENTRY2が削除されるインデックス30 に挿入されてしまった指標20に挿入されたインデックスに挿入されます。 今、entry3のルックアップはインデックス20を返しますが、この場所には値はありません。したがって、変更/削除は失敗します。

正しいルックアップ機能を作成する方法を教えてください。 "（* entry） - > key！= 0"チェックを使わずにdo-whileループを終了する条件を見つけることができません。

ありがとうございます。

#define DB_HASH_LEN 10009 

typedef struct node_ { 
    u_int32_t key; 
} hashnode_t; 

int 
vnid_db_open() 
{ 
    u_int32_t db_size = DB_HASH_LEN * sizeof(*db_start); 
    db_start = malloc(db_size); 
    if (db_start == NULL) { 
     return 0; 
    } else { 
     memset(db_start, 0, db_size); 
     return 1; 
    } 
} 

static inline u_int32_t 
get_hash_index(u_int32_t key, u_int32_t hash_len) 
{ 
    return (key % hash_len); 
} 

static inline u_int32_t 
get_hash_offset(u_int32_t key, u_int32_t hash_len) 
{ 
    return (1 + ((key/hash_len) % (hash_len - 1))); 
} 

void 
find_entry(u_int32_t key, hashnode_t **entry) 
{ 
    u_int32_t index = get_hash_index(key, DB_HASH_LEN); 
    u_int32_t offset = get_hash_offset(key, DB_HASH_LEN); 

    do { 
     *entry = db_start + index; 
     index = (index + offset) % DB_HASH_LEN; 
    } while ((*entry)->key != 0 && (*entry)->key != key); 
} 

int 
main(void) 
{ 
    hashnode_t *node = NULL; 
    u_int32_t op, key; 
    vnid_db_open(); 

    while (1) { 
     printf("op:"); 
     scanf("%d", &op); 
     getchar(); 

     printf("key:"); 
     scanf("%d", &key); 
     getchar(); 

     switch (op) { 
      case(0): 
       find_entry(key, &node); 
       if (node->key == 0) { 
        node->key = key; 
        printf("inserted %d\n", key); 
       } else if (node->key == key) { 
        printf("key %d exists for insert\n", key); 
       } else { 
        printf("key %d not found for insert\n", key); 
       } 
       break; 

      case(1): 
       find_entry(key, &node); 
       if (node->key == key) { 
        node->key = 0; 
        printf("deleted %d\n", key); 
       } else { 
        printf("key not found %d for delete\n", key); 
       } 
       break; 

      case(2): 
       find_entry(key, &node); 
       if (node->key == key) { 
        printf("found %d\n", key); 
       } else { 
        printf("key not found %d for lookup\n", key); 
       } 
       break; 

      default: 
       break; 
     } 
     fflush(stdin); 
    } 

    return 0; 
} 

bash-3.2$ ./a.out 
op:0 
key:11111111 
index 1121 offset 1111 
inserted 11111111 
op:0 
key:11111112 
index 1122 offset 1111 
inserted 11111112 
op:0 
key:11111113 
index 1123 offset 1111 
inserted 11111113 
op:0 
key:2111113 
index 9223 offset 211 
inserted 2111113 
op:0 
key:2111114 
index 9224 offset 211 
inserted 2111114 
op:0 
key:2111114 
index 9224 offset 211 
key 2111114 exists for insert 
op:0 
key:2111115 
index 9225 offset 211 
inserted 2111115 
op:0 
key:9223 
index 9223 offset 1 index 9224 offset 1 index 9225 offset 1 index 9226 offset 1 
inserted 9223 
op:1 
key:2111113 
index 9223 offset 211 
deleted 2111113 
op:2 
key:9223 
index 9223 offset 1 
key not found 9223 for lookup 

PS：私は、エントリがハッシュテーブルにないがあり、その後、最終的には完全な円を尽くすルックアップした場合、インデックスはSTART_INDEXに一致するという事実に、私はすることができます。この時点で基づいて、異なる検索機能を導入することができ検索を終了しますか？以下のコードをご覧ください。

void 
find_entry1(u_int32_t key, hashnode_t **entry) 
{ 
    u_int32_t index = get_hash_index(key, DB_HASH_LEN); 
    u_int32_t offset = get_hash_offset(key, DB_HASH_LEN); 
    u_int32_t start_index = index; 

    do { 
     printf("index %d offset %d ", index, offset); 
     *entry = db_start + index; 
     index = (index + offset) % DB_HASH_LEN; 
    } while ((start_index != index) && ((*entry)->key != key)); 

    printf("\n"); 
} 

クレジット：あなたの検索が終了しないように私は私のコメントで参照記事を1として

how to search using double hash in c

Answer 1

、あなたは「削除キー」のための特別な値を確保しなければなりませんそれがゼロを見つけるとき。

0は「未使用」を意味し、「特殊値」（たとえば-1）は「削除済みであり続ける」ことを意味します。 「特別な値」を持つエントリを再利用することができます。

検索を開始した「優先インデックス」に戻るときは、検索を終了する必要があります。検索時に「見つかりません」、挿入時に「テーブルがいっぱいです」という意味です。

詳細については、記事を参照してください。