問題タブ [constant-time]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
26 問題
0
投票する
1
に答える
180
参照
python - Python の hash() 関数が可変長の文字列を操作するのに一定の時間がかかるのはなぜですか?
可変長文字列に対する hash() 操作を含むプログラムの実行時から、異なる長さの文字列に対する hash() 関数の操作には一定の時間がかかる可能性があると感じました。私の仮定を検証するために、次の戦略を立てました-
- 長さ k の文字列を作成する
- 文字列をハッシュし、hash() 操作時間 t を記録します
- これは、0 から 100,00 まで変化する k に対して繰り返され、文字列の長さ k と時間 t のプロットが生成されます。
したがって、文字列を操作するときに hash() 関数が一定時間操作であるという私の推測が正しい場合、素人の言葉でなぜそうなのか説明していただけますか? ソースコードへの参照ではなく、概念的または理論的な説明が望ましいでしょう-文字の長さに関係なく、大きな文字列でも瞬時にハッシュを生成する方法について。
以下は、上記の戦略のコード実装です -
以下は、生成されたプロットです -
