ハッシュマップについて私が理解していることから、内部データ構造は 2D 配列として見ることができます。最初のインデックスは「キー」になり、2 番目のインデックスは同じキーにハッシュされる値を含む配列になります。私の考えでは、将来のエントリを考慮して十分に大きな配列を初期化する必要があります(そうでなければ、ある時点で配列を拡大するか、すべての値を同じ値にハッシュする必要があります)。特定のサイズの配列を初期化する初期コストのため、これはハッシュマップがリンクリストよりも初期コストが高いことを意味します。
Linkedlist は、X 個の項目を表すのに必要なだけのメモリしか必要としません。私はこの仮定で正しいですか？LinkedList はより多くのメモリを使用すると多くの人が言うので、私は混乱しているだけです。
Maps にはキーと値があることを忘れています。したがって、リスト内のすべてのアイテムに対して、マップには 2 つあります。したがって、LinkedList がnストレージに関してコストがかかる場合、Map には が必要になります2n。それに加えて、あなたが指摘したように、いくらかの空き容量が必要なので、これで最大 2n + 2n*.c、つまり (1+c)2n になります。ここで、c は .25 のような分数です。
これは、リンクされたリストと比較して「高い」スペース要件と見なされますか? メモリ要件に制約がない限り、そうは思いません。また、リンクされたリストの場合、O(n) でアクセスする任意の要素に一定時間アクセスできることを覚えておいてください。
最後に、マップはキーと値を持つ問題を処理し、リストは主に値のみに関係するため、これらのデータ構造を適用する問題は異なる傾向があるため、この質問はあまり意味をなさない可能性があります。
いくつかの数字：
空の HashMap には 128 バイトが必要です。オーバーヘッドは 64 バイトと、エントリごとに 36 バイトです。10K エントリの場合、予想されるオーバーヘッドは ~360K です
空の LinkedList には 48 バイトが必要です。オーバーヘッドは 24 バイトに加えて、エントリごとに 24 バイトです。10K エントリの場合、予想されるオーバーヘッドは ~240K です
ソース: http://www.ibm.com/developerworks/java/library/j-codetoheap/
