Transcript Generics and Collections

13주
컬렉션 (Collection)
제네릭스 (Generics)
자바프로그래밍
강원대학교
1/79
Collections
- 많은 데이터를 저장하는 방법 배열과 ArrayList 외에도 많은 클래스가 있다.
이들의 특징과 용도를 알아본다.
자바프로그래밍
강원대학교
2/79
LinkedList
먼저 구체적 예를 하나 살펴보자
자바프로그래밍
강원대학교
3/79
Array vs Linked List
arrays
Easier to use and access
Faster access to the elements
Fixed size
One block allocation
Complex position-based insertion
자바프로그래밍
Linked Lists
Flexibility - insert (or delete) in contant time
No single allocation of memory needed
Dynamic allocation
Complex to use and access
No constant time access to the elements
강원대학교
4/79
LinkedList Methods
자바프로그래밍
강원대학교
5/79
A List Iterator
LinkedList<String> staff = new LinkedList<String>();
staff.addLast("Diana");
staff.addLast("Harry");
staff.addLast("Romeo");
staff.addLast("Tom");
ListIterator<String> iterator = staff.listIterator();
iterator.next(); // D|HRT
iterator.next(); // DH|RT
java api
자바프로그래밍
강원대학교
6/79
A List Iterator
자바프로그래밍
강원대학교
7/79
List Iterator
while iterator.hasNext()
{
String name = iterator.next();
Do something with name
}
자바프로그래밍
강원대학교
8/79
Adding to List (using the List Iterator)
iterator.add("Juliet");
자바프로그래밍
강원대학교
9/79
List Iterator
• LinkedList is a doubly linked list
 Class stores two links:
o
One to the next element, and
o
One to the previous element
• To move the list position backwards, use:
 hasPrevious
 previous
자바프로그래밍
강원대학교
10/79
Removing from LinkedList (using the ListIterator)
• The remove method
 Removes and returns the object that was returned by the last call to
next or previous
while (iterator.hasNext())
{
String name = iterator.next();
iterator.remove();
}
자바프로그래밍
강원대학교
11/79
Adding and Removing from a LinkedList
• Be careful when calling remove:
 It can be called only once after calling next or previous:
iterator.next();
iterator.next();
iterator.remove();
iterator.remove();
// Error: You cannot call remove twice.
 You cannot call it immediately after a call to add:
iter.add("Fred");
iter.remove(); // Error: Can only call remove after
// calling next or previous
자바프로그래밍
강원대학교
12/79
Methods of the ListIterator Interface
자바프로그래밍
강원대학교
13/79
ListTester.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.LinkedList;
import java.util.ListIterator;
/**
A program that tests the LinkedList class
*/
public class ListTester
{
public static void main(String[] args)
{
LinkedList<String> staff = new LinkedList<String>();
staff.addLast("Diana");
staff.addLast("Harry");
staff.addLast("Romeo");
staff.addLast("Tom");
// | in the comments indicates the iterator position
ListIterator<String> iterator = staff.listIterator(); // |DHRT
iterator.next(); // D|HRT
iterator.next(); // DH|RT
Continued
자바프로그래밍
강원대학교
14/79
ListTester.java (cont.)
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Add more elements after second element
iterator.add("Juliet"); // DHJ|RT
iterator.add("Nina"); // DHJN|RT
iterator.next(); // DHJNR|T
// Remove last traversed element
iterator.remove(); // DHJN|T
// Print all elements
for (String name : staff)
System.out.print(name + " ");
System.out.println();
System.out.println("Expected: Diana Harry Juliet Nina Tom");
}
}
Continued
자바프로그래밍
강원대학교
15/79
ArrayList vs LinkedList
java api
Arraylist uses an array
for internal storage
자바프로그래밍
강원대학교
16/79
Self Check
Do linked lists take more storage space than arrays of the
same size?
Answer: Yes, for two reasons. You need to store the node references, and each node is a separate
object. (There is a fixed overhead to store each object in the virtual machine.)
자바프로그래밍
강원대학교
17/79
Self Check
Why don’t we need iterators with arrays?
Answer: An integer index can be used to access any array location.
자바프로그래밍
강원대학교
18/79
Core Collections Framework
Collection
Set
SortedSet
List
Map
Queue
SortedMap
이들은 모두 인터페이스이다.
Set: cannot take any duplicate elements.
List: ordered, allows duplicate elements
Queue: FIFO (First In First Out)
Map: Collection of key and value pairs. does not allow duplicate keys.
Sorted Set: Ordered version of the set interface.
Sorted Map: Maintains ascending order of keys.
자바프로그래밍
강원대학교
19/79
Set
자바프로그래밍
강원대학교
20/79
Sets
• Collection of distinct elements
• Elements can be added and removed
자바프로그래밍
강원대학교
21/79
Fundamental Operations on a Set
• Adding an element
 Adding an element has no effect if the element is already in the set
