問題タブ [hashmap]

.txt 形式のデータが 100 万行あります。フォーマットは非常にシンプルです。行ごとに:

私の言っていることが分かるよね。ユーザーごとに、何度も表示されることもあれば、1 回だけ表示されることもあります (わかりません)。各ユーザーのすべての値を見つける必要があります。ユーザーはランダムに出現する可能性があるため、Hashmap を使用してそれを行いました。つまり、HashMap(キー: 文字列、値: ArrayList) です。しかし、arrayList にデータを追加するには、常に HashMap get(key) を使用して arrayList を取得し、それに値を追加してから、HashMap に戻す必要があります。あまり効率的ではないように感じます。誰かがそれを行うためのより良い方法を知っていますか?

私のコードでは、デフォルトですべてのリストにArrayList、すべてのマップにHashMap、すべてのセットにHashSetを使用しています。

実用的な観点から、間違った実装を選択することで、柔軟性、スケーラビリティ、読みやすさ、パフォーマンスがどれだけ失われるのでしょうか。時間をかけて別の使用ではなく使用することを決定するのはいつ意味がありますか？

特定の状況で誰かがArrayListの代わりにLinkedListを使用する理由については、確かに非常に明確なケースがあります。TreeMapやHashTableではなくHashMapを使用することが重要だと誰かが感じるのはいつですか？セットはどうですか？

質問：

1. 選択が不十分な場合のコストはいくらですか？
2. 間違った実装を選択し、データセンターに火がついたという悲惨な話はありますか？
3. 経験則はありますか？
4. なくてはならないあいまいなコレクションの実装はありますか？

私は読み通しました：

• https://docs.oracle.com/javase/1.5.0/docs/api/java/util/TreeMap.html
• https://docs.oracle.com/javase/1.5.0/docs/api/java/util/HashMap.html
• Java：リストの場合はArrayList、マップの場合はHashMap、セットの場合はHashSet？ 等...

私はこの質問が理論的な観点から関連していることを発見しましたが、私は現実の世界にもっと興味があります。

SO re Java ハッシュマップとそのO(1)検索時間に関する興味深い主張を見てきました。誰かがなぜそうなのか説明できますか? これらのハッシュマップが、私が購入したハッシュ アルゴリズムのいずれかと大きく異なる場合を除き、衝突を含むデータセットが常に存在する必要があります。

その場合、ルックアップはO(n)ではなくO(1).

誰かがO(1) であるかどうかを説明できますか?もしそうなら、どうやってこれを達成したのでしょうか?

私はC＃でHashSetとDictionaryをよく使用しましたが、非常に高速であることがわかりました...

std::mapとstd::hash_mapを使用してみましたが、比較が非常に遅いことがわかりました。これは期待される動作のように聞こえますか？std :: hash_mapの使用で間違っている可能性のあることがありますか？

または、より良いC ++ハッシュコンテナがありますか？

私はint32をハッシュしています。通常はそのうちの約100,000です。

更新：C＃とC++で再現を作成しました。2つのトライアルを実行します。C＃では19ミリ秒と13ミリ秒、C++では約11,000ミリ秒かかります。私のC++コードに本当に何か問題があるに違いありません:)

（どちらもリリースビルドとして実行されました。どちらもコンソールアプリです）

C＃出力：

C ++出力：

C ++出力（std::mapの代わりにstdext::hash_mapを使用）

C ++出力（stdext :: hash_map、リリースx64ビルドを使用）

ノート：

• Set2は、C ++で必要なように入力されていません。これは、Set1と50％の交差があると予想していましたが（C＃の場合と同様）、何らかの理由で乱数を10倍する必要がありました。部分的に交差しない

C＃：

C ++：

Map キーとしてバイト配列を使用することに問題はありますか? new String(byte[])とハッシュすることもできますがString、 を使用する方が簡単byte[]です。

STL C++ hash_map を使用して...

このような...

大量のエラーが発生します。最初の3つはこちら...

エラー 1 エラー C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : 'const std::_Tree<_Traits> のテンプレート引数を推測できませんでした&' from 'const MyKeyObject' c:\program files\microsoft visual studio 8\vc\include\functional 143

エラー 2 エラー C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : 'const std::basic_string<_Elem,_Traits, _Alloc> &' from 'const Tasking::MyKeyObject' c:\program files\microsoft visual studio 8\vc\include\functional 143

エラー 3 エラー C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : 'const MyDataObject' から 'const _Elem *' のテンプレート引数を推定できませんでした c :\program files\microsoft ビジュアル スタジオ 8\vc\include\functional 143

...

キーを int のような単純なものに設定すると、すべて問題ありません。

私は何を間違っていますか?! 多分私はテンプレートで何かをする必要がありますか?

このようなカスタム キー オブジェクトを使用してデータにアクセスするより良い (より速い?) 方法はありますか?

内のアイテムを反復処理するための最良の方法は何HashMapですか？

次のクラスを実行すると、ExecutionService はしばしばデッドロックします。

では、なぜこれが起こるのですか？またはさらに良いことに、カスタム抽象マップの実装がスレッドセーフであることを確認するテストを作成するにはどうすればよいでしょうか? (一部の実装には複数のマップがあり、別のデリゲートはキャッシュ実装など)

背景: これは Windows 上の Java 1.6.0_04 および 1.6.0_07 で発生します。問題が sun.misc.Unsafe.park() にあることはわかっています。

• Core2 Duo 2.4Ghz ラップトップで問題を再現できますが、デバッグ中には再現できません
• 作業中の Core2 Quad でデバッグできますが、RDP でハングアップしているため、明日までスタック トレースを取得できません。

以下のほとんどの回答は、HashMap のスレッド以外の安全性に関するものですが、HashMap にロックされたスレッドは見つかりませんでした。それはすべて ExecutionService コード (および Unsafe.park()) にありました。明日、スレッドを詳しく調べます。

これはすべて、カスタムの抽象 Map 実装がスレッドセーフではなかったためです。そのため、すべての実装がスレッドセーフであることを確認することにしました。本質的に、ConcurrentHashMap などの理解がまさに期待どおりであることを確認したいのですが、ExecutionService が奇妙に欠けていることがわかりました...

Python コードを同等の Java コードに変換する必要があります。Python は、多くのショートカット機能を提供することで、開発者の作業を非常に簡単にします。しかし、今は同じものを Java に移行する必要があります。Javaのdictオブジェクトに相当するものは何だろうと思っていましたか? 私は HashMap を使ってみましたが、人生は地獄です。まず、これを考慮してください。

では、これを Java に変換するにはどうすればよいでしょうか。手始めに、私は HashMap オブジェクトを使用したので、

私の問題は、名前と強度を含むリスト部分を取得し、強度部分を更新することです。これを行う実行可能な方法はありますか？別のデータ構造を検討する必要がありますか? 助けてください。