Коллекции Макаревич Л. Г.

Что такое коллекции Коллекция – это объект для хранения множества объектов в одном месте. Это контейнер, куда можно поместить информацию. Интерфейсы Реализация Алгоритмы Массивы

class Weeble {} // Немного мистическое создание public class ArraySize { public static void main(String[] args) { // Массивы объектов: Weeble[] a; // Null - ссылки Weeble[] b = new Weeble[5]; // Null - ссылки Weeble[] c = new Weeble[4]; for(int i = 0; i < c.length; i++) c[i] = new Weeble(); // Групповая инициализация: Weeble[] d = { new Weeble(), new Weeble(), new Weeble() }; // Динамическая групповая инициализация: a = new Weeble[] { new Weeble(), new Weeble() }; System.out.println("a.length=" + a.length); System.out.println("b.length = " + b.length); // Ссылки внутри массива автоматически // инициализируются значением null: for(int i = 0; i < b.length; i++) System.out.println("b[" + i + "]=" + b[i]); System.out.println("c.length = " + c.length); System.out.println("d.length = " + d.length); a = d; System.out.println("a.length = " + a.length); } a.length = 2 b.length = 5 b[0]=null b[1]=null b[2]=null b[3]=null b[4]=null с.length = 4 d.length = 3 a.length = 3

// Массив примитивов: int[] e; // Null - ссылка int[] f = new int[5]; int[] g = new int[4]; for(int i = 0; i < g.length; i++) g[i] = i*i; int[] h = { 11, 47, 93 }; // Ошибка компиляции: переменная e не инициализирована //!System.out.println("e.length=" + e.length); System.out.println("f.length = " + f.length); // Примитивы внутри массива // автоматически инициализируются нулем: for(int i = 0; i < f.length; i++) System.out.println("f[" + i + "]=" + f[i]); System.out.println("g.length = " + g.length); System.out.println("h.length = " + h.length); e = h; System.out.println("e.length = " + e.length); e = new int[] { 1, 2 }; System.out.println("e.length = " + e.length); f.length = 5 f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=0 g.length = 4 h.length = 3 e.length = 3 e.length = 2

