アルゴリズムとデータ構造 補足資料 14-2
「ダイレクトチェイニング法」
外部ハッシュ法
サンプルプログラム： directchaining.c
• ダイレクトチェイニング法／外部ハッシュ法
• 指定された ID に対してハッシュ値を作成
• アイテムは要素リストに格納される
• ハッシュ表はリスト先頭を保持
• 格納できる長さに制限がない
• 挿入：ハッシュ値衝突の際は要素リストの先頭にアイテムを追加する
削除：ハッシュ値からハッシュ表を特定し、要素リストから削除する
ダイレクトチェイニング法 開始前
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1]
hashtable[ 2]
hashtable[ 3]
hashtable[ 4]
hashtable[ 5]
hashtable[ 6]
hashtable[ 7]
hashtable[ 8]
hashtable[ 9]
hashtable[10]
hashtable[11]
jname:
ename:
addr :
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
←x: ファイルから取り出したレコード 1 件を保持
←dummy: ダミーのデータ（重複キーを持つ）
ダイレクトチェイニング法 ハッシュ表初期化
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname:
ename:
addr :
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
ダイレクトチェイニング法 レコード 1 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
ダイレクトチェイニング法
レコード 1 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Yokohama Kunihiro”) = 8
ダイレクトチェイニング法
レコード 1 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Yokohama Kunihiro”) = 8
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL
ダイレクトチェイニング法 レコード 2 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname: 神奈川花子
ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL
ダイレクトチェイニング法
レコード 2 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Kanagawa Hanako”) = 4
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL
ダイレクトチェイニング法
レコード 2 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL
hash(“Kanagawa Hanako”) = 4
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
ダイレクトチェイニング法 レコード 3 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname: 鳩三郎
ename: Hato Saburo addr : 鎌倉市小町
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
ダイレクトチェイニング法
レコード 3 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Hato Saburo”) = 8
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL jname: 鳩三郎
ename: Hato Saburo addr : 鎌倉市小町
ダイレクトチェイニング法
レコード 3 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
hash(“Hato Saburo”) = 8
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
ダイレクトチェイニング法 レコード 4 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL jname: 北条梅子
ename: Hojo Umeko addr : 小田原市城山
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
ダイレクトチェイニング法
レコード 4 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Hojo Umeko”) = 9
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山
ダイレクトチェイニング法
レコード 4 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL
hash(“Hojo Umeko”) = 9
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山
ダイレクトチェイニング法 レコード 5 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL
ダイレクトチェイニング法
レコード 5 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0] NULL hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Ashigara Kintaro”) = 0
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山
ダイレクトチェイニング法
レコード 5 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL
hash(“Ashigara Kintaro”) = 0
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山
data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL
ダイレクトチェイニング法 レコード 6 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL jname: 上野蘭々
ename: Ueno Ranran addr : 台東区上野公園
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL
ダイレクトチェイニング法
レコード 6 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Ueno Ranran”) = 9
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL jname: 上野蘭々
ename: Ueno Ranran addr : 台東区上野公園
ダイレクトチェイニング法
レコード 6 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL
hash(“Ueno Ranran”) = 9
jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL data:
jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9
next:
ダイレクトチェイニング法 レコード 7 件目取り出し
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL jname: 三月磨臼
ename: Mitsuki Mausu addr : 浦安市舞浜
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL data:
jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9
next:
ダイレクトチェイニング法
レコード 7 件目ハッシュ関数計算
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10] NULL hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
hash(“Mitsuki Mausu”) = 10
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL data:
jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9
next:
jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜
ダイレクトチェイニング法
レコード 7 件目ハッシュ表へ登録
/* ハッシュ表初期化 */
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);
hashtable[ 0]
hashtable[ 1] NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4]
hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8]
hashtable[ 9]
hashtable[10]
hashtable[11] NULL
struct record x
jname: 横浜邦博
ename: Yokohama Kunihiro addr : 横浜市中区日本大通
struct record dummy
struct item *hashtable[B]
data:
jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上 町
id: Kanagawa Hanako hash:
4
next: NULL
data:
jname: 横浜国大
ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8
next: NULL data:
jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町
id: Hato Saburo hash: 8
next:
data:
jname: 足柄金太郎
ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0
next: NULL
data:
jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9
next: NULL data:
jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9
next:
hash(“Mitsuki Mausu”) = 10
jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜
