ハッシュ

質問

この問題の解き方を出来ればわかりやすくお願いします。
疑問:データと書いてある所に16進数の解答の答えを10進数に直していれるのでしょうか？

問題↓
表A
ーーーーーーーーーーーーーーーーー
データと格納順
7B→B5→A7→58→FE→6A→7D→E9→88
ーーーーーーーーーーーーーーーーー
ハッシュ値を f(データ)=mod(データ,8) で求めたとき最初に衝突が起こる。(上の表Aにあるデータと等しいハッシュ値になる)のはどのデータか。mod(a,b)はaをbで割った余りを表す。
a 6A　b E9　c 7D　d 88
(問題の解答はもとめておりません)

回答No.2

MrBan · ベストアンサー

16進数のまま計算してもかまいませんが、データのところに値を入れていくこと自体は合っています。
ただし、入れていくのは表A内のデータなので「回答の答え」(a～dのこと?)だけでは無理です。

考え方としては、データからハッシュ値を順次計算し、格納していくのですから、
まず表Aのデータについて、左から順にハッシュ値を算出します。
mod(7B,8)、mod(B5,8)、mod(A7,0)、…
8の剰余なのでそれぞれ0～7のハッシュ値が取れます。例えばmod(7B,8)は3です。

このように表Aのハッシュ値を順次計算していき、最初に既出のハッシュ値になったものがシノニム(衝突)です。

そのときの値が、a～dの値のどれかになります。

a～dの値は「表A内のうち、その値のどれかで衝突する」ことを示しますが、
左から順に格納するため、予め左側の値についてもハッシュ値を算出しておかないと、衝突しているかどうかは判断できません。

お礼

回答して頂きありがとうございます。
この問題の意味が分かった気がします。
これで何とかすっきりしたと思います。

回答No.3

ymmasayan

この場合衝突が起きるのは下３ビットが同じもの同士です。
２つのうち後の方が衝突したと言います。
例えば８個の座席があって８面体のさいころを振ってその番号の席につくとします。
先客が座っていると衝突です。

お礼

回答して頂きありがとうございます。
例えが良かったおかげで何とかうまくいきそうです。
例え通りにやってみたいと思います。

回答No.1

yambejp

２桁の16進数を8でわったあまりなのですから
２桁目はかならず８で割りきれますよね？
したがって１桁目の比較ですみます。
あとは対比表でもつくればよろしいのでは？

0～Fを8で割ったあまり
01234567
89ABCDEF

お礼

回答ありがとうございます！
対比表作ってやってみます。