2017年度 第2回 ハッシュ法Ⅱ 演習課題


同族連鎖法におけるハッシュ表生成
前半グループ(整数集合)
番号  除数  CONSL
  0:  999983  19
  1:  999983  23
  2:  999979  29
  3:  999979  31
  4:  999961  37
  5:  999961  41
  6:  999959  43
  7:  999959  47
  8:  999953  53
  9:  999953  59

二分探索法
要素数 総比較回数
1U 1895151 (± 1)
2U 3790293 (± 1)
3U 5685436 (± 1)
4U 7580577 (± 1)
5U 9475713 (± 1)
6U 11370864 (± 1)
7U 13266006 (± 1)
8U 15161149 (± 1)
9U 17056290 (± 1)
10U 18951445 (± 1)


番号:0 除数:999983 CONSL:19
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 10107 (± 1) 210107 (± 1)
3U 29311 (± 1) 330374 (± 1)
4U 56212 (± 1) 460227 (± 1)
5U 90692 (± 1) 600282 (± 1)
6U 131643 (± 1)750215 (± 1)
7U 178406 (± 1)910013 (± 1)
8U 230601 (± 1)1080233 (± 1)
9U 287513 (± 1)1260254 (± 1)
10U 348630 (± 1)1449842 (± 1)


番号:1 除数:999983 CONSL:23
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 10107 (± 1) 210107 (± 1)
3U 29311 (± 1) 330374 (± 1)
4U 56212 (± 1) 460227 (± 1)
5U 90692 (± 1) 600282 (± 1)
6U 131643 (± 1)750215 (± 1)
7U 178406 (± 1)910013 (± 1)
8U 230601 (± 1)1080233 (± 1)
9U 287513 (± 1)1260254 (± 1)
10U 348630 (± 1)1449842 (± 1)


番号:2 除数:999979 CONSL:29
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 10031 (± 1) 210031 (± 1)
3U 29129 (± 1) 330171 (± 1)
4U 56185 (± 1) 460132 (± 1)
5U 90610 (± 1) 600099 (± 1)
6U 131384 (± 1)749737 (± 1)
7U 178230 (± 1)909877 (± 1)
8U 230479 (± 1)1079909 (± 1)
9U 287725 (± 1)1260306 (± 1)
10U 348855 (± 1)1450031 (± 1)


番号:3 除数:999979 CONSL:31
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 10031 (± 1) 210031 (± 1)
3U 29129 (± 1) 330171 (± 1)
4U 56185 (± 1) 460132 (± 1)
5U 90610 (± 1) 600099 (± 1)
6U 131384 (± 1)749737 (± 1)
7U 178230 (± 1)909877 (± 1)
8U 230479 (± 1)1079909 (± 1)
9U 287725 (± 1)1260306 (± 1)
10U 348855 (± 1)1450031 (± 1)


番号:4 除数:999961 CONSL:37
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 9966 (± 1) 209966 (± 1)
3U 29066 (± 1) 330064 (± 1)
4U 56111 (± 1) 459979 (± 1)
5U 90272 (± 1) 599627 (± 1)
6U 131341 (± 1)749724 (± 1)
7U 178267 (± 1)909847 (± 1)
8U 230170 (± 1)1079588 (± 1)
9U 287064 (± 1)1259222 (± 1)
10U 348445 (± 1)1449288 (± 1)


番号:5 除数:999961 CONSL:41
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 9966 (± 1) 209966 (± 1)
3U 29066 (± 1) 330064 (± 1)
4U 56111 (± 1) 459979 (± 1)
5U 90272 (± 1) 599627 (± 1)
6U 131341 (± 1)749724 (± 1)
7U 178267 (± 1)909847 (± 1)
8U 230170 (± 1)1079588 (± 1)
9U 287064 (± 1)1259222 (± 1)
10U 348445 (± 1)1449288 (± 1)


番号:6 除数:999959 CONSL:43
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 10020 (± 1) 210020 (± 1)
3U 29021 (± 1) 330020 (± 1)
4U 56078 (± 1) 459917 (± 1)
5U 90616 (± 1) 600021 (± 1)
6U 131382 (± 1)749749 (± 1)
7U 178077 (± 1)909451 (± 1)
8U 230162 (± 1)1079117 (± 1)
9U 287124 (± 1)1259108 (± 1)
10U 348231 (± 1)1448806 (± 1)


番号:7 除数:999959 CONSL:47
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 10020 (± 1) 210020 (± 1)
3U 29021 (± 1) 330020 (± 1)
4U 56078 (± 1) 459917 (± 1)
5U 90616 (± 1) 600021 (± 1)
6U 131382 (± 1)749749 (± 1)
7U 178077 (± 1)909451 (± 1)
8U 230162 (± 1)1079117 (± 1)
9U 287124 (± 1)1259108 (± 1)
10U 348231 (± 1)1448806 (± 1)


番号:8 除数:999953 CONSL:53
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 9873 (± 1) 209873 (± 1)
3U 29057 (± 1) 330090 (± 1)
4U 56187 (± 1) 460061 (± 1)
5U 90417 (± 1) 600012 (± 1)
6U 131073 (± 1)749538 (± 1)
7U 178099 (± 1)909715 (± 1)
8U 229892 (± 1)1079078 (± 1)
9U 286609 (± 1)1258369 (± 1)
10U 347888 (± 1)1448315 (± 1)


番号:9 除数:999953 CONSL:59
要素数 衝突キー総数 総探査回数
1U 0 (+ 1) 100000 (± 1)
2U 9873 (± 1) 209873 (± 1)
3U 29057 (± 1) 330090 (± 1)
4U 56187 (± 1) 460061 (± 1)
5U 90417 (± 1) 600012 (± 1)
6U 131073 (± 1)749538 (± 1)
7U 178099 (± 1)909715 (± 1)
8U 229892 (± 1)1079078 (± 1)
9U 286609 (± 1)1258369 (± 1)
10U 347888 (± 1)1448315 (± 1)