配列とコレクション

計算量（Java）

List

Map

Set

Queue

★効率比較

最後から追加

list.add(obj); ArrayList > LinkedList

任意に追加

list.add(0, obj); LinkedList > ArrayList

最初を削除

list.remove(0); LinkedList > ArrayList

中央を削除

list.remove(list.size() >> 1); ArrayList > LinkedList

最後を削除

list.remove(list.size() - 1); ArrayList = LinkedList

★Arrays.asListについて

int[] data = {1,2,3,4,5};

List list = Arrays.asList(data); // listのサイズ=1

System.out.println(data.equals(list.get(0))); true

※コレクションは基本型を含めいないため

Integer[] data = {1,2,3,4,5};

List list = Arrays.asList(data); // listのサイズ=5

list.add(6); 実行エラー

asListメソッドから戻った結果リストは変更できない、読み取り専用

改良版

class ArrayUtils{

public static <T> List<T> asList(T... t){

List<T> list = new ArrayList<T>();

Collections.addAll(list, t);

return list;

}

}

List<String> list1 = ArrayUtils.<String>asList("a", "b");

List<Integer> list2 = ArrayUtils.<Integer>asList();

List<Number> list3 = ArrayUtils.<Number>asList(1, 2, 3.6);

List<String> names = Arrays.asList(names); // read-only

List<String> names = new ArrayList<>(Arrays.asList(names));

List<String> names = Arrays.stream(names).collect(Collectors.toList()); // Java 8

// Collectors.toCollection(LinkedList::new)

★VectorとHashTable

Vector ArrayListのマルチスレッド版

HashTable HashMapのマルチスレッド版

並列処理の例

final List<Integer> tickets = new ArrayList<Integer>(); ×

final List<Integer> tickets = new Vector<Integer>(); ×

tickets.add(1);

...

Thread returnThread = new Thread(){

public void run(){

while(true){

tickets.add(new Random().nextInt());

}

}

};

Thread saleThread = new Thread(){

public void run(){

for(Integer ticket : tickets){

tickets.remove(ticket);

}

}

};

returnThread.start();

saleThread.start();

※実行エラー：java.util.ConcurrentModificationException

スレッドセーフの例

final List<Integer> tickets = new ArrayList<Integer>(); ×

final List<Integer> tickets = new Vector<Integer>(); 〇

tickets.add(1);

...

for(int i = 0; i < 10; i++){

new Thread(){

public void run(){

while(true){

System.out.println(

Thread.currentThread().getId() + " " + tickets.remove(0));

}

}

}.start();

}

★Thread Safeなコレクションに変換

JDKを参照

Map m = Collections.synchronizedMap(new HashMap());

// List l = Collections.sychronizedList(new ArrayList());

...

Set s = m.keySet(); // Needn't be in synchronized block

...

synchronized(m) { // Synchronizing on m, not s!

Iterator i = s.iterator(); // Must be in synchronized block

while (i.hasNext())

foo(i.next());

}

※変換処理より、java.util.concurrentパッケージのThread Safeなコレクションを使った方がよい

★初期化の方法

Set<String> set = new HashSet<String>();

set.add("a");

set.add("b");

private static final Set<String> set = new HashSet<String>();

static {

set.add("a");

set.add("b");

}

private static final Set<String> set = new HashSet<String>() {{

add("a");

add("b");

}};

List<String> list = new ArrayList<String>(Arrays.asList("a", "b"));

★PriorityQueueについて

・常に一番小さい値を最初に置く

PriorityQueue ソートなし

PriorityBlockingQueue Thread-safe

TreeSet 自動ソート

Queue<Item> items = new PriorityQueue<Item>();

items.add(new Item("xxx", 1000));

//items.add(null); ×

Item item = items.poll(); //poll()、peek()、element()

public class Item implements Comparable<Item> {

...

@Override

public int compareTo(Item item) {

if (this.price == item.price) {

return this.name.compareTo(item.name);

}

return this.price - item.price;

}

}

Queue<Integer> priorityQueue = new PriorityQueue<Integer>(10);

Queue<Customer> priorityQueue = new PriorityQueue<Customer>(10, comparator);

public static Comparator<Customer> comparator = new Comparator<Customer>(){

@Override

public int compare(Customer c1, Customer c2) {

return (int) (c1.getId() - c2.getId());

}

};

★TreeSetの注意点

Setの重複意味 equalsにより判断

TreeSetの順序意味 compareToにより判断

TreeSetとListの使い分け

TreeSet 定数(String, Integerなど基本型)のソートに向かう

List 変数(自作クラス)のソートに向かう

class Person implements Comparable<Person>{

private int height;

// constructor

// setter/getter

public int compareTo(Person o){

return this.height - o.height; // 昇順

}

}

SortedSet<Person> set = new TreeSet<Person>();

