CでHashTable（衝突を避けるためにリンクリストを使用する）を実装するために必要な構造体はありますか？

Question

ちょっと、私はここ数日間、Cのポインタ、構造体、データ構造について読んでいました。今度は、このチュートリアルに従うことで、Cでハッシュテーブルを実装しようとしています。https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm

しかし、tutorialspointは1つのハッシュテーブルしか存在しないと仮定し、グローバル化しています。さらに、tutorialspointは衝突を考慮しません。

構造体を1つのハッシュテーブルに限定しないようにしたいのですが、私はリンクされたリストで（衝突に対処するために）連鎖を組み込む予定です。私が説明する必要が

typedef struct node { 
    int key; 
    int data; 
    struct node* next; 
} node; 

typedef struct linkedList{ 
    node* head; 
    node* tail; 
    size_t size; 
} linkedList; 

typedef struct hashTable{ 
    //perhaps an array of linked list? This member is what I need help with 
    //And other potential members I am overlooking 
    size_t size 
} hashTable; 

いくつかのもの：私は、以下の持っている

1. ノードの構造体は、キー/データのペアとして機能し、それが持っている次のペアへのポインタを持っています同じハッシュコード。同じハッシュコードを持つすべてのノードは同じリンクリストに含まれます。

2. linkedList構造体は、最終的にハッシュテーブルの行になるリンクリストを表します。すべてのリンクリストは、ハッシュテーブル内の行になります。

3. hashTable構造体には、すべてのlinkedListsが含まれています。

どのように私はハッシュテーブルの構造体でのLinkedList構造体の配列を作ることができますか？私の3つの構造体で見落としている他のメンバはありますか？

ご協力いただきましてありがとうございます。

P.S.私はLinked Listプログラムで書いた方法を使うつもりです。 https://codereview.stackexchange.com/questions/176904/my-linked-list-implementation-in-c

Answer 1

typedef struct linkedList{ 
    node* head; 
    node* tail; 
    size_t size; 
} linkedList; 

私はあなたが本当にここsize_t sizeを必要としないと思います。実際のハッシュテーブルの構造体に来る何を、あなたができる：あなたができる方法を2、4、8、16、...：また

typedef struct has_map { 
    linkedList** table; // stores the actual collision chains. 
    size_t table_capacity; // the current capacity of table. 
    size_t size; // number of mappings in this hash map. 
} hash_map; 

を、私はあなたがtableの長さが2のべき乗を保つ示唆しますhash_code % hash_map->table_capacityをビット操作hash_code & (hash_map->table_capacity - 1)で変更してください。

Answer 2

ノードとリスト構造を使用することができます。ハッシュテーブルは、リストの配列を持つ構造体になります。ハッシュテーブルのサイズは動的なものではなく、のは、一定のサイズを使用させることができます：

enum { 
    hashSize = 32 
}; 

typedef struct hashTable { 
    linkedList list[hashSize]; 
    size_t size;      // How many elelents overall? 
} hashTable; 

あなたのハッシュ関数はhashSizeよりも小さい符号なしのハッシュ値を返す必要があります。

しかし、実際にリンクリスト構造は必要ありません。この構造は、前面と後端に簡単に挿入することができ、要素の数も保持します。リストの要素は順序付けされていないので、常に先頭に挿入することができます。実際にはサイズは必要ありません。したがって、リンク先のリストを頭のポインタだけで定義することができます。NULL：

（しかし、あなたはすでにリンクリストのコードを持っている場合は、リンクリストの配列を移動するための方法かもしれません。）

---

あなたがリンクされtutorialspointコードに関する注記：これは、衝突に応じるん別のアプローチを使用しています。各ハッシュコードには1つのスロットしかありません。ハッシュコードのスロットがすでに使用されている場合は、次の空きハッシュコードが使用されます。

このアプローチでは、単に要素を削除することはできません。ハッシュ値5のアイテムを挿入したとしますが、そのスロットはすでに別のキーで、同じハッシュコードを持つ別のアイテムによって取得されているとします。 6と7も言われているので、スロット8にアイテムを挿入します。そのアイテムを検索すると、まずスロット5が検索されますが、そこにあるアイテムは一致しません。 hasコードが増加し、最終的には、そのアイテムはスロット8にあります。最初に空のスロットが見つかると、検索は成功しなくなります。スロット5のアイテムを取り外すと、スロット8のアイテムにアクセスできなくなります。そのため、ダミー要素をそのスロットに配置する必要があります。あなたのリンクリストのアプローチは、そのようなダミー要素を必要としません。

（tutorialspointアプローチは、ハッシュテーブルがいっぱいの場合、すべての要素を検索することを意味します。これは、未分類の配列を検索するよりも優れていません。リンクリストハッシュテーブルは一杯になりませんが、テーブル内の項目のハッシュテーブルのサイズよりもはるかに大きい、パフォーマンスが低下します。）