Возвращение массивов public class IceCream { static String[] flav = { "Chocolate", "Strawberry", "Vanilla Fudge Swirl", "Mint Chip", "Mocha Almond Fudge", "Rum Raisin", "Praline Cream", "Mud Pie" }; static String[] flavorSet(int n) { n = Math.abs(n) % (flav.length + 1); String[] results = new String[n]; boolean[] picked = new boolean[flav.length]; for (int i = 0; i < n; i++) { int t; do t = (int)(Math.random() * flav.length); while (picked[t]); results[i] = flav[t]; picked[t] = true; } return results; } public static void main(String[] args) { for(int i = 0; i < 20; i++) { System.out.println( "flavorSet(" + i + ") = "); String[] fl = flavorSet(flav.length); for(int j = 0; j < fl.length; j++) System.out.println("\t" + fl[j]); }

Класс Arrays ( java.util.Arrays ) Заполнение Сортировка Двоичный поиск Сравнение

Заполнение

Сортировка

Поиск

Интерфейс Comparable (I подход) int compareTocompareTo(Object o) Compares this object with the specified object for order.Object import java.util.*; public class CompType implements Comparable { int i; int j; public CompType(int n1, int n2) { i = n1; j = n2; } public String toString() { return "[i = " + i + ", j = " + j + "]"; } public int compareTo(Object rv) { int rvi = ((CompType)rv).i; return (i < rvi ? -1 : (i == rvi ? 0 : 1)); } public static void main(String[] args) { CompType[] a = new CompType[10]; Random r = new Random(); for ( int i = 0 ; i < 10; i++ ) { a[i] = new CompType(Math.abs(r.nextInt()) % 100, Math.abs(r.nextInt()) % 100);} for ( int i = 0 ; i < 10; i++ ) { System.out.println(a[i]);} Arrays.sort(a); System.out.println(); for ( int i = 0 ; i < 10; i++ ) { System.out.println(a[i]);} }} Естественное сравнение

Интерфейс Comparator (II подход) import java.util.*; class CompTypeComparator implements Comparator { public int compare(Object o1, Object o2) { int j1 = ((CompType)o1).j; int j2 = ((CompType)o2).j; return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1)); } public class ComparatorTest { public static void main(String[] args) { CompType[] a = new CompType[10]; Random r = new Random(); for ( int i = 0 ; i < 10; i++ ) { a[i] = new CompType(Math.abs(r.nextInt()) % 100, Math.abs(r.nextInt()) % 100); } for ( int i = 0 ; i < 10; i++ ) { System.out.println(a[i]); } Arrays.sort(a, new CompTypeComparator()); System.out.println(); for ( int i = 0 ; i < 10; i++ ) { System.out.println(a[i]); } }}

Интерфейс Comparator int comparecompare(Object o1, Object o2) Compares its two arguments for order.Object boolean equalsequals(Object obj) Indicates whether some other object is "equal to" this Comparator.Object

Сравнение

Интерфейсы коллекций Collection – набор элементов Set – коллекция, в которой нет дублирующих элементов List – упорядоченная коллекция элементов, в которой могут быть одинаковые элементы Map – коллекция, содержащая пары ключ-значение SortedSet – множество отсортированных элементов SortedMap – коллекция с отсортированными по ключу парами Для сортировки используют два способа: интерфейсы Comparable и Comparator

Интерфейс Collection public interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator(); boolean containsAll(Collection c); boolean addAll(Collection c); // Optional boolean removeAll(Collection c); // Optional boolean retainAll(Collection c); // Optional void clear(); // Optional // Array Operations Object[] toArray(); Object[] toArray(Object a[]); } public interface Iterator { boolean hasNext(); Object next(); void remove(); // Optional }

Интерфейс Set нет дублирующих элементов public interface Set { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator(); // Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // Optional boolean removeAll(Collection c); // Optional boolean retainAll(Collection c); // Optional void clear(); // Optional // Array Operations Object[] toArray(); Object[] toArray(Object a[]); } HashSet HashSet, which stores its elements in a hash table, is the best- performing implementation. TreeSet TreeSet, which stores its elements in a red-black tree, guarantees the order of iteration.

import java.util.*; public class FindDups { public static void main(String args[]) { Set s = new HashSet(); for (int i=0; i

import java.util.*; public class FindDups2 { public static void main(String args[]) { Set uniques = new HashSet(); Set dups = new HashSet(); for (int i=0; i

Интерфейс List public interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); void add(int index, Object element); Object remove(int index); abstract boolean addAll(int index, Collection c); int indexOf(Object o); int lastIndexOf(Object o); // Iteration ListIterator listIterator(); ListIterator listIterator(int index); // Range-view List subList(int from, int to); } ArrayList - реализация public interface ListIterator extends Iterator { boolean hasNext(); Object next(); boolean hasPrevious(); Object previous(); int nextIndex(); int previousIndex(); void remove(); // Optional void set(Object o); // Optional void add(Object o); // Optional }

Пример – сдача карт import java.util.*; class Deal { public static void main(String args[]) { int numHands = Integer.parseInt(args[0]); int cardsPerHand = Integer.parseInt(args[1]); // Make a normal 52-card deck String[] suit = new String[] {"spades", "hearts", "diamonds", "clubs"}; String[] rank = new String[] {"ace","2","3","4","5","6","7","8", "9","10","jack","queen","king"}; List deck = new ArrayList(); for (int i=0; i

Интерфейс Map public interface Map { // Basic Operations Object put(Object key, Object value); Object get(Object key); Object remove(Object key); boolean containsKey(Object key); boolean containsValue(Object value); int size(); boolean isEmpty(); // Bulk Operations void putAll(Map t); void clear(); // Collection Views public Set keySet(); public Collection values(); public Set entrySet(); // Interface for entrySet elements public interface Entry { Object getKey(); Object getValue(); Object setValue(Object value); } import java.util.*; public class Freq { private static final Integer ONE = new Integer(1); public static void main(String args[]) { Map m = new HashMap(); // Initialize frequency table from command line for (int i=0; i

SortedSet и SortedMap интерфейсы public interface SortedSet extends Set { // Range-view SortedSet subSet(Object fromElement, Object toElement); SortedSet headSet(Object toElement); SortedSet tailSet(Object fromElement); // Endpoints Object first(); Object last(); // Comparator access Comparator comparator(); } public interface SortedMap extends Map { Comparator comparator(); SortedMap subMap(Object fromKey, Object toKey); SortedMap headMap(Object toKey); SortedMap tailMap(Object fromKey); Object firstKey(); Object lastKey(); } TreeSet TreeMap

SortedMap m = new TreeMap(); m.put("Sneezy", "common cold"); m.put("Sleepy", "narcolepsy"); m.put("Grumpy", "seasonal affective disorder"); System.out.println(m.keySet()); System.out.println(m.values()); System.out.println(m.entrySet()); [Grumpy, Sleepy, Sneezy] [seasonal affective disorder, narcolepsy, common cold] [Grumpy=seasonal affective disorder, Sleepy=narcolepsy, Sneezy=common cold] import java.util.*; public class MySortedSet{ public static void main(String[] a) { SortedSet m = new TreeSet(); m.add(new Integer(5)); m.add(new Integer(-5)); m.add(new Integer(1)); System.out.println(m); }

Реализации интерфейсов Implementations Hash Table Resizable ArrayBalanced TreeLinked List Interfaces SetHashSet TreeSet (SortedSet) ListArrayListLinkedList MapHashMap TreeMap SortedMap) Vector HashTable Синхронизированные коллекции (из Java 1.0)

import java.util.*; public class LinkedListDemo { public static void main(String[] argv) { System.out.println("Here is a demo of Java 1.2's LinkedList class"); LinkedList l = new LinkedList(); l.add(new Object()); l.add("Hello"); System.out.println("Here is a list of all the elements"); ListIterator li = l.listIterator(0); while (li.hasNext()) System.out.println(li.next()); if (l.indexOf("Hello") < 0) System.err.println("Lookup does not work"); else System.err.println("Lookup works"); }

import java.util.*; public class HashMapDemo { public static void main(String[] argv) { HashMap h = new HashMap(); h.put("Adobe", "Mountain View, CA"); h.put("IBM", "White Plains, NY"); h.put("Learning Tree", "Los Angeles, CA"); h.put("Microsoft", "Redmond, WA"); h.put("Netscape", "Mountain View, CA"); h.put("O'Reilly", "Sebastopol, CA"); h.put("Sun", "Mountain View, CA"); String queryString = "O'Reilly"; System.out.println("You asked about " + queryString + "."); String resultString = (String)h.get(queryString); System.out.println("They are located in: " + resultString); System.out.println(); Iterator k = h.keySet().iterator(); while (k.hasNext()) { String key = (String) k.next(); System.out.println("Key " + key + "; Value " + (String) h.get(key)); }

/** Treat a LinkList as a Queue */ public class Queue extends java.util.LinkedList { public void q_add(Object o) { addLast(o); } public Object q_take() { return removeFirst(); } public int q_len() { return size(); } public boolean q_empty() { return size() == 0; } public Object q_check() { return getFirst(); } // public void q_delete(Object o) { // } }

import java.util.*; public class TreeSetDemo { public static void main(String[] argv) { TreeSet tm = new TreeSet(String.CASE_INSENSITIVE_ORDER); tm.add("Gosling"); tm.add("da Vinci"); tm.add("van Gogh"); tm.add("Java To Go"); tm.add("Vanguard"); tm.add("Darwin"); tm.add("Darwin");// TreeSet is Set, ignores duplicates. System.out.println("Lowest (alphabetically) is " + tm.first()); System.out.println(tm.tailSet("k").toArray().length + " elements higher than \"k\""); // Print the whole list in sorted order System.out.println("Sorted list:"); java.util.Iterator t = tm.iterator(); while (t.hasNext()) System.out.println(t.next());}

import java.io.*; /** * ExecDemo shows how to execute an external program and read its output. */ public class ExecDemoSort { public static void main(String[] av) throws IOException { // A Runtime object has methods for dealing with the OS Runtime r = Runtime.getRuntime(); // A process object tracks one external running process Process p; // file contains unsorted data p = r.exec("sort sortdemo.txt"); // getInputStream gives an Input stream connected to // the process p's standard output (and vice versa). We use // that to construct a BufferedReader so we can readLine() it. BufferedReader is = new BufferedReader( new InputStreamReader(p.getInputStream())); System.out.println("Here is your sorted data:"); String aLine; while ((aLine = is.readLine()) != null) System.out.println(aLine); System.out.println("That is all, folks!"); return;}}

/** * ExecDemo shows how to execute an external program and read its output. * This version tries to let the sort's standard output appear at the terminal. */ public class ExecDemoSort2 { public static void main(String[] av) { // A Runtime object has methods for dealing with the OS Runtime r = Runtime.getRuntime(); // A process object tracks one external running process Process p; try { // file contains unsorted data p = r.exec("sort sortdemo.txt"); p.waitFor(); } catch (java.io.IOException e) { System.err.println("I/O error: " + e); } catch (InterruptedException e) { // nothing to do } }}

Создание синхронизированных классов public static Collection synchronizedCollection(Collection c); public static Set synchronizedSet(Set s); public static List synchronizedList(List list); public static Map synchronizedMap(Map m); public static SortedSet synchronizedSortedSet(SortedSet s); public static SortedMap synchronizedSortedMap(SortedMap m); List list = Collections.synchronizedList(new ArrayList()); Такая коллекция уже синхронтзирована и равносильна классу Vector Collection c = Collections.synchronizedCollection(myCollection); synchronized(c) { Iterator i = c.iterator(); // Must be in synchronized block! while (i.hasNext()) foo(i.next()); } Map m = Collections.synchronizedMap(new HashMap());... 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()); }

Создание немодифицируемых коллекций public static Collection unmodifiableCollection(Collection c); public static Set unmodifiableSet(Set s); public static List unmodifiableList(List list); public static Map unmodifiableMap(Map m); public static SortedSet unmodifiableSortedSet(SortedSet s); public static SortedMap unmodifiableSortedMap(SortedMap m);

Алгоритмы – класс Collections Сортировка Перемешивание Обработка данных Инвертирование Заполнение Копирование Поиск Нахождение экстремумов

Collections static ListList EMPTY_LIST EMPTY_LIST The empty list (immutable). static MapMap EMPTY_MAP EMPTY_MAP The empty map (immutable). static SetSet EMPTY_SET EMPTY_SET The empty set (immutable). java.lang.Objectjava.lang.Object | +--java.util.Collections

Сортировка static void sortsort(List list) Sorts the specified list into ascending order, according to the natural ordering of its elements.List static void sortsort(List list, Comparator c) Sorts the specified list according to the order induced by the specified comparator.ListComparator import java.util.*; public class Sort { public static void main(String args[]) { List l = Arrays.asList(args); Collections.sort(l); System.out.println(l); } % java Sort i walk the line [i, line, the, walk] // Sort permutation groups according to size Collections.sort(winners, new Comparator() { public int compare(Object o1, Object o2) { return ((List)o2).size() - ((List)o1).size(); } });

Перемешивание import java.util.*; public class Shuffle { public static void main(String args[]) { List l = new ArrayList(); for (int i=0; i

Манипулирование данными static void reversereverse(List list) Reverses the order of the elements in the specified list.List static Compar atorCompar ator reverseOrderreverseOrder() Returns a comparator that imposes the reverse of the natural ordering on a collection of objects that implement the Comparable interface. static void rotaterotate(List list, int distance) Rotates the elements in the specified list by the specified distance.List static void copycopy(List dest, List src) Copies all of the elements from one list into another.List static void fillfill(List list, Object obj) Replaces all of the elements of the specified list with the specified element.ListObject static ListList nCopiesnCopies(int n, Object o) Returns an immutable list consisting of n copies of the specified object.Object static boolean replaceAllreplaceAll(List list, Object oldVal, Object newVal) Replaces all occurrences of one specified value in a list with another.ListObject

Поиск static int binarySearchbinarySearch(List list, Object key) Searches the specified list for the specified object using the binary search algorithm.ListObject static int binarySearchbinarySearch(List list, Object key, Comparator c) Searches the specified list for the specified object using the binary search algorithm.ListObjectComparator Возвращается или индекс, или отрицательное значение индекса -1, куда можно вставить элемент. int pos = Collections.binarySearch(l, key); if (pos < 0) l.add(-pos-1, key);

Экстремальные значения static Obj ectObj ect maxmax(Collection coll) Returns the maximum element of the given collection, according to the natural ordering of its elements.Collection static Obj ectObj ect maxmax(Collection coll, Comparator comp) Returns the maximum element of the given collection, according to the order induced by the specified comparator.CollectionComparator static Obj ectObj ect minmin(Collection coll) Returns the minimum element of the given collection, according to the natural ordering of its elements.Collection static Obj ectObj ect minmin(Collection coll, Comparator comp) Returns the minimum element of the given collection, according to the order induced by the specified comparator.CollectionComparator

Класc Vector Methods inherited from class java.util.AbstractListAbstractList iteratoriterator, listIterator, listIteratorlistIterator Methods inherited from class java.lang.ObjectObject finalizefinalize, getClass, notify, notifyAll, wait, wait, waitgetClassnotifynotifyAllwait Methods inherited from interface java.util.ListList iteratoriterator, listIterator, listIteratorlistIterator

import java.util.*; public class VectorDemo { public static void main(String[] argv) { Vector v = new Vector(); // Create a source of Objects StructureDemo source = new StructureDemo(15); // Add lots of elements to the Vector... v.add(source.getDate()); // First print them out using a for loop. System.out.println("Retrieving by index:"); for (int i = 0; i MAX) return null; return Calendar.getInstance(); }

import java.util.*; public class VectorIterator { public static void main(String[] argv) { Vector v = new Vector(); Enumeration e; StructureDemo source = new StructureDemo(15); // Add lots of elements to the Vector... v.addElement(source.getDate()); // Process the data structure using an iterator. int i = 0; Iterator it = v.iterator(); // Remaining part of the code does not know or care // if the data is an an array, a Vector, or whatever. while (it.hasNext()) { Object o = it.next(); System.out.println("Element " + i++ + " = " + o); }

Хронометраж static long currentTimeMilliscurrentTimeMillis() Returns the current time in milliseconds. Class System long t1 = System.currentTimeMillis(); // что-то делается long t2 = System.currentTimeMillis(); System.out.println(Затраченное время: " + (t2 - t1) );