• Removing an element
 Attempting to remove an element that isn’t in the set is silently
ignored
• Containment testing (Does the set contain a given object?)
• Listing all elements (in arbitrary order)
자바프로그래밍
강원대학교
22/79
Sets
• We could use a linked list to implement a set
 Removing, and containment testing would be relatively slow
• There are data structures that can handle these operations
much more quickly
 Hash tables
 Trees
자바프로그래밍
강원대학교
23/79
Sets
• Standard Java library provides set implementations based on
both data structures
 HashSet
 TreeSet
• Both of these data structures implement the Set interface
• As a rule of thumb, use a hash set unless you want to visit
the set elements in sorted order
자바프로그래밍
강원대학교
24/79
Set Classes and Interface in the Standard Library
자바프로그래밍
강원대학교
25/79
Using a Set
• Example: Using a set of strings
• Construct the Set:
Set<String> names = new HashSet<String>();
or
Set<String> names = new TreeSet<String>();
• Add and remove elements:
names.add("Romeo");
names.remove("Juliet");
• Test whether an element is contained in the set:
if (names.contains("Juliet")) . . .
자바프로그래밍
강원대학교
26/79
Iterator
• Use an iterator to visit all elements in a set
• A set iterator does not visit the elements in the order in
which they were inserted
자바프로그래밍
강원대학교
27/79
Visiting All Elements with an Iterator
Iterator<String> iter = names.iterator();
while (iter.hasNext())
{
String name = iter.next();
Do something with name
}
or, using the “for each” loop:
for (String name : names)
{
Do something with name
}
자바프로그래밍
강원대학교
28/79
Iterator
• An element cannot be added to a set at an iterator position
List<E>는 아래 두 메소드를 지원함
ListIterator<E> listIterator()
Iterator<E>
iterator()
Set<E>는 아래 메소드만을 지원함
Iterator<E>
iterator()
Interator<E>
boolean
E
void
자바프로그래밍
hasNext()
next()
remove()
ListIterator<E>
voidadd(E e)
boolean
hasNext()
boolean
hasPrevious()
E
next()
int
nextIndex()
E
previous()
int
previousIndex()
void
remove()
void
set(E e)
강원대학교
29/79
Set Test Program
1. Read in all words from a dictionary file that contains
correctly spelled words and place them into a set
2. Read all words from a document into a second set — here,
the book “Alice in Wonderland”
3. Print all words from that set that are not in the dictionary
set — potential misspellings
자바프로그래밍
강원대학교
30/79
SpellCheck.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import
import
import
import
import
java.util.HashSet;
java.util.Scanner;
java.util.Set;
java.io.File;
java.io.FileNotFoundException;
/**
This program checks which words in a file are not present in a dictionary.
*/
public class SpellCheck
{
public static void main(String[] args)
throws FileNotFoundException
{
Continued
자바프로그래밍
강원대학교
31/79
SpellCheck.java (cont.)
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Read the dictionary and the document
Set<String> dictionaryWords = readWords("words");
Set<String> documentWords = readWords("alice30.txt");
// Print all words that are in the document but not the dictionary
for (String word : documentWords)
{
if (!dictionaryWords.contains(word))
{
System.out.println(word);
}
}
}
Continued
자바프로그래밍
강원대학교
32/79
SpellCheck.java (cont.)
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
Reads all words from a file.
@param filename the name of the file
@return a set with all lowercased words in the file. Here, a
word is a sequence of upper- and lowercase letters.
*/
public static Set<String> readWords(String filename)
throws FileNotFoundException
{
Set<String> words = new HashSet<String>();
Scanner in = new Scanner(new File(filename));
// Use any characters other than a-z or A-Z as delimiters
in.useDelimiter("[^a-zA-Z]+");
while (in.hasNext())
{
words.add(in.next().toLowerCase());
}
return words;
}
}
자바프로그래밍
강원대학교
33/79
SpellCheck.java
Program Run:
neighbouring
croqueted
pennyworth
dutchess
comfits
xii
dinn
clamour
...
자바프로그래밍
강원대학교
34/79
Self Check
Arrays and lists remember the order in which you added
elements; sets do not. Why would you want to use a set
instead of an array or list?
Answer: Efficient set implementations can quickly test whether a given element is a member of the
set.
자바프로그래밍
강원대학교
35/79
Self Check
Why are set iterators different from list iterators?
Answer: Sets do not have an ordering, so it doesn’t make sense to add an element at a
particular iterator position, or to traverse a set backwards.
자바프로그래밍
강원대학교
36/79
Self Check
Suppose you changed line 18 of the SpellCheck program to
use a TreeSet instead of a HashSet. How would the output
change?
Answer: The words would be listed in sorted order.
자바프로그래밍
강원대학교
37/79
Self Check
When would you choose a tree set over a hash set?
Answer: When it is desirable to visit the set elements in sorted order.
자바프로그래밍
강원대학교
38/79
Map
자바프로그래밍
강원대학교
39/79
Maps
• A map keeps associations between key and value objects
• Every key in a map is unique
• A value may be associated with several keys
자바프로그래밍
강원대학교
40/79
Maps
• Classes that implement the Map interface
 HashMap
 TreeMap
