スパース配列の実装を探していると思いますが、これはメモリ使用量の点で効率的である必要があり、実装が利用できるデータの特徴の 1 つは、値がインデックスiが存在する場合、インデックスi-1とi+1にも値が存在する可能性が高く、同様に、 の値に値が存在しない場合は、値iが存在i-1しi+1ない可能性があります。
私はJavaで作業していますが、これが違いを生む場合は、インデックスタイプをlongより一般的な ではなく にする必要があります。int保存する必要があるオブジェクトは約 5,000 万個あります。Trove4J のTLongObjectHashMap.
連続して割り当てられた識別子の長時間の実行を最適化できるものを誰かに教えてもらえますか? 挿入/取得の対数パフォーマンスは私には許容できるので、おそらくツリーベースのものでしょうか?