2のn乗+1

質問

nビットのハッシュ関数の出力は0から2のn乗の、合計すると2のn乗+1のパターンがあるってことで合ってますか？
それとも0から2のn乗-1で、合計2のn乗パターンですか？
もしくは0はなくて1から2のn乗までですか？
実際の出力をみると0000……FA16みたいなケースもあるので、そうすると全部0という出力も有り得るのですか？
また最大値はn+1ビットも有り得るのですか？最大桁が1で残りが全て0とすると、2のn乗は2進数だと最大桁に1が来て、残りが全部0ですがその0の数は、n個になると思いますが、そうすると何々ビットのハッシュ関数といいつつ、最大値でみるとビット数は2のn乗+1となりますが、認識正しいでしょうか？

回答No.1

kmee

nビットで表現できるのは、最大2のn乗通りです。
2のn乗+1通りのパターンを表現するには、最低(n+1)ビット必要です。

例えば、 n=2で考えてください。
00
01
10
11
の4通りしかありません。
この4つで0～4の5通りをどうやって表現したらよいのでしょう?

ですから

> 合計すると2のn乗+1のパターンがある
「出力nビット」の場合は有り得ません。
関数内ではnビット超で計算している可能性はありますが、出力nビットなら、取り得る値は最大2のn乗通りです。

> 1から2のn乗までですか？

こちらは、最大2のn乗通りなので、nビットで表現できます。
ただし、一般的な10進⇔2進変換では対応できないので、工夫が必要です。
例えば、 n=2の1～4を対応させる場合。
00=1
01=2
10=3
11=4
と割り当てる、という方法が考えられます。
# 全部でnPn通りの割り当て方があります。

ですが、ハッシュで大切なのは「同じか、違うか」であって、具体的な値ではありません。
こんな面倒な割り当てをするより、素直に0～2のn乗-1を使った方が便利です。

> 全部0という出力も有り得るのですか？

ハッシュ関数の作り方次第です。
・0を使わなければならない(2のn乗通り全てが出力されなればならない)
・0を使ってはならない(2のn乗通り全てが出力されてはならない)
いずれの規則もありません。

> 最大桁が1で残りが全て0とする
>その0の数は、n個になる

最大桁の「1」用の1桁 + 0のn桁 = n+1桁です。
nビットで 「最大桁が1で残りが全て0とする」となると
最大桁の「1」用の1桁 + 0の(n-1)桁 = n桁
です。

お礼

何々ビットのハッシュ関数では、
2のn乗通りの区別が出来るということ、
0から2のn乗-1か、1から2のn乗かは、そのハッシュ関数の作り次第ということが理解できました。
回答ありがとうございました。

補足

先にお礼を書いてしまって、誤記してしまったので修正させてください。
>何々ビットのハッシュ関数では、
nビットのハッシュ関数では、
でした。