1

私は2つのリストを持っています。2つの中で最小公倍数を見つけたい。重複が許されないので、HashSetを使うことを考えました。両方のリスト要素を追加しながら、共通の番号を見つけることができます。そして、HashSetはconstant time挿入のみを行います。これO(n)により、2つの最小公倍数を見つけることができます。しかし、HashSetはどのようnに要素を挿入できconstant timeますか？この場合、最後の要素を追加するにはO(n)時間がかかります。これは、適切なバケットを見つけるために、最悪の場合、ハッシュコードをn個のバケットと比較する必要があるためです。これを修正して、よろしくお願いします。

4

3 に答える 3

1

アルゴリズムは非常に単純なようです。

  1. HashSetlistの要素を含むを構築しますA。
  2. minのような大きなものに初期化しますInteger.MAX_VALUE。
  3. の各要素についてB、それがにあるかどうかをテストしHashSetます。そうであり、それが、未満の場合はmin、を更新しminます。

いずれにせよ、ハッシュアルゴリズムは、多かれ少なかれ、ハッシュが実際には優れたハッシュ関数であると常に想定しており、O（n）の最悪の場合について心配する必要はありません。

于 2012-07-11T13:37:18.397 に答える
0

バケットの検索は一定時間です。これは、指定されたオブジェクトのハッシュ値にのみ依存し、既存のオブジェクトには依存しません。

于 2012-07-11T13:36:23.673 に答える
0

答えは、アルゴリズムの本（Corman、Knuthなど）で見つけることができます。間もなく：bucketIndex = toPositiveInteger（hashcode（））％buckets.length

于 2012-07-11T13:36:46.977 に答える