質問

ハッシュ法（オープンアドレス法）をC言語で実装しました。

ハッシュ表の使用率ごとにかかる計算時間を比べたいと思い、以下のような実装をしました。

しかし、登録するデータを手動で登録していかなければならないので、ハッシュ表を大きくし、データ数を1000、10000と増やしていくと登録に時間と手間がかかりすぎてしまいます。

そこで、手動ではなく自動でデータを登録するようにしたいのですが、その場合どのように記述すれば良いのでしょうか？

また、計算時間だけでなく、計算量がわかるようにするにはどのようにすれば良いのでしょうか？

ご回答頂ければ幸いです。

ソースコード

C言語
1#include <stdio.h>
2#include <time.h>
3
4/* ハッシュ表サイズの定義 */
5#define TABLE_SIZE 100
6
7/* 関数の戻り値 */
8#define SUCCESS 0
9#define FAILURE 1
10
11/* 空のバケットの表す定数 */
12#define EMPTY 0
13#define DELETED -1
14
15/* 構造体の定義 */
16typedef struct record{
17    long int tel;
18    char name[32];
19}Record;
20
21/* ハッシュ表の宣言 */
22Record Table[TABLE_SIZE];
23
24/* ハッシュ関数の定義 */
25int hash(long int key){
26    return key%TABLE_SIZE;
27}
28
29/* 再ハッシュ関数の定義 */
30int rehash(int bucket){
31    return (bucket+1)%TABLE_SIZE;
32}
33
34/* ハッシュ表へのデータ追加 */
35int add_hashtable(Record new_data)
36{
37    int bucket,k;
38    long int key,data;
39    
40    key=new_data.tel;
41    bucket=hash(key);
42    for(k=0;k<TABLE_SIZE;k++){
43        data=Table[bucket].tel;
44        if( data==EMPTY || data==DELETED){
45            Table[bucket]=new_data;
46            printf("追加しました\n");
47            return SUCCESS;
48        }
49        bucket=rehash(bucket);
50    }
51    printf("追加できませんでした");
52    return FAILURE;
53}
54 
55/* ハッシュ表の探索 */
56int search_hashtable(long int key)
57{
58    int bucket,k;
59    long int data;
60    
61    bucket=hash(key);
62    for(k=1;k<TABLE_SIZE;k++){
63        data=Table[bucket].tel;
64        if(data==key){
65            printf("%sさんの電話番号です\n",Table[bucket].name);
66            return SUCCESS;
67        }
68        if(data==EMPTY) break;
69        bucket=rehash(bucket);
70    }
71    printf("見つかりませんでした\n");
72    return FAILURE;
73}
74
75/* ハッシュ表からのデータ削除 */
76int delete_hashtable(long int key)
77{
78    int bucket,k;
79    long int data;
80    
81    bucket=hash(key);
82    for(k=0;k<TABLE_SIZE;k++){
83        data=Table[bucket].tel;
84        if(data==key){
85            Table[bucket].tel=DELETED;
86            printf("削除しました\n");
87            return SUCCESS;
88        }
89        if( data==EMPTY ) break;
90        bucket=rehash(bucket);
91    }
92    printf("見つかりませんでした\n");
93    return FAILURE;
94}
95
96/* ハッシュ法によるデータ管理プログラム */
97void main(void)
98{
99    Record new_data;
100    int i,menu,rc;
101    long int key;
102    unsigned int sec;
103    int nsec;
104    double d_sec;
105    
106    struct timespec start_time, end_time;
107    
108    for(i=0;i<TABLE_SIZE;i++)Table[i].tel=EMPTY;
109    
110    while(1){
111        printf("\n登録 1  削除 2  検索 3  表示 4\nメニュー番号:  ");
112        scanf("%d",&menu);
113        switch(menu){
114            case 1:
115                printf("\n=データ登録=\n");
116                while(1){
117                    printf("電話番号(-1で登録終了) : ");
118                    scanf("%ld",&new_data.tel);
119                    if(new_data.tel==-1) break;
120                    printf("名前: ");
121                    scanf("%s",new_data.name);
122                    rc=add_hashtable(new_data);
123                    if(rc==FAILURE) break;
124                }
125                break;
126            case 2:
127                printf("\n=データ削除=\n");
128                while(1){
129                    printf("電話番号(-1で削除終了) : ");
130                    scanf("%ld",&key);
131                    if(key==-1)break;
132                    delete_hashtable(key);
133                }
134                break;
135            case 3:
136                printf("\n=データ検索=\n");
137                while(1){
138                    printf("電話番号(-1で検索終了) : ");
139                    scanf("%ld",&key);
140                    if(key==-1)break;
141                    
142                    clock_gettime(CLOCK_REALTIME, &start_time);
143                    search_hashtable(key);
144                    clock_gettime(CLOCK_REALTIME, &end_time);
145                    sec = end_time.tv_sec - start_time.tv_sec;
146                    nsec = end_time.tv_nsec - start_time.tv_nsec;
147                    d_sec = (double)sec + (double)nsec / (1000 * 1000 * 1000);
148                    printf("time:%f\n", d_sec);
149                }
150                break;
151            case 4:
152                printf("\n=データ表示=\n");
153                for(i=0;i<TABLE_SIZE;i++){
154                    if(Table[i].tel==EMPTY || Table[i].tel==DELETED) continue;
155                    printf("%d\t%ld\t%s\n",i,Table[i].tel,Table[i].name);
156                }
157                break;
158            default:
159                return;
160        }
161    }
162    return;
163}