• As a rule of thumb, use a hash set unless you want to visit
the set elements in sorted order
자바프로그래밍
강원대학교
41/79
Map Classes and Interfaces
자바프로그래밍
강원대학교
42/79
Using a Map
• Example: Associate names with colors
• Construct the Map:
Map<String, Color> favoriteColors =
new HashMap<String, Color>();
or
Map<String, Color> favoriteColors =
new TreeMap<String, Color>();
• Add an association:
favoriteColors.put("Juliet", Color.RED);
• Change an existing association:
favoriteColors.put("Juliet",Color.BLUE);
자바프로그래밍
강원대학교
43/79
Using a Map
• Get the value associated with a key:
Color julietsFavoriteColor =
favoriteColors.get("Juliet”);
• Remove a key and its associated value:
favoriteColors.remove("Juliet");
자바프로그래밍
강원대학교
44/79
Printing Key/Value Pairs
Set<String> keySet = m.keySet();
for (String key : keySet)
{
Color value = m.get(key);
System.out.println(key + ” : " + value);
}
자바프로그래밍
강원대학교
45/79
MapDemo.java
1 import java.awt.Color;
2 import java.util.HashMap;
3 import java.util.Map;
4 import java.util.Set;
5
6 /**
7
This program demonstrates a map that maps names to colors.
8 */
9 public class MapDemo
10 {
11
public static void main(String[] args)
12
{
13
Map<String, Color> favoriteColors = new HashMap<String,
Color>();
14
favoriteColors.put("Juliet", Color.BLUE);
15
favoriteColors.put("Romeo", Color.GREEN);
16
favoriteColors.put("Adam", Color.RED);
17
favoriteColors.put("Eve", Color.BLUE);
18
Continued
자바프로그래밍
강원대학교
46/79
MapDemo.java (cont.)
19
20
21
22
23
24
25
26
27
28
// Print all keys and values in the map
Set<String> keySet = favoriteColors.keySet();
for (String key : keySet)
{
Color value = favoriteColors.get(key);
System.out.println(key + " : " + value);
}
}
}
Program Run:
Romeo : java.awt.Color[r=0,g=255,b=0]
Eve : java.awt.Color[r=0,g=0,b=255]
Adam : java.awt.Color[r=255,g=0,b=0]
Juliet : java.awt.Color[r=0,g=0,b=255]
자바프로그래밍
강원대학교
47/79
Self Check
What is the difference between a set and a map?
Answer: A set stores elements. A map stores associations between keys and values.
자바프로그래밍
강원대학교
48/79
Self Check
Why is the collection of the keys of a map a set?
Answer: The ordering does not matter, and you cannot have duplicates.
자바프로그래밍
강원대학교
49/79
Core Collections Framework
Collection
Set
List
Map
Queue
SortedMap
SortedSet
Set: cannot take any duplicate elements.
List: ordered, allows duplicate elements
Queue: FIFO (First In First Out)
Map: Collection of key and value pairs. does not allow duplicate keys.
Sorted Set: Ordered version of the set interface.
Sorted Map: Maintains ascending order of keys.
자바프로그래밍
강원대학교
50/79
Operations Supported by
Collection <E> interface
boolean isEmpty();
boolean contains (Object element);
boolean add (Object element);
boolean remove (Object element);
Iterator <E> iterator();
boolean containsAll (Collection <?> C);
boolean addAll (Collection <? extends E> C);
boolean removeAll (Collection() <?> C);
boolean retainAll (Collection <?> C);
void clear();
Object[ ] toArray();
<T> T[ ] toArray(T[ ]a);
51/79
Iteration
• Two ways to iterate over Collections:
– Iterator
static void loopThrough(Collection col){
for (Iterator <E> iter = col.iterator(); iter.hasnext()) {
Object obj=iter.next();
}
}
– For-each
static void loopThrough(Collection col){
for (Object obj: col) {
//access object
}
}
자바프로그래밍
강원대학교
52/79
자바프로그래밍
강원대학교
53/79
HashTable과 SortedTree 구현
자바프로그래밍
강원대학교
54/79
Hash Tables
• Hashing can be used to find elements in a data structure
quickly without making a linear search
• A hash table can be used to implement sets and maps
• A hash function computes an integer value (called the hash
code) from an object
• A good hash function minimizes collisions — identical hash
codes for different objects
• To compute the hash code of object x:
int h = x.hashCode();
자바프로그래밍
강원대학교
55/79
Sample Strings and Their Hash Codes
자바프로그래밍
String
Hash Code
"Adam"
2035631
"Eve"
700068
"Harry"
69496448
"Jim"
74478
"Joe"
74656
"Juliet"
-2065036585
"Katherine"
2079199209
"Sue"
83491
강원대학교
56/79
Hash Table with Buckets to Store Elements with Same
Hash Code
자바프로그래밍
강원대학교
57/79
Binary Search Trees
• Data In order
• Fast insertion and removal of elements
• Fast searching
• A binary tree consists of two nodes, each of which has two
child nodes
• All nodes in a binary search tree fulfill the property that:
 Descendants to the left have smaller data values than the node data
value
 Descendants to the right have larger data values than the node data
value
자바프로그래밍
강원대학교
58/79
A Binary Search Tree
자바프로그래밍
강원대학교
Big Java by Cay Horstmann
Copyright © 2009 by John Wiley & Sons.59/79
All rights
Generics
자바프로그래밍
강원대학교
60/79
List myList = new LinkedList();
// myList에는 무엇이든 넣을 수 있다.
// myList에 Integer 객체만을 넣기로 작정함
myList.add(new Integer(0));
Why generics?
Integer x = (Integer) myList.get(0); // 0번째 항목 반환
// LinkedList의 get 메소드가 반환하는 것은 Object 타입이므로
// Integer 타입으로 캐스팅, 캐스팅 하지 않는 경우 컴파일 오류 발생!
// 프로그래머 실수로
// myList에 Integer 객체가 아닌 것을 넣으면 런타임 에러 발생!
견고한 (robust) 프로그램
List<Integer> myList = new LinkedList<Integer>();
// myList에는 Integer 객체만 넣을 수 있다.
myList.add(new Integer(0));
Integer x = myList.get(0);
// get(0)가 반환하는 것은 Integer 타입, 캐스팅 불필요!
자바프로그래밍
강원대학교
61/79
Type parameter, type argument
public interface List <E>{
void add(E e);
E get(int index);
•••
}
type parameter
List<Integer>
List<Double>
type argument
•
•
Gereric type 클래스나 인터페이스는 한 번 컴파일되어 하나의 바이트코드
파일로 존재
실행시 (메소드가 호출될 때) type argument 가 type parameter에 대입됨
자바프로그래밍
강원대학교
62/79
Java.util.List<E>, java.util.Iterator<E>
public interface List <E>{
void add(E e);
E get(int index);
Iterator<E> iterator();
}
public interface Iterator<E>{
E next();
boolean hasNext();
}
List<Integer> myList = new LinkedList<Integer>();
myList.add(new Integer(0));
myList.add(new Integer(1));
Iterator<Integer> it = myList.iterator();
while(it.hasNext())
System.out.println(it.next());
자바프로그래밍
강원대학교
63/79
Java.util.List<E>, java.util.Iterator<E>
public interface List <E>{
void add(E e);
E get(int index);
Iterator<E> iterator();
}
public interface Iterator<E>{
E next();
boolean hasNext();
}
List<Double> myList = new LinkedList<Double>();
myList.add(new Double(0.0));
myList.add(new Double(1.0));
Iterator<Double> it = myList.iterator();
while(it.hasNext())
System.out.println(it.next());
자바프로그래밍
강원대학교
64/79
Generics and Subtyping
• String은 Object이다.
(String은 Object의 서브타입)
• List<String>은 List<Object>이다? No!
(List<String>은 List<Object>의 서브타입이 아님)
만약, List<String>이 List<Object>의 서브타입이라면,
List<String> ls = new ArrayList<String>();
List<Object> lo = ls; // aliasing
lo.add(new Object());
String s = ls.get(0);
// Generics의 타입 체크 기능 무력화!
자바프로그래밍
강원대학교
65/79
Wildcards
void printCollection(Collection<Object> c) {
for (Object e : c) {
System.out.println(e);
}
}
Collection<String> c = new ArrayList<String>();
c.add("aa"); c.add("bb");
printCollection(c); // error!
// Collection<String>은 Collection<Object>의 서브타입이 아니므로
void printCollection(Collection<?> c) {
for (Object e : c) {
System.out.println(e);
}
}
// Collection of unknowns
Collection <String> c = new ArrayList<String>();
c.add("aa"); c.add("bb");
printCollection(c); // OK!
자바프로그래밍
강원대학교
66/79
Wildcards
Collection<?> c = new ArrayList<String>();
c.add(new Object());
// Compile time error
c의 원소의 타입이 unknown인 경우 c에 어떤 것도 add할 수 없다!
(null은 넣을 수 있다)
Object o = c.iterator().next();
자바프로그래밍
// OK!
강원대학교
67/79
Bounded Wildcards
public abstract class Shape {
public abstract void draw(Canvas c);
}
public class Circle extends Shape {
private int x, y, radius;
public void draw(Canvas c) {
...
}
}
public class Rectangle extends Shape
{
private int x, y, width, height;
public void draw(Canvas c) {
...
}
}
자바프로그래밍
public void drawAll(List<Shape> shapes) {
for (Shape s: shapes) {
s.draw(this);
}
}
List<Shape> ls = new List<Shape>();
drawAll(ls);
// OK!
List<Circle> lc = new List<Circle>();
drawAll(lc);
// Compile Error!
List<Rectangle> lr = new List<Rectangle>();
drawAll(lr);
// Compile Error!
강원대학교
68/79
Bounded Wildcards
public abstract class Shape {
public abstract void draw(Canvas
c);
}
public class Circle extends Shape {
private int x, y, radius;
public void draw(Canvas c) {
...
}
}
public class Rectangle extends Shape
{
private int x, y, width, height;
public void draw(Canvas c) {
...
}
}
자바프로그래밍
unknown type,
bounded wildcard
public void drawAll(List<? extends Shape>
shapes){
for (Shape s: shapes) {
s.draw(this);
}
}
List<Shape> ls = new List<Shape>();
drawAll(ls);
// OK!
List<Circle> lc = new List<Circle>();
drawAll(lc);
// OK!
List<Rectangle> lr = new List<Rectangle>();
drawAll(lr);
// OK!
강원대학교
69/79
Bounded Wildcards
? - Unknown type!
public void drawAll(List<? extends Shape> shapes){
shapes.add(0, new Rectangle());
// Compile-time error!
}
자바프로그래밍
강원대학교
70/79
Arrays vs Generics
String[] strings = new String[] { "a", "b" };
Object[] objects = strings;
// OK!
objects[0] = new Date(); // <-- Runtime error here
List<String> ls = new LinkedList<String>();
List<Object> lo = ls;
// Compile error
자바프로그래밍
강원대학교
71/79
Generic Methods
class Collections {
static void fromArrayToCollection(Object[] a, Collection<Object> c) {
for (Object o : a)
c.add(o);
}
}
public class GenericMethods {
public static void main(String[] args){
String[] sa = {"aa", "bb"};
Collection<Object> co = new ArrayList<Object>();
Collections.fromArrayToCollection(sa, co);
for (Object o : co)
System.out.println(o); String array는 Object array에 대입 가능
}
}
String array를 collection of object 에 넣음!
자바프로그래밍
강원대학교
72/79
Generic Methods
String array는 Collection of String에,
Circle array는 Collection of Circle에 넣고 싶다면?
class Collections {
static void fromArrayToCollection(Object[] a, Collection<?> c) {
for (Object o : a)
c.add(o); // 컴파일 에러!
unknown type
}
}
자바프로그래밍
강원대학교
73/79
Generic Methods
String array는 Collection of String에,
Circle array는 Collection of Circle에 넣고 싶다면?
static <T> void fromArrayToCollection(T[] a, Collection<T> c) {
for (T o : a) {
c.add(o); // Correct
}
}
자바프로그래밍
강원대학교
74/79
static <T> void fromArrayToCollection(T[] a, Collection<T> c) {
for (T o : a)
c.add(o);
}
Object[] oa = new Object[100];
Collection<Object> co = new ArrayList<Object>();
fromArrayToCollection(oa, co);
// T inferred to be Object
String[] sa = new String[100];
Collection<String> cs = new ArrayList<String>();
fromArrayToCollection(sa, cs);
// T inferred to be String
fromArrayToCollection(sa, co);
자바프로그래밍
// T inferred to be Object
강원대학교
75/79
static <T> void fromArrayToCollection(T[] a, Collection<T> c) {
for (T o : a)
c.add(o);
}
Number은
BigInteger, Byte, Double, Float,
Integer, Long, Short의 super class!
Integer[] ia = new Integer[100];
Float[] fa = new Float[100];
Number[] na = new Number[100];
Collection<Number> cn = new ArrayList<Number>();
fromArrayToCollection(ia, cn);
fromArrayToCollection(fa, cn);
fromArrayToCollection(na, cn);
fromArrayToCollection(na, co);
//
//
//
//
fromArrayToCollection(na, cs);
// compile-time error
자바프로그래밍
T
T
T
T
inferred
inferred
inferred
inferred
강원대학교
to
to
to
to
be
be
be
be
Number
Number
Number
Object
76/79
Generic Methods
class Collections {
public static <T> void copy(List<T> dest, List<? extends T> src) {
...
}
자바프로그래밍
강원대학교
77/79
참고자료
• http://docs.oracle.com/javase/tutorial/extra/g
enerics/index.html
자바프로그래밍
강원대학교
78/79
자바프로그래밍
강원대학교
79/79