Java のデータ構造で使いそうなものを自分なりにまとめたメモ。
標準ライブラリの他に、Guava 等もまとめの対象です。
java.util.List
- 順序を持つ
- 重複要素を許可
ArrayList
- 内部的には配列
- 挿入、削除はその要素以降の要素の再配置が行われるため遅い
- 追加やget(index)は速い
LinkedList
- 数珠つなぎ構造
- get(index)は遅い
- 挿入、削除が速い
org.apache.commons.collections4.list.TreeList
- 挿入、削除が速い
- 追加やget(index)も速いが、ArrayList には劣る
- 挿入・削除が多い場合は LinkedList より TreeList を選択したほうが大抵良いらしい。
- AVL tree で実装されている
java.util.Set
- 重複要素を持たない
- 順序を保証しない
HashSet
- 順序を保持しない
TreeSet
- ソートされた順序を保持する。自然順序か指定された Comparator の昇順。
- Red-Black tree で実装されている
LinkedHashSet
- 順序は挿入順
java.util.Map
- key と value が対になった要素を持つ。
- key の重複は許可されない。
- 順序を保証しない
HashMap
- 順序を保持しない
TreeMap
- key がソートされた順序を保持する。自然順序か指定された Comparator の昇順。
- Red-Black tree で実装されている
LinkedHashMap
- key の順序は挿入順。アクセス順にすることもできる。
com.google.common.collect.BiMap
- value もユニークである Map
- BiMap#inverse で key と value を入れ替えることができる
- HashBiMap、EnumHashBiMap、EnumBiMap がある
com.google.common.collect.Multiset (Bag)
- 重複を許可した Set のようなもの
- 重複要素の数をカウントするのに便利
- Bag と呼ばれるものと同じ。org.apache.commons.collections4.Bag など。
- Set のように扱えるが Set は継承していない
- HashMultiset、TreeMultiset、LinkedHashMultiset、EnumMultiset がある
com.google.common.collect.Multimap
- key 重複を許可した Map のようなもの
- Map に似ているが key - value が1対多
-
Map<key, Collection<value>>の扱いやすい版 - Map は継承していない
- ListMultimap系、SetMultimap系 などがある
com.google.common.collect.Table
-
Table<row, column, value>というテーブル構造 - key が2次元になった Map のようなもの
-
Map<key1, Map<key2, value>>の扱いやすい版 - ArrayTable、HashBasedTable、TreeBasedTable がある
stack
- 先入れ後出し(First-In Last-Out, FILO)のデータ構造
- java.util.Stack や、java.util. Deque の様々な実装を stack として使用できる
queue
- 先入れ先出し (First-In First-Out, FIFO)のデータ構造
- PriorityQueue, BlockingQueue など、java.util.Queue の様々な派生がある