1

私の質問は、バリエーションマップ/ツリーのような抽象データ構造の実装を実装する際に使用される基本/具体的なデータ構造（配列のような）は何ですか？

理論的な答えではなく、Javaコレクションで実際に使用されているものを探しています。

4

2 に答える 2

9

Sun /OracleJDKのクイックコードレビューに基づいています。詳細は自分で簡単に見つけることができます。

リスト/キュー

ArrayList

成長Object[] elementData分野。デフォルトで10個の要素を保持できますが、それ以上オブジェクトを保持できない場合は約50％増加し、古い配列をより大きな新しい配列にコピーします。アイテムを削除するときに縮小しません。

LinkedList

実際の要素、前の要素、次の要素（存在する場合）への参照Entryを保持する参照。

ArrayDeque

と似ていますが、内部配列ArrayListへの2つのポインタを保持しています-および。どちらかの側で要素を追加および削除することは、これらのポインターを移動するだけの問題です。が小さすぎると、配列は200％大きくなります。E[] elementsheadtail

マップ

HashMap

Entry[] tableいわゆるバケツを保持する成長フィールド。各バケットには、キーモジュールテーブルサイズの同じハッシュを持つエントリのリンクリストが含まれています。

TreeMap

Entry<K,V> root赤黒平衡木の根を保持する参照。

ConcurrentHashMap

同様HashMapですが、各バケット（セグメントと呼ばれる）へのアクセスは、独立したロックによって同期されます。

セット

TreeSet

下で使用TreeMap（！）

HashSet

下で使用HashMap（！）

BitSet

フィールドを使用long[] wordsして、可能な限りメモリ効率を高めます。1つの要素に最大64ビットを格納できます。

于 2012-06-02T19:31:35.940 に答える
1

もちろん、実装ごとに1つの答えがあります。javadocsを見てください、彼らはしばしばこれらのことを説明しています。http://docs.oracle.com/javase/7/docs/api/

于 2012-06-02T19:24:49.307 に答える