set.add(new Person(180));

set.add(new Person(175));

set.first().setHeight(185); ←途中変更後、順序が保証できない

解決方法１

set = new TreeSet<Person>(new ArrayList<Person>(set)); // 再度ソート

set = new TreeSet<Person>(set); × Shallow Cloneのため

解決方法２

List<Person> set = new ArrayList<Person>();

...

Collections.sort();

※なお、データの唯一性を保証するため、List⇒HashSet⇒List

★コレクション中の乱数

int num = 10;

List<String> list = new ArrayList<String>(num);

list.add("a");

...

Random rand = new Random();

for(int i = 0; i < num; i++){

int randPos = rand.nextInt(num);

// 方法１

String temp = list.get(i);

list.set(i, list.get(randPos));

list.set(randPos, temp);

// 方法２

Collections.swap(list, i, randPos);

// 方法３

Collections.shuffle(list);

}

※shuffleの応用例：ゲーム中に物の分配、宝くじ、セキュリティのデータ転送

★Arrays.sortとCollections.sort

java.util.Collections.sort(List<T>list, Comparator<? super T> c)

java.util.Arrays.sort(T[], Comparator <? super T> c)

＞Strategy pattern

class SizeComparator implements Comparator<Dog>{

@Override

public int compare(Dog o1, Dog o2) {

return o1.size - o2.size;

}

}

class WeightComparator implements Comparator<Dog>{

@Override

public int compare(Dog o1, Dog o2) {

return o1.weight - o2.weight;

}

}

Dog[] dogArray = {...};

Arrays.sort(dogArray, new SizeComparator());

Arrays.sort(dogArray, new WeightComparator());

＞superの作用

class Animal{

int size;

}

class Dog extends Animal{...}

class Cat extends Animal{...}

class SizeComparator implements Comparator<Animal>{

@Override

public int compare(Animal o1, Animal o2) {

return o1.size - o2.size;

}

}

Dog[] dogArray = {...};

Arrays.sort(dogArray, new SizeComparator());

Cat[] catArray = {...};

Arrays.sort(catArray, new SizeComparator());

★Mapに対する操作

Map⇒List

List keyList = new ArrayList(map.keySet());

List valueList = new ArrayList(map.valueSet());

List<Entry> entryList = new ArrayList<Entry>(map.entrySet());

for(Entry entry: map.entrySet()) {

K key = entry.getKey();

V value = entry.getValue();

}

あるいは

Iterator<Entry> itr = map.entrySet().iterator();

while(itr.hasNext()) {

Entry entry = itr.next();

K key = entry.getKey();

V value = entry.getValue();

}

Java8版

Map<Integer, String> map = students.stream()

.collect(Collectors.toMap(Student::getId, Student::getName));

//Handle Duplicate Keys

.collect(Collectors.toMap(Student::getId, Student::getName, (oldValue, newValue) -> oldValue));

// (oldValue, newValue) -> newValue

//Preserve List Order

.collect(Collectors.toMap(Student::getId, Student::getName, (oldValue, newValue) -> oldValue, LinkedHashMap::new));

List<Entry> list = new ArrayList<Entry>(map.entrySet());

Collections.sort(list, new Comparator<Entry>() {

@Override

public int compare(Entry e1, Entry e2) {

return e1.getKey().compareTo(e2.getKey()); //By Key

return e1.getValue().compareTo(e2.getValue()); //By Value

}

});

あるいは

SortedMap sortedMap = new TreeMap(new Comparator() {

@Override

public int compare(K k1, K k2) {

return k1.compareTo(k2);

}

});

sortedMap.putAll(map);

Map map = new HashMap();

map.put(1, "one");

...

mapX = Collections.unmodifiableMap(map);

Map<K, V> copiedMap = Collections.synchronizedMap(map); //Shallow copy

map = Collections.emptyMap(); //immutable

map = new HashMap();

for (String value : map.values()) {

...

}

繰り返し制御構文について

// Better way

for (Map.Entry<String,Integer> entry : map.entrySet()) {

String key = entry.getKey();

Integer value = entry.getValue();

}

for (String key : map.keySet()) {

Integer value = map.get(key);

}

Iterator<Map.Entry<String,Integer>> itr = map.entrySet().iterator();

while(itr.hasNext()) {

Map.Entry<String,Integer> entry = itr.next();

String key = entry.getKey();

Integer value = entry.getValue();

itr.remove(); // avoid ConcurrentModificationException

}

Iterator itr = map.keySet().iterator();

while(itr.hasNext()) {

String key = itr.next();

Integer value = map.get(key);

}

map.forEach((key, value)->{

...

});

entrySet() in foreach loop : 50

keySet() in foreach loop : 76

entrySet() and iterator : 50

keySet() and iterator : 75