計算量で学んだこと

大学院の課題で面白い問題があったので紹介

ハッシュ構造は原則参照、挿入、削除の計算量はO(1)
しかし、O(1)が成立しないときそれはどんな条件だろうか

ハッシュ構造はO(1)で暗記していたが、成立しない時があるのか・・・よく考えていなかったなと反省した。

解法のヒントは下記に残しておきます

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。

ハッシュ衝突の対策　より引用

ハッシュ衝突の対策 – 電子情報工学科

あと、先生の課題の意図とは外れるかもしれないが、そもそもどうやってハッシュ値を計算しているのかという視点から考える事もできた

ハッシュのキーは，たいていの場合で，ごく小さな文字列変数に格納されます。その長さは，取り扱うデータ量に比較すればとても短いはずです。たいていは文字列変数は固定長です。つまり，文字列長には最大値があります。すると，ハッシュ関数の計算実行量は，平均すればある定数，キーを格納する文字列の最大サイズ程度です。ですから計算量が一定，O (1)であると言えるのです。

はじめMath! Javaでコンピュータ数学
第76回　計算量の数学　計算量と実際のコード　その2　より引用

第76回　計算量の数学　計算量と実際のコード　その2