Transcript 강의 13

13주
컬렉션 (Collection)
제네릭스 (Generics)
자바프로그래밍
강원대학교
1
Collections
- 많은 데이터를 저장하는 방법 배열과 ArrayList 외에도 많은 클래스가 있다.
이들의 특징과 용도를 알아본다.
자바프로그래밍
강원대학교
2
LinkedList
먼저 구체적 예를 하나 살펴보자
자바프로그래밍
강원대학교
3
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
Arraylist uses an array
for internal storage
자바프로그래밍
강원대학교
4
LinkedList Methods
자바프로그래밍
강원대학교
5
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
자바프로그래밍
강원대학교
6
A List Iterator
자바프로그래밍
강원대학교
7
List Iterator
iterator.next();
if (iterator.hasNext())
iterator.next();
while iterator.hasNext()
{
String name = iterator.next();
Do something with name
}
자바프로그래밍
강원대학교
8
Adding and Removing from a LinkedList
• The add method:
 Adds an object after the iterator
 Moves the iterator position past the new element:
iterator.add("Juliet");
자바프로그래밍
강원대학교
9
A Conceptual View of the List Iterator
자바프로그래밍
강원대학교
10
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
자바프로그래밍
강원대학교
11
Adding and Removing from a LinkedList
• The remove method
 Removes and
 Returns the object that was returned by the last call to next or
previous
//Remove all names that fulfill a certain condition
while (iterator.hasNext())
{
String name = iterator.next();
if (name fulfills condition)
iterator.remove();
}
자바프로그래밍
강원대학교
12
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
자바프로그래밍
강원대학교
13
Methods of the ListIterator Interface
자바프로그래밍
강원대학교
14
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
자바프로그래밍
강원대학교
15
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
자바프로그래밍
강원대학교
16
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
Self Check
Why don’t we need iterators with arrays?
Answer: An integer index can be used to access any array location.
자바프로그래밍
강원대학교
18
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
Set
자바프로그래밍
강원대학교
20
Sets
• Set: Unordered collection of distinct elements
• Elements can be added, located, and removed
• Sets don’t have duplicates
자바프로그래밍
강원대학교
21
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
Sets
• We could use a linked list to implement a set
 Adding, removing, and containment testing would be relatively slow
• There are data structures that can handle these operations
much more quickly
 Hash tables
 Trees
자바프로그래밍
강원대학교
23
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
Set Classes and Interface in the Standard Library
자바프로그래밍
강원대학교
25
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
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
• An element cannot be added to a set at an iterator position
자바프로그래밍
강원대학교
27
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
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
자바프로그래밍
강원대학교
29
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
자바프로그래밍
강원대학교
30
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
자바프로그래밍
강원대학교
31
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;
}
}
Continued
자바프로그래밍
강원대학교
32
SpellCheck.java (cont.)
Program Run:
neighbouring
croqueted
pennyworth
dutchess
comfits
xii
dinn
clamour
...
자바프로그래밍
강원대학교
33
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.
자바프로그래밍
강원대학교
34
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.
자바프로그래밍
강원대학교
35
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.
자바프로그래밍
강원대학교
36
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.
자바프로그래밍
강원대학교
37
Map
자바프로그래밍
강원대학교
38
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
• Classes that implement the Map interface
 HashMap
 TreeMap
• Both of these data structures implement the Map interface
• As a rule of thumb, use a hash set unless you want to visit
the set elements in sorted order
자바프로그래밍
강원대학교
39
An Example of a Map
자바프로그래밍
강원대학교
40
Map Classes and Interfaces
자바프로그래밍
강원대학교
41
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);
자바프로그래밍
강원대학교
42
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");
자바프로그래밍
강원대학교
43
Printing Key/Value Pairs
Set<String> keySet = m.keySet();
for (String key : keySet)
{
Color value = m.get(key);
System.out.println(key + ” : " + value);
}
자바프로그래밍
강원대학교
44
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
자바프로그래밍
강원대학교
45
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]
Continued
자바프로그래밍
강원대학교
46
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.
자바프로그래밍
강원대학교
47
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.
자바프로그래밍
강원대학교
48
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.
자바프로그래밍
강원대학교
49
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);
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
}
}
자바프로그래밍
강원대학교
51
자바프로그래밍
강원대학교
52
HashTable과 SortedTree 구현
자바프로그래밍
강원대학교
53
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();
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
Hash Table with Buckets to Store Elements with Same
Hash Code
Binary Search Trees
• Fast insertion and removal of elements
• Fast searching
• Data In order
• 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
A Binary Search Tree
Big Java by Cay Horstmann
Copyright © 2009 by John Wiley & Sons. All rights
Generics
자바프로그래밍
강원대학교
59
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 타입, 캐스팅 불필요!
자바프로그래밍
강원대학교
60
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에 대입됨
자바프로그래밍
강원대학교
61
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());
자바프로그래밍
강원대학교
62
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());
자바프로그래밍
강원대학교
63
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의 타입 체크 기능 무력화!
자바프로그래밍
강원대학교
64
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!
자바프로그래밍
강원대학교
65
Wildcards
Collection<?> c = new ArrayList<String>();
c.add(new Object());
// Compile time error
c의 원소의 타입이 unknown이므로 c에 어떤 것도 add할 수 없다!
(null은 넣을 수 있다)
Object o = c.iterator().next();
자바프로그래밍
// OK!
강원대학교
66
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!
강원대학교
67
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<? extends Shape>
shapes){
for (Shape s: shapes) { unknown type,
s.draw(this);
bounded wildcard
}
}
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!
강원대학교
68
Bounded Wildcards
? - Unknown type!
public void drawAll(List<? extends Shape> shapes){
shapes.add(0, new Rectangle());
// Compile-time error!
}
자바프로그래밍
강원대학교
69
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를 object collection에 넣음!
자바프로그래밍
강원대학교
70
Generic Methods
String array일 때는 String의 Collection에,
Circle array 일때 는 Circle Collection에 넣고 싶다면?
class Collections {
static void fromArrayToCollection(Object[] a, Collection<?> c) {
for (Object o : a)
c.add(o); // 컴파일 에러!
known type
}
}
자바프로그래밍
강원대학교
71
Generic Methods
String array일 때는 String의 Collection에,
Circle array 일때 는 Circle Collection에 넣고 싶다면?
static <T> void fromArrayToCollection(T[] a, Collection<T> c) {
for (T o : a) {
c.add(o); // Correct
}
}
자바프로그래밍
강원대학교
72
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
자바프로그래밍
강원대학교
73
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
74
Generic Methods
class Collections {
public static <T> void copy(List<T> dest, List<? extends T> src) {
...
}
자바프로그래밍
강원대학교
75
참고자료
• http://docs.oracle.com/javase/tutorial/extra/g
enerics/index.html
자바프로그래밍
강원대학교
76