計算速度はどれくらいですか？

-1

O（1）かO（n）かその中間にあるのですか？非常に大きなオブジェクトと小さなオブジェクトのハッシュを計算することに不利な点はありませんか？それが問題なら、私はPythonを使用しています。計算速度はどれくらいですか？

2017-06-16 Vic

ハッシュ関数の実装によって異なります。 – zerocool

1つのアドオン：大きいオブジェクトと小さいオブジェクトの衝突確率が高くなっていますか？ – Vic

まあ、私の応答は同じですが、衝突はアルゴリズムに依存しています。あなたは100文字の長さの文字列を、もう1文字の長さの文字列を持つことができます。あなたのハッシュ関数が文字列の最初の文字だけを考慮に入れると、たくさんの衝突が起こります。 – zerocool

一般に、ハッシュを計算することは、「小さい」アイテムの場合はO（1）、「大きい」アイテムの場合はO（N）（「N」はアイテムのキーのサイズを表します）になります。小と大の間の正確な分割線は変化するが、通常、レジスタのサイズの一般的な近傍（例えば、32ビットマシンでは32ビット、64ビットマシンでは64ビット）のどこかにある。これは、入力の種類にも依存します。たとえば、レジスタのサイズの整数型は、すべて複雑な定数でハッシュしますが、バイト単位のサイズに比例する文字列は、1文字になります（つまり、2文字1文字列の約2倍の時間を要する文字列）。

ハッシュを計算したら、ハッシュテーブルにアクセスするには一定の複雑さが予想されますが、最悪の場合はO（N）と同じくらい悪い可能性があります（ただし、これは異なる "N"個々のキーのサイズではなくテーブルに挿入されます）。

出典

2017-06-16 22:25:13

漸近的な複雑さは、入力サイズが小さくても実行時間を議論するのに最適なツールではない可能性があります。また、N = 1からO（N/32）やO（N/64）（= O（N））のようなものだとは言えませんか？おそらくもっと重要なのは、複雑さは、実際にハッシュをどのように計算するかに完全に依存するということです。ハッシュを計算するためにバイト単位でO（1）の作業しかできないというルールがあるとは思いません。 – Dukeling

ありがとうございます。やや関連したメモでは、これは1文字の文字列が64ビットを占め、2文字の文字列が128ビットを占めることを意味しますか？（64ビットマシンの場合） – Vic

@Vic：いいえ - 通常、文字は1〜4バイトのようなものを占有しますが、それより大きいものは非常にまれです。 –

ほとんどの場合、ハッシュはO（1）のアクセスで計算されます。しかし、すべての値が同じハッシュを持つ本当に悪いハッシュであれば、それはO（n）最悪のケースになります。

ハッシュに関連付けられているオブジェクトが増えるほど、より多くの衝突に相当します。

出典

2017-06-16 22:24:23

本当の答えはそれに依存します。あなたが興味を持っているハッシュ関数を指定していません。SHA256のような暗号ハッシュについて話すとき、複雑さはO（n）です。電話番号の最後の2桁を取るハッシュ関数について話すと、O（1）になります。ハッシュテーブルで使用されるハッシュ関数は速度が最適化され、O（1）に近い傾向があります。

ハッシュテーブルの詳細については、Time Complexityのpython wikiのこのページを参照してください。

出典

2017-06-18 19:33:49

計算速度はどれくらいですか？

答えて

関連する問題