1

一定時間内にアイテムを検索できる dotnet のデータ構造が必要です。これは、データ構造が内部でインデックス作成を実装する必要があることを意味します。辞書は、この目的または他の目的に役立ちますか?

4

1 に答える 1

2

はい、Dictionary<> (古いバージョンの .NET を使用している場合は Hashtable) を使用します。ディクショナリに詰め込むオブジェクトのハッシュ値が適切であることを確認してください (ディクショナリでキーとして使用しているオブジェクトの GetHashCode() と Equals() をオーバーライドすることを検討してください)。データ オブジェクトのハッシュ コードが不十分な場合、パフォーマンスが低下し始めます。はい、あなたの質問に答えるために、ハッシュテーブル/辞書のルックアップは比較的一定の時間である必要があります（本では一般にO（1）であると言われていますが、それは議論の余地があります）。ルックアップのパフォーマンスは、多くの要因によって決まります。

  1. ハッシュ関数（分布を決定）
  2. テーブルは衝突をどのように処理しますか? プロービング？バケツ？(ほとんどの実装ではバケットを使用します)。
  3. テーブルのサイズは変更できますか? どのようにサイズ変更されますか? 少しずつ？2の累乗？素数？
  4. 等...
于 2009-05-21T05:26:04.720 に答える