アルゴリズムとデータ構造
補足資料14-3
「オープンアドレッシング法」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
内部ハッシュ法
サンプルプログラム：openaddressing.c
• オープンアドレッシング法／内部ハッシュ法
• 指定されたIDに対してハッシュ値を作成
• アイテムはハッシュ表内に格納される（表の大きさに制限がある）
• ハッシュ値から、ハッシュ表の格納位置（アドレス）を特定する
• 記録できる量に制限があるときに有効
• 挿入：ハッシュ値衝突の際は再ハッシュによって別の位置を探す
• 削除：ハッシュ値、再ハッシュ値からハッシュ表のアドレスを特定し削除す
る→次回の探索のために「未使用」と「削除済」の区別がある
• 探索：ハッシュ値の特定はO(1)だが、再ハッシュのため最悪時O(N)（全バ
ケットを探索）を要する
– 表の埋まり具合にゆとりを持たせると、O(1)に近くなる
オープンアドレッシング法
開始前
struct record x
ename:
jname:
addr :
struct record dummy
←x: ファイルから取り出したレコード1件を保持
←dummy: ダミーのデータ（重複キーを持つ）
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item hashtable[B]
hashtable[ 0]
hashtable[ 4]
hashtable[ 1]
hashtable[ 5]
hashtable[ 2]
hashtable[ 6]
hashtable[ 3]
hashtable[ 7]
hashtable[ 8]
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
hashtable[11]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[12]
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
↑ハッシュ表： アイテムの実体を
B個格納可能
struct record x
ename:
jname:
addr :
オープンアドレッシング法
ハッシュ表初期化
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: ***EMPTY***
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: ***EMPTY***
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
オープンアドレッシング法
レコード1件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: ***EMPTY***
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: ***EMPTY***
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード1件目ハッシュ関数計算
struct record x
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: ***EMPTY***
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: ***EMPTY***
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード1件目ハッシュ表へ登録
struct record x
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: ***EMPTY***
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
オープンアドレッシング法
レコード2件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: ***EMPTY***
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード2件目ハッシュ関数計算
struct record x
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hash(“Kanagawa Hanako”) = 4
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: ***EMPTY***
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード2件目ハッシュ表へ登録
struct record x
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hash(“Kanagawa Hanako”) = 4
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
オープンアドレッシング法
レコード3件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード3件目ハッシュ関数計算
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hash(“Hato Saburo”) = 8 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
オープンアドレッシング法
レコード3件目ハッシュ関数再計算
hash(“Hato Saburo”) = 8 → すでに埋まっている（衝突）
rehash(“Hato Saburo”, 1) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード3件目ハッシュ表へ登録
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hash(“Hato Saburo”) = 8
rehash(“Hato Saburo”, 1) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
オープンアドレッシング法
レコード4件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード4件目ハッシュ関数計算
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hash(“Hojo Umeko”) = 9 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
オープンアドレッシング法
レコード4件目ハッシュ関数再計算
hash(“Hojo Umeko”) = 9 → すでに埋まっている（衝突）
rehash(“Hojo Umeko”, 1) = 10
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: ***EMPTY***
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード4件目ハッシュ表へ登録
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hash(“Hojo Umeko”) = 9 → すでに埋まっている（衝突）
rehash(“Hojo Umeko”, 1) = 10
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
オープンアドレッシング法
レコード5件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード5件目ハッシュ関数計算
struct record x
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hash(“Ashigara Kintaro”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: ***EMPTY***
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード5件目ハッシュ表へ登録
struct record x
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hash(“Ashigara Kintaro”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
オープンアドレッシング法
レコード6件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード6件目ハッシュ関数計算
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hash(“Ueno Ranran”) = 9 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
オープンアドレッシング法
レコード6件目ハッシュ関数再計算
hash(“Ueno Ranran”) = 9 → すでに埋まっている（衝突）
rehash(“Ueno Ranran”, 1) = 10 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
オープンアドレッシング法
レコード6件目ハッシュ関数再々計算
struct record dummy
hash(“Ueno Ranran”) = 9 → すでに埋まっている（衝突）
rehash(“Ueno Ranran”, 1) = 10 → すでに埋まっている（衝突）
rehash(“Ueno Ranran”, 2) = 11
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード6件目ハッシュ表へ登録
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
struct record dummy
hash(“Ueno Ranran”) = 9 → すでに埋まっている（衝突）
rehash(“Ueno Ranran”, 1) = 10 → すでに埋まっている（衝突）
rehash(“Ueno Ranran”, 2) = 11
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: ***EMPTY***
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
レコード7件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード7件目ハッシュ関数計算
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
hash(“Mitsuki Mausu”) = 10 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: ***EMPTY***
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
レコード7件目ハッシュ関数再計算
hash(“Mitsuki Mausu”) = 10 → すでに埋まっている（衝突）
rehash(“Mitsuki Mausu”, 1) = 11 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: ***EMPTY***
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
レコード7件目ハッシュ関数再々計算
struct record dummy
hash(“Mitsuki Mausu”) = 10 → すでに埋まっている（衝突）
rehash(“Mitsuki Mausu”, 1) = 11 → すでに埋まっている（衝突）
rehash(“Mitsuki Mausu”, 2) = 12
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: ***EMPTY***
オープンアドレッシング法
レコード7件目ハッシュ表へ登録
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record dummy
hash(“Mitsuki Mausu”) = 10 → すでに埋まっている（衝突）
rehash(“Mitsuki Mausu”, 1) = 11 → すでに埋まっている（衝突）
rehash(“Mitsuki Mausu”, 2) = 12
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
オープンアドレッシング法
レコード8件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
レコード8件目ハッシュ関数計算
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hash(“Nobi Toraemon”) = 0 → すでに埋まっている（衝突）
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
レコード8件目ハッシュ関数計算
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hash(“Nobi Toraemon”) = 0 → すでに埋まっている（衝突）
rehash(“Nobi Toraemon”, 1) = 1
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: ***EMPTY***
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
レコード8件目ハッシュ表へ登録
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hash(“Nobi Toraemon”) = 0 → すでに埋まっている（衝突）
rehash(“Nobi Toraemon”, 1) = 1
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
登録後
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
↑ハッシュ表の状態が印刷される
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
重複データ登録の試み
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
重複データ登録の試み
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
“Yokohama Kunihiro” は、
すでに登録されているので登録拒否
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索1
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8
→ 該当せず
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索1
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索1
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Hato Saburo”) = 8 → 該当せず
：見つかるか、または、EMPTYか1周する（存在しないことを確認する）まで再ハッシュ
rehash(“Hato Saburo”) = 9 → 発見！
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
found <(8) Hato Saburo 鳩三郎 鎌倉市小町>
再ハッシュにより発見
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索2
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8 → 発見
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
found <(8) Yokohama Kunihiro 横浜国大
1度の探索で発見
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
横浜市保土ヶ谷区常盤台> addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除1
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除1: 探索
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8
→ 該当せず
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除1: 探索
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除1: 探索
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Hato Saburo”) = 8 → 該当せず
：見つかるか、または、EMPTYか1周する（存在しないことを確認する）まで再ハッシュ
rehash(“Hato Saburo”, 1) = 9 → 発見！
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: Hato
***EMPTY***
id:
Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除1: idに「削除済」を記録
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Hato Saburo”) = 8 → 該当せず
：見つかるか、または、EMPTYか1周する（存在しないことを確認する）まで再ハッシュ
rehash(“Hato Saburo”, 1) = 9 → 発見！
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
•EMPTY（空）ではなくDELETED（削除済）と記録するのは、
data:
別の探索の際に、rehashする必要があるから
ename: Mitsuki Mausu
jname: 三月磨臼
•DELETEDの箇所の扱いは次のとおり
•探索時： 再ハッシュして続きを探索すべき（EMPTYと異なる） addr : 浦安市舞浜
•挿入時： 挿入可能（EMPTYと同じ扱い）
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除2
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除2: 探索
struct record x
ename:
jname:
addr :
hash(“Ueno Ranran”) = 9 → ここは「削除済」: 該当せず、かつ、続きにある可能性
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除2: 探索（再ハッシュ）
struct record x
ename:
jname:
addr :
hash(“Ueno Ranran”) = 9 → ここは「削除済」: 該当せず、かつ、続きにある可能性
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除2: 探索（再ハッシュ）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Ueno Ranran”) = 9 → ここは「削除済」: 該当せず、かつ、続きにある可能性
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Ueno Ranran”, 1) = 10 → 該当せず
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除2: 探索（再ハッシュ）
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Ueno Ranran”) = 9 → ここは「削除済」: 該当せず、かつ、続きにある可能性
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Ueno Ranran”, 1) = 10 → 該当せず
rehash(“Ueno Ranran”, 2) = 11 → 発見！
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: Ueno
***EMPTY***
id:
Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除2: idに「削除済」を記録
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Ueno Ranran”) = 9 → ここは「削除済」: 該当せず、かつ、続きにある可能性
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Ueno Ranran”, 1) = 10 → 該当せず
rehash(“Ueno Ranran”, 2) = 11 → 発見！
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除3
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除3: 探索
struct record x
ename:
jname:
addr :
hash(“Nobi Toraemon”) = 0 →
該当せず
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除3: 探索（再ハッシュ）
struct record x
ename:
jname:
addr :
hash(“Nobi Toraemon”) = 0 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除3: 探索（再ハッシュ）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nobi Toraemon”) = 0 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nobi Toraemon”, 1) = 1 → 発見！
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: Nobi
***EMPTY***
id:
Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除3: idに「削除済」を記録
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nobi Toraemon”) = 0 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nobi Toraemon”, 1) = 1 → 発見！
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除4
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索
struct record x
ename:
jname:
addr :
hash(“Nanashi Gonbei”) = 8 → 該当せず
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索
struct record x
ename:
jname:
addr :
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ1回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 1) = 9 → ここは「削除済」: 該当せず、かつ、続きにある可能性
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ2回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 2) = 10 → 該当せず
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ3回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 3) = 11 → ここは「削除済」: 該当せず、かつ、続きにある可能性
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ4回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 4) = 12 → 該当せず
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ5回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 5) = 0 → 該当せず
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ6回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 6) = 1 → ここは「削除済」: 該当せず、かつ、続きにある可能性
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除4: 探索（再ハッシュ7回目）
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Nanashi Gonbei”) = 8 → 該当せず
：見つかるか、または、1周するかEMPTY（存在しないことを確認する）まで再ハッシュ
rehash(“Nanashi Gonbei”, 7) = 2 → ここは「空」: 該当せず、かつ、続きにもないことが確定
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
該当なし！
1回の探索＋7回の再ハッシュ探索を費やした！
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除5
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
削除5: 探索
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8 → 発見！
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
***EMPTY***
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
あくまでキーが一致するかどうかが条件なので、
削除されるアイテムはキーだけが一致し、
それ以外はdummyの内容と異なることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除5: 探索idに「削除済」を記録
hash(“Yokohama Kunihiro”) = 8 → 発見！
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
あくまでキーが一致するかどうかが条件なので、
削除されるアイテムはキーだけが一致し、
それ以外はdummyの内容と異なることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
削除後
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8 → DELETEDなので、続きを探索
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8 → DELETEDなので、続きを探索
rehash(“Hato Saburo”, 1) = 9 → DELETEDなので、続きを探索
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
hash(“Hato Saburo”) = 8 → DELETEDなので、続きを探索
rehash(“Hato Saburo”, 1) = 9 → DELETEDなので、続きを探索
rehash(“Hato Saburo”, 2) = 10 → キー不一致なので、続きを探索
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Hato Saburo”) =
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
8 →
1) =
2) =
3) =
DELETEDなので、続きを探索
9 → DELETEDなので、続きを探索
10 → キー不一致なので、続きを探索
11 → DELETEDなので、続きを探索
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Hato Saburo”) =
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
8 →
1) =
2) =
3) =
DELETEDなので、続きを探索
9 → DELETEDなので、続きを探索
10 → キー不一致なので、続きを探索
11 → DELETEDなので、続きを探索
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
rehash(“Hato Saburo”, 4) = 12 →
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
キー不一致なので、続きを探索 data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Hato Saburo”) =
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
8 →
1) =
2) =
3) =
DELETEDなので、続きを探索
9 → DELETEDなので、続きを探索
10 → キー不一致なので、続きを探索
11 → DELETEDなので、続きを探索
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
rehash(“Hato Saburo”, 4) =
rehash(“Hato Saburo”, 5) =
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
12 → キー不一致なので、続きを探索 data:
0 → キー不一致なので、続きを探索 ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Hato Saburo”) =
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
8 →
1) =
2) =
3) =
DELETEDなので、続きを探索
9 → DELETEDなので、続きを探索
10 → キー不一致なので、続きを探索
11 → DELETEDなので、続きを探索
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
rehash(“Hato Saburo”, 4) =
rehash(“Hato Saburo”, 5) =
rehash(“Hato Saburo”, 6) =
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
12 → キー不一致なので、続きを探索 data:
0 → キー不一致なので、続きを探索 ename: Mitsuki Mausu
jname: 三月磨臼
1 → DELETEDなので、続きを探索
addr : 浦安市舞浜
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Hato Saburo”) =
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
rehash(“Hato Saburo”,
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
8 →
1) =
2) =
3) =
DELETEDなので、続きを探索
9 → DELETEDなので、続きを探索
10 → キー不一致なので、続きを探索
11 → DELETEDなので、続きを探索
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
12 → キー不一致なので、続きを探索 data:
0 → キー不一致なので、続きを探索 ename: Mitsuki Mausu
jname: 三月磨臼
1 → DELETEDなので、続きを探索
addr : 浦安市舞浜
rehash(“Hato Saburo”, 4) =
rehash(“Hato Saburo”, 5) =
rehash(“Hato Saburo”, 6) =
rehash(“Hato Saburo”, 7) = 2 → EMPTYなので、ないことを確認
→ “Hato Saburo”をidとするアイテムは存在しない！
オープンアドレッシング法
探索
struct record x
ename:
jname:
addr :
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hash(“Yokohama Kunihiro”) =
rehash(“Yokohama Kunihiro”,
rehash(“Yokohama Kunihiro”,
rehash(“Yokohama Kunihiro”,
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
8 →
1) =
2) =
3) =
DELETEDなので、続きを探索
9 → DELETEDなので、続きを探索
10 → キー不一致なので、続きを探索
11 → DELETEDなので、続きを探索
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
12 → キー不一致なので、続きを探索
ename: Mitsuki Mausu
0 → キー不一致なので、続きを探索
1 → DELETEDなので、続きを探索jname: 三月磨臼
addr : 浦安市舞浜
rehash(“Yokohama Kunihiro”, 4) =
rehash(“Yokohama Kunihiro”, 5) =
rehash(“Yokohama Kunihiro”, 6) =
rehash(“Yokohama Kunihiro”, 7) = 2 → EMPTYなので、ないことを確認
→ “Yokohama Kunihiro”をidとするアイテムは存在しない！
オープンアドレッシング法
挿入
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
今回挿入するレコードの内容は、
dummyに書かれている内容であることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
挿入
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8 → DELETEDなので、挿入可能
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: **DELETED**
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
今回挿入するレコードの内容は、
dummyに書かれている内容であることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
挿入
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8 → DELETEDなので、挿入可能
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
**DELETED**
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
今回挿入するレコードの内容は、
dummyに書かれている内容であることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
挿入後
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
**DELETED**
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
今回挿入するレコードの内容は、
dummyに書かれている内容であることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
オープンアドレッシング法
探索1
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
**DELETED**
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
found <(8) Yokohama Kunihiro 横浜邦博 横浜市中区日本大通>
今度の結果は、先ほど新たに挿入されたデータであることに注意
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
struct record x
ename:
jname:
addr :
オープンアドレッシング法
終了直前の状態
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item hashtable[B]
hashtable[ 0]
id: Ashigara
***EMPTY***
id:
Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hashtable[ 4]
id: Kanagawa
***EMPTY***
id:
Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 1]
id: **DELETED**
hashtable[ 5]
id: ***EMPTY***
hashtable[ 2]
id: ***EMPTY***
hashtable[ 6]
id: ***EMPTY***
hashtable[ 3]
id: ***EMPTY***
hashtable[ 7]
id: ***EMPTY***
hashtable[ 8]
id: Yokohama
**DELETED**
id:
Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
hashtable[ 9]
id: **DELETED**
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[10]
id: Hojo
***EMPTY***
id:
Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[11]
id: **DELETED**
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
まとめ
•動的データ管理： 探索、挿入、削除 → 記録できる量に制限あり
• ハッシュ表の探索開始箇所を見つけるには、O(1)：
登録済みのデータ件数には依存しない
• ハッシュ表の要素リストの中からアイテムを見つけるには、
再ハッシュ回数に依存 O( N ) （最悪時）
hashtable[12]
id: Mitsuki
***EMPTY***
id:
Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜

9章 家族周期論的アプローチ

クラブ規程 - 山旅クラブ ティンバーライン

第8回入出力制御

WORKS2011 2014 - jamrucrew inc.

AR-F series

シミュレーション工学 第3回 ANSYSによる演習

無担保貸出の導入が企業の資金調達と パフォーマンスに与える効果の検証

SUBACASANARE S.A. 26/mar/2015 FECHA CIUDAD 00877 FERIA

今日の資料スライドは、脇田先生作成のスライドを ベースに用いています。

DRYPRO Vstage MODEL 793