[CH11] Collections framework

본 포스팅은 자바의 정석 교재를 공부하며, 간단히 정리/기록 용도로 작성하였습니다. 혹여, 잘못된 내용이 있다면 지적해주시면 감사하겠습니다.

 

 

---

0. Collections Framework

  Collections Framework 란 data group 을 다루고 표현하기 위한 단일화된 architecture 을 말한다. Collections Framework 의 핵심 인터페이스는 List, Set, Map 이다. List 는 (순서가 있는) 데이터의 중복을 허용하며 ArrayList, LinkedList, Stack, Vector 등으로 구현된다. Set 은 (순서가 없는) 데이터의 중복을 허용하지 않는 것으로 HashSet, TreeSet 등으로 구현된다. Map 은 key - value pair 로 이뤄진 것으로 순서는 유지되지 않으며 키는 중복을 허용하지 않고 값은 허용한다. HashMap, TreeMap, HashTable, Properties 등으로 구현된다.

 

  List 인터페이스는 중복을 허용하면서 저장 순서는 유지되는 컬렉션을 구현하는데에 사용한다. 

https://catsbi.oopy.io/8f0f5192-3a06-405e-8076-dbc5ff9f2dfb

  Set 인터페이스는 중복을 허용하지 않고 순서를 고려하지 않는 클래스를 구현하는데에 사용된다.

https://catsbi.oopy.io/8f0f5192-3a06-405e-8076-dbc5ff9f2dfb

  Map 인터페이스는 key- value 를 pair 로 가지는 클래스를 구현하는데에 사용된다. 키는 중복될 수 없으나 value 는 중복을 허용하며, 중복된 키와 값을 저장하면 마지막에 저장된 값이 남는다.

https://catsbi.oopy.io/8f0f5192-3a06-405e-8076-dbc5ff9f2dfb

  Map.Entry 인터페이스는 Map 인터페이스의 내부 인터페이스(inner interface)이다. 

 

public interface Map {

...

public static interface Entry{

Object getKey();

Object getValue();

Object setValue(Object value);

boolean equals(Object o);

int hashCode();

...

    }

}

1. ArrayList

  ArrayList 는 List 인터페이스의 구현이기 때문에 데이터의 저장 순서가 유지되고 중복을 허용한다. Vector 을 개선한 것으로, 데이터를 Object 배열을 이용해서 순차적으로 저장한다. 

 

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable {

...

transient Object[] elementData;

...

}

 

ArrayList 는 elementData 을 멤버변수로 선언하고 있고, Object 배열이므로 모든 type 의 객체를 담을 수 있다.

import java.util.ArrayList;
import java.util.Collections;

class source{
    public static void main(String[] args) {
        ArrayList list1 = new ArrayList(10);
        list1.add(5);
        list1.add(4);
        list1.add(2);
        list1.add(0);
        list1.add(1);
        list1.add(3);

        ArrayList list2 = new ArrayList(list1.subList(1,4));
        print(list1, list2);

        Collections.sort(list1);
        Collections.sort(list2);

        System.out.println("list1.containsAll(list2): " + list1.containsAll(list2));

        list2.add("B");
        list2.add("C");
        list2.add(3, "A");
        print(list1, list2);

        list2.set(3, "AA");
        print(list1, list2);

        System.out.println("list1.retainAll(list2):" + list1.retainAll(list2));
        print(list1, list2);

        for(int i = list2.size()-1; i>=0 ;i--){
            if(list1.contains(list2.get(i)))
                list2.remove(i);
        }
        print(list1, list2);
    }
    static void print(ArrayList list1, ArrayList list2){
        System.out.println("List1:" + list1);
        System.out.println("List2:" + list2);
        System.out.println();
    }
}

import java.util.ArrayList;
import java.util.List;

class source{
    public static void main(String[] args) {
        final int LIMIT = 10;
        String source = "0123456789abcdefghijABCDEFGHIJ!@#$%^&*()ZZZ";
        int length = source.length();

        List list = new ArrayList(length/LIMIT + 10);

        for(int i=0; i < length; i+=LIMIT){
            if(i+LIMIT < length)
                list.add(source.substring(i, i+LIMIT));
            else
                list.add(source.substring(i));
        }
        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }


    }
    static void print(ArrayList list1, ArrayList list2){
        System.out.println("List1:" + list1);
        System.out.println("List2:" + list2);
        System.out.println();
    }
}

import java.util.ArrayList;
import java.util.Vector;

class source{
    public static void main(String[] args) {
        Vector v = new Vector(5);
        v.add("1");
        v.add("2");
        v.add("3");
        print(v);

        v.trimToSize();
        System.out.println("=== After trimToSize() ===");
        print(v);

        v.ensureCapacity(6);
        System.out.println("=== After ensureCapacity(6) ===");
        print(v);

        v.setSize(7);
        System.out.println("=== After setSize(7) ===");;
        print(v);

        v.clear();
        System.out.println("=== After clear() === ");
        print(v);
    }
    static void print(ArrayList list1, ArrayList list2){
        System.out.println("List1:" + list1);
        System.out.println("List2:" + list2);
        System.out.println();
    }
    static void print(Vector v){
        System.out.println(v);
        System.out.println("size :" + v.size());
        System.out.println("capacity :" + v.capacity());
    }
}

3번째 코드의 결과는 아래와 같다.

1. 맨 처음에는 capacity 가 5 인 Vector 인스턴스 v 를 생성하고, 3개의 객체를 저장했기 때문에 size 가 3, cap 이 5 가 나온다.

2. 이후 v.trimToSize(); 를 호출하면 빈 공간을 없애므로 size = 3, cpa = 3 이 된다. 배열은 크기를 변경할 수 없으므로 새로운 배열을 생성한 다음 주소값을 변수 v 에 할당하는 것이다. 기존의 Vector 인스턴스는 Garbage collector 에 의해 메모리에서 제거된다.

3. 그리고 ensureCapacity(6) 을 호출하면 인스턴스 v 의 capacity 가 최소한 6이 되도록 한다. v 의 cap 이 만약 6보다 컸다면 아무런 변화가 일어나지 않고, 6보다 작았다면 크기가 6인 배열을 생성해서 v의 내용을 복사한다.

4. v.setSize(7) 은 인스턴스 v 의 size 를 7로 만들어준다. capacity 가 충분하다면 새로운 인스턴스를 만들지 않으나, capacity 가 부족하다면 새로운 인스턴스를 생성하는데, 내부 구현 방식에 따라 capacity 는 2배가 된다.

5. v.clear(); 는 v 의 모든 요소를 삭제하는 것으로 size 가 0이 된다. 

 

ArrayList 나 Vecotr 와 같이 배열을 이용한 자료구조는 데이터의 read/write 효울이 좋은 편이지만,

Capacity 를 변경해야 하는 상황에는 새로운 배열을 생성한 다음에 복사하므로

효율이 상당히 떨어진다는 단점이 있다.

 

import java.util.List;

public class MyVector implements List{
    Object[] data = null;
    int capacity = 0;
    int size = 0;

    public MyVector(int capacity){
        if(capacity < 0)
            throw new IllegalArgumentException("invalid value. : " + capacity);
        this.capacity = capacity;
        data = new Object[capacity];
    }
    public MyVector(){
        this(10);
    }
    public void ensureCapacity(int minCapacity){
        if(minCapacity - data.length>0)
            setCapacity(minCapacity);
    }
    public boolean add(Object obj){
        ensureCapacity(size+1);
        data[size++] = obj;
        return true;
    }
    public Object get(int index){
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException("OutOfBounds...");
        return data[index];
    }
    public Object remove(int index){
        Object oldObj = null;

        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException("OutOfBounds...");
        oldObj = data[index];

        if(index != size-1){
            System.arraycopy(data, index+1, data, index, size-index-1);
        }
        data[size-1] = null;
        size--;
        return oldObj;
    }
    public boolean remove(Object obj){
        for(int i = 0 ; i < size; i ++){
            if(obj.equals(data[i])){
                remove(i);
                return true;
            }
        }
        return false;
    }
    public void trimToSize(){
        setCapacity(size);
    }
    private void setCapacity(int capacity){
        if(this.capacity == capacity) return;

        Object[] tmp = new Object[capacity];
        System.arraycopy(data, 0, tmp, 0, size);
        data = tmp;
        this.capacity = capacity;
    }
    public Object[] toArray(){
        Object[] result = new Object[size];
        System.arraycopy(data, 0, result, 0, size);

        return result;
    }

    public boolean isEmpty() { return size==0; }
    public int capacity() { return capacity; }
    public int size() { return size; }
    
    public boolean contains(Object o){
        if(indexOf(o) >= 0) return true;
        else return false;
    }
    public Object set(int index, Object element){
        if(index >= size || index < 0)
            throw new IndexOutOfBoundsException();
        else{
            data[index] = element;
            return data;
        }
    }
    public void add(int index, Object element){
        if(index >= size || index < 0)
            throw new IndexOutOfBoundsException();
        else {
            ensureCapacity(size+1);
            data[++size] = element;
        }
    }
    public int indexOf(Object o){
        for(int i = 0 ; i < size; i ++){
            if(data[i].equals(o)){
                return i;
            }
        }
        return -1;
    }
    public int lastIndexOf(Object o){
        for(int i = size - 1 ; i >=0 ; i--){
            if(data[i].equals(o))
                return i;
        }
        return -1;
    }
    public String toString(){
        String str = "[";
        for(int i = 0 ; i < size; i ++){
            str += data[i];
            if(i < size-1){
                str +=",";
            }
        }
        return str + "]";
    }
    /*

    이하 생략

     */
}

 

2. LinkedList

  링크드 리스트는 배열의 단점 (1. 크기를 변경할 수 없다. 2. 비순차적인 데이터의 추가/삭제에 비효율적이다) 을 보완하고자 고안된 자료구조이며 불연속적으로 존재하는 데이터를 서로 linking 한 형태이다. 각각의 요소들은 다음 요소에 대한 참조(주소값)와 데이터로 구성되어있다.

 

class Node{ 

Node next;

Object obj;

}

 

  다만 single linked list 는 이동 방향이 단방향이라 다음 요소에 대한 접근은 효율적이지만 이전 요소에 대한 접근은 어렵다. 이를 보완한 것은 이전 요소에 대한 참조도 저장하는 double linked list 이다.

 

class Node{ 

Node next;

Node previous;

Object obj;

}

 

  double linked list 의 접근성을 보다 향상 시킨 것은 double circular linked list 으로 첫 번째 요소와 마지막 요소를 연결한 것이다. 실제 JAVA 의 LinkedList 클래스는 double linked list 로 구현되어 있다. 

 

1. 순차적으로 추가/삭제 하는 경우에는 ArrayList 가 LinkedList 보다 빠르다.

2. 중간 데이터를 추가/삭제 하는 경우에는 LinkedList 가 ArrayList 보다 빠르다.

3. Stack and Queue

   Stack 은 ArrayList 와 같은 배열 기반 컬렉션 클래스로 구현하고, Queue 는 ArrayList 를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위한 데이터의 복사 작업이 필요하므로 이보다는 LinkedList 로 구현하는 것이 적합하다. 

import java.util.EmptyStackException;
import java.util.Vector;

class MyStack extends Vector {
    public Object push(Object item){
        addElement(item);
        return item;
    }
    public Object pop(){
        Object obj = peek();
        removeElementAt(size()-1);
        return obj;
    }
    public Object peek(){
        int len = size();
        if(len == 0)
            throw new EmptyStackException();
        return elementAt(len-1);
    }
    public boolean empty(){
        return size()==0;
    }
    public int search(Object o){
        int i = lastIndexOf(o);
        if(i>=0)
            return size()-i;
        return -1;
    }
}

스택의 대표적인 활용 사례는 수식 계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로이며, 큐의 대표적인 활용 사례는 최근사용문서, 인쇄작업 대기목록, buffer 등이 있다.

import java.util.Stack;

class source{
    public static Stack back = new Stack();
    public static Stack forward = new Stack();
    public static void main(String[] args) {
        goURL("1.google");
        goURL("2.naver");
        goURL("3.daum");
        goURL("4.yahoo");

        printStatus();

        goBack();
        System.out.println("push \"go back\" ");
        printStatus();

        goBack();
        System.out.println("push \"go back\" ");
        printStatus();

        goForward();
        System.out.println("push \"go forward\" ");
        printStatus();

        goURL("codechobo.com");
        System.out.println("push \"go to new URL\" ");
        printStatus();
    }
    public static void printStatus(){
        System.out.println("back:"+back);
        System.out.println("forward:"+forward);
        System.out.println("present: " + back.peek());
        System.out.println();
    }
    public static void goURL(String url){
        back.push(url);
        if(!forward.empty())
            forward.clear();
    }
    public static void goForward(){
        if(!forward.empty())
            back.push(forward.pop());
    }
    public static void goBack(){
        if(!back.empty())
            forward.push(back.pop());
    }
}

위 예제는 웹 브라우저의 앞으로가기, 뒤로가기를 간단히 구현한 것으로 BACK, FORWARD 역할을 하는 2 개의 STACK 으로 구현이 가능하다.

import java.util.EmptyStackException;
import java.util.Stack;

public class source{
    public static void main(String[] args) {
        Stack st = new Stack();
        String expression = "((2+3)*1)+3";

        System.out.println("Expression:" + expression);

        try{
            for(int i = 0 ; i < expression.length(); i++){
                char ch = expression.charAt(i);
                if(ch=='('){
                    st.push(ch+"");
                } else if(ch==')'){
                    st.pop();
                }
            }
            if(st.isEmpty()){
                System.out.println("correct!");
            }
            else{
                System.out.println("something wrong...");
            }
        } catch (EmptyStackException e){
            System.out.println("something wrong...");
        }
    }
}

위 예제는 수식의 괄호를 검사하는 것으로, stack 을 이용하여 간단히 구현할 수 있다. 

 

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Scanner;

class source{
    static Queue q =new LinkedList();
    static final int MAX_SIZE = 5;

    public static void main(String[] args) {
        System.out.println("You can view the guide by typing \"help\". ");

        while(true){
            System.out.print(">>");
            try{
                Scanner s = new Scanner(System.in);
                String input = s.nextLine().trim();

                if("".equals(input)) continue;

                if(input.equalsIgnoreCase("q")){
                    System.exit(0);
                } else if(input.equalsIgnoreCase("help")){
                    System.out.println(" help - Shows guide.");
                    System.out.println(" q or Q - Exit");
                    System.out.println(" history - Shows " + MAX_SIZE + " commands " +
                            "that you have recently entered.");
                } else if(input.equalsIgnoreCase("history")){
                    int i = 0;
                    save(input);
                    LinkedList tmp = (LinkedList)q;
                    ListIterator it = tmp.listIterator();

                    while(it.hasNext())
                        System.out.println(++i+"."+it.next());
                } else{
                    save(input);
                    System.out.println(input);
                }
            } catch (Exception e) {
                System.out.println("invalid command.");
            }
        }
    }
    public static void save(String input){
        if(!"".equals(input))
            q.offer(input); // queue 에 객체를 저장

        if(q.size() > MAX_SIZE)
            q.remove();
    }
}

위 예제는 Queue 를 이용하여 유닉스의 history 명령어를 구현한 것이다.

 

PriorityQueue 는 Queue 인터페이스의 구현체 중 하나로, 우선 순위에 따라 저장되는 queue 이다. null 은 저장할 수 없고, 저장 공간으로 배열을 사용하며, 각각의 요소를 heap 형태로 저장한다. heap 은 이진 트리의 한 종류로 max 값이나 min 값을 효율적으로 찾을 수 있다.

Deque(Double-Ended Queue) 는 양방향 Queue 이다.

4. Interator, ListIterator, Enumeration

  컬렉션에 저장된 요소를 접근하는데에 사용하는 인터페이스이다. Enumeration 은 Iterator 의 구버전이고, ListIterator 은 Iterator 을 보다 개선한 것이다.

 

  Collections framework 에는 Iterator 인터페이스로 저장된 요소를 읽어오는 방법을 표준화하였다.

 

public interface Iterator{

boolean hasNext();

Object next();

void remove();

}

 

map 인터페이스를 구현한 Collection class 는 key-value 를 pair 로 저장하기 때문에 iterator 을 직접 호출할 수 없다. 대신 keySet() 이나 entrySet() 메서드를 이용하여 key 와 value 를 각각 set 의 형태로 얻어온 뒤에 iterator 를 호출하는 것이 가능하다.

import java.util.ArrayList;
import java.util.Iterator;

class source{
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        Iterator it = list.iterator();

        while(it.hasNext()){
            Object obj = it.next();
            System.out.println(obj);
        }
    }
}

ListIterator 은 단방향 순회만 가능한 Iterator 을 개선하여 양방향 순회가 가능한데 다만 ArrayList 나 LinkedList 처럼 List 인터페이스를 구현한 컬렉션에 대해서만 사용이 가능하다. 

import java.util.ArrayList;
import java.util.ListIterator;

class source{
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");

        ListIterator it = list.listIterator();

        while(it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println();

        while(it.hasPrevious()){
            System.out.println(it.previous());
        }
        System.out.println();
    }
}

import java.util.ArrayList;
import java.util.Iterator;

public class source{
    public static void main(String[] args) {
        ArrayList original = new ArrayList(10);
        ArrayList copy1 = new ArrayList(10);
        ArrayList copy2 = new ArrayList(10);

        for(int i=0; i<10; i++)
            original.add(i+"");
        Iterator it = original.iterator();

        while(it.hasNext())
            copy1.add(it.next());

        System.out.println("= copy from Original to copy1 =");
        System.out.println("original:" + original);
        System.out.println("copy1:" + copy1);
        System.out.println();

        it = original.iterator();

        while(it.hasNext()){
            copy2.add(it.next());
            it.remove();
        }

        System.out.println("= move from original to copy2 = ");
        System.out.println("original:" + original);
        System.out.println("copy2:" + copy2);
    }
}

iterator 의 remove() 는 특정 위치의 요소가 아닌 읽어온 것을 삭제하는 것에 유의하자.

5. Arrays

  Arrays 클래스에는 배열을 다루는 데에 유용한 메서드가 정의되어 있다. 

배열의 복사 : copyOf(), copyOfRange()

배열 채우기 : fill(), setAll()

배열의 정렬과 검색 : sort(), binarySearch()

배열의 비교와 출력 : equals(), toString(), deepToString(), deepEquals()

  * 다차원 배열을 equals() 로 비교하면 배열의 주소를 비교하므로 false 가 반환되므로 deepEquals() 를 사용할 것.

배열을 List 로 변환 : asList(Object... a)

  * 예시)  List list = Arrays.asList(new Integer[]{1,2,3,4,5});  

               List list2 = Arrays.asList(1,2,3,4,5);

 * 다만 asList 로 얻은 List 는 크기를 변경할 수 없다. 크기를 변경하고자 한다면 아래와 같이 선언할 것.

              List list = new ArrayList(Arrays.asList(1,2,3,4,5));

parallelXXX(), spliterator(), stream()

:   parallel 로 시작하는 메서드들은 보다 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어서 처리한다. spliterator() 은 여러 쓰레드가 처리할 수 있도록 하나의 작업을 여러 작업으로 나누는 Spliterator 을 반환한다. stream 은 컬렉션을 스트림으로 변환한다.

 

6. Comparator and Comparable

  Arrays.sort() 는 Character 클래스의 Comparable 의 구현으로 부터 가능했던 것이다. Comparator 와 Comparable 은 interface 로 collection 을 sorting 하는데에 필요한 메서드를 정의하고 있는데, Comparable 을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들이며 기본적으로 오름차순으로 정렬되도록 구현되어 있다. 그래서 Comparable 을 구현한 클래스는 sorting 이 가능하다는 것이다. 

 

public interface Comparaotr{

int compare(Object o1, Object o2);

boolean equals(Object obj);

}

public interface Comparable{

public int compareTo(Object o);

}

 

  compare() 와 compareTo() 는 같은 기능을 목적으로 고안된 것이다. 

 

public final class Integer extends Number implements Comparable {

...

public int compareTo(Object o){

return compareTo((Integer)o);

}

public int compareTo(Integer anotherInteger){

int thisVal = this.value;

int anotherVal = anotherInteger.value;

return (thisVal<anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));

   }

...

}

  Integer 클래스를 보면 Comparable 인터페이스의 compareTo(Object to) 을 구현한 것을 알 수 있다. Comparable 을 구현한 클래스들은 기본적으로 오름차순 정렬이 되어있지만, 다른 기준으로 정렬하고자 할 때에는 Comparator 을 구현해서 정렬 기준을 만들 수 있다.

import java.util.Arrays;
import java.util.Comparator;

public class source{
    public static void main(String[] args) {
        Integer[] arr = {1,2,3,4,5};

        Arrays.sort(arr, new Comparator<Integer>(){
            @Override
            public int compare(Integer i1, Integer i2){
                return i2-i1;
            }
        });

        print(arr);
    }
    public static void print(Integer[] arr){
        System.out.print("arr :");
        for(int ele : arr){
            System.out.print(ele + " ");
        }
    }
}

7. HashSet

    HashSet 에 새로운 요소를 추가할 때에는 add 나 addAll 을 사용하는데, 이미 저장된 요소와 중복된 요소를 추가하려고 한다면 false 를 반환한다. HashSet 은 저장순서를 유지하지 않으므로, 만약 저장순서를 유지하고자 한다면 LinkedHashSet 을 사용하여야 한다. 

import java.util.HashSet;
import java.util.Set;
class source{
    public static void main(String[] args) {
        Object[] arr = {"1", 1, "2", "2", "3", "3", "4", "4", "4"};
        Set set = new HashSet();

        for(int i = 0 ; i < arr.length; i++){
            set.add(arr[i]);
        }
        System.out.println(set);
    }
}

 

만약 중복을 제거함과 동시에 저장 순서를 유지하고자 한다면 LinkedHashSet 을 사용하면 된다.

import java.util.*;

class source{
    public static void main(String[] args) {
        Set set = new HashSet();
        for(int i = 0 ; set.size()<6; i++){
            int num = (int)(Math.random()*45)+1;
            set.add(num);
        }
        List list = new LinkedList(set); // LinkedList(Collection c)
        Collections.sort(list);
        System.out.println(list);
    }
}

아래는 1~50 의 숫자 중, 중복없이 25개를 골라서 5 by 5 matrix 로 만들어 출력하는 예제이다. 

import java.util.*;

class source {
    public static void main(String[] args) {
        Set set = new LinkedHashSet();
        int[][] board = new int[5][5];

        for (int i = 0; set.size() < 25; i++) {
            set.add((int) (Math.random() * 50) + 1 + "");
        }
        Iterator it = set.iterator();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                board[i][j] = Integer.parseInt((String) it.next());
                System.out.print((board[i][j] < 10 ? "  " : " ") + board[i][j]);
            }
            System.out.println();
        }
    }
}

아래의 Person 클래스를 요소로 가지는 HashSet 을 살펴보자.

import java.util.HashSet;

class source {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        set.add("abc");
        set.add("abc");
        set.add(new Person("David", 10));
        set.add(new Person("David", 10));

        System.out.println(set);
    }
}
class Person{
    String name;
    int age;

    Person(String name, int age){
        this.name = name;
        this.age = age;
    }
    public String toString(){
        return name +":"+ age;
    }
}

실행결과를 보면 예상과는 달리 David:10 이 중복되어 저장된 것을 볼 수 있다. HashSet 메서드의 add 메서드는 새로운 요소를 추가할 때, 기존 저장된 요소와 같은지 판별하기 위해 추가하려는 요소의 equals() 메소드와 hashCode() 를 호출해서 이에 대한 오버라이딩을 해주어야 의도대로 동작한다.

import java.util.HashSet;

class source {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        set.add("abc");
        set.add("abc");
        set.add(new Person("David", 10));
        set.add(new Person("David", 10));

        System.out.println(set);
    }
}
class Person{
    String name;
    int age;

    Person(String name, int age){
        this.name = name;
        this.age = age;
    }
    public String toString(){
        return name +":"+ age;
    }
    public boolean equals(Object obj){
        if(obj instanceof Person){
            Person tmp = (Person) obj;
            return name.equals(tmp.name) && age==tmp.age;
        }
        return false;
    }
    public int hashCode(){
        return (name+age).hashCode();
    }
}

  오버라이딩을 통해 작성한 hashcode() 메서드는 아래의 3 가지 사항을 만족해야한다.

 

1. 실행중인 application 내 동일한 객체에 대해 hashCode() 를 여러 번 호출 하더라도 동일한 int 값을 반환해야 한다. 하지만, 실행시마다 동일한 int 값을 반환할 필요는 없다. (단, equals 메서드의 구현에 사용한 멤버변수의 값이 바뀌지 않았다고 가정함.)

 

2. equals 메서드를 이용한 비교 연산에 의해 true 를 얻은 두 객체에 대하여 각각 hashCode() 를 호출해서 얻은 결과는 반드시 같아야 한다.

 

3. equals 메서드를 호출했을 때 false 를 반환하는 두 객체는 hashcode() 호출에 대해 같은 int 값을 반환하는 경우가 발생해도 되지만, hashing 을 사용하는 collection 의 성능을 향상시키기 위해선 반드시 다른 int 값을 반환하도록 하는 것이 좋다.

8. TreeSet

   TreeSet 은 바이너리트리 형태로 데이터를 저장하는 Collection class 이다. 바이너리 트리는 sorting, searching, range searching 에 높은 성능을 보이며, TreeSet 은 바이너리 트리를 개선시킨 Red - Black Tree 구조로 되어있다. Set 인터페이스를 구현한 것이므로 중복을 허용하지 않으며, 저장 순서도 유지하지 않는다. 

import java.util.TreeSet;

class source {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        int[] score = {80, 95, 50, 35, 45, 65, 10, 100};

        for(int i=0; i<score.length; i++)
            set.add(score[i]);

        System.out.println("less than 50 : " + set.headSet(50));
        System.out.println("bigger than 50 : " + set.tailSet(50));
    }
}

headSet 메서드와 tailSet 메서드를 이용하면 기준 값보다 큰/작은 객체들을 얻을 수 있다.

9. HashMap  

 HashMap 은 Map 을 구현한 것으로 key-value 형태의 값을 데이터로 저장한다. 또한 hashing 을 사용하므로 검색에 있어서 뛰어난 성능을 보인다. 

 

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable{

trainsient Entry[] table;

...

static class Entry implements Map.Entry{

final Object key;

Object value;

...

     }

}

 

 위는 실제 소스코드의 일부인데,  Entry 라는 inner class 를 정의하고 Entry 타입의 배열을 선언하고 있다. key - value 형태의 데이터이기 때문에 하나의 클래스로 정의해서 다루는 것이 data integrity 측면에서 바람직하기 때문이다.

import java.util.HashMap;
import java.util.Scanner;

class source {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("myId", "1234");
        map.put("asdf", "1111");
        map.put("asdf", "1234");

        Scanner s = new Scanner(System.in);

        while (true) {
            System.out.println("Enter Id, password");
            System.out.print("id :");
            String id = s.nextLine().trim();

            System.out.print("password :");
            String password = s.nextLine().trim();
            System.out.println();

            if (!map.containsKey(id)) {
                System.out.println("there is no id, please enter again.");
                continue;
            }
            if (!(map.get(id)).equals(password)) {
                System.out.println("Passwords do not match, please try again.");
            } else {
                System.out.println("success!!");
                break;
            }
        }
    }
}

맨 처음에 asdf 라는 key 를 중복해서 넣었기 때문에, 마지막에 put 한 key-value 만 살아남는다.

import java.util.*;

class source {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("Kim", 100);
        map.put("Lee", 100);
        map.put("Kang", 100);
        map.put("Ahn", 100);

        Set set = map.entrySet();
        Iterator it = set.iterator();

        while(it.hasNext()){
            Map.Entry e = (Map.Entry)it.next();
            System.out.println("name : " + e.getKey() + "score : " + e.getValue());
        }

        set = map.keySet();
        System.out.println("participant list : " + set);

        Collection values = map.values();
        it = values.iterator();

        int total = 0;
        while(it.hasNext()){
            Integer i = (Integer)it.next();
            total += i.intValue();
        }

        System.out.println("total : " + total);
        System.out.println("average : " + (float)total/set.size());
        System.out.println("max : " + Collections.max(values));
        System.out.println("min : " + Collections.min(values));
    }
}

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

class source {
    static HashMap phoneBook = new HashMap();
    public static void main(String[] args) {
       addPhoneNo("Friend", "Lee", "010-1111-1111");
       addPhoneNo("Friend", "Ki", "010-1121-1141");
       addPhoneNo("Friend", "Kim", "010-3111-1111");
       addPhoneNo("Job", "Ted", "010-5111-1111");
       addPhoneNo("Job", "James", "010-6111-1111");
       addPhoneNo("Job", "Travis", "010-7111-1111");
       addPhoneNo("Job", "Gael", "010-8111-1111");
       addPhoneNo("Food", "KFC", "010-9111-1111");

       printList();
    }
    static void addPhoneNo(String groupName, String name, String tel){
        addGroup(groupName);
        HashMap group = (HashMap)phoneBook.get(groupName);
        group.put(tel, name);
    }
    static void addGroup(String groupName){
        if(!phoneBook.containsKey(groupName))
            phoneBook.put(groupName, new HashMap());
    }
    static void addPhoneNo(String name, String tel){
        addPhoneNo("etc", name, tel);
    }
    static void printList(){
        Set set = phoneBook.entrySet();
        Iterator it = set.iterator();

        while(it.hasNext()){
            Map.Entry e = (Map.Entry)it.next();

            Set subSet = ((HashMap)e.getValue()).entrySet();
            Iterator subIt = subSet.iterator();

            System.out.println(" * " + e.getKey()+"[" + subSet.size() + "]");

            while(subIt.hasNext()){
                Map.Entry subE = (Map.Entry)subIt.next();
                String telNo = (String)subE.getKey();
                String name = (String)subE.getValue();
                System.out.println(name + " " + telNo);
            }
            System.out.println();
        }
    }
}

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

class source {
    static HashMap phoneBook = new HashMap();
    public static void main(String[] args) {
        String[] data = {"A", "B", "C", "D", "E", "F", "G", "A", "A", "B", "C", "G", "A", "A", "A"};

        HashMap map = new HashMap();

        for(int i=0; i<data.length; i++){
            if(map.containsKey(data[i])){
                Integer value = (Integer) map.get(data[i]);
                map.put(data[i], value.intValue() +1);
            } else {
                map.put(data[i], 1);
            }
        }
        Iterator it = map.entrySet().iterator();

        while(it.hasNext()){
            Map.Entry entry = (Map.Entry)it.next();
            int value = ((Integer)entry.getValue()).intValue();
            System.out.println(entry.getKey() + " : " + printBar('#', value) + " " + value);
        }
    }

    public static String printBar(char ch, int value){
        char[] bar = new char[value];

        for(int i=0; i<bar.length; i++)
            bar[i] = ch;

        return new String(bar);
    }
}

  String 배열인 data 를 순회하며, 현재 HashMap 에 data[i] 와 중복되는 key 가 없으면 map.put(data[i], new Integer(1)); 을 수행하고 만약 HashMap 에 data[i] 와 중복되는 key 가 존재하면 value 를 얻어오고, value 에 1 을 더한 값을 value 로 해서 다시 put 해준다. 그러면 HashMap 에는 data 배열의 원소의 빈도가 저장되며 이를 iterator 을 이용하여 순회하는데, printBar 함수를 이용해서 그래프를 그려주는 예제이다. 

 

[ Hash Function ]

  Hashing 을 구현한 컬렉션 클래스는 HashSet, HashMap, Hashtable 등이 있으며 Hashtable 은 collections framework 가 도입되며 HashMap 으로 대체되었으나, 이전에 작성된 코드와의 호환을 위해 남아있는 것이다. 

10. TreeMap

   바이너리서치트리 형태로 key-value 의 pair 데이터를 저장하므로 검색과 정렬에 적합한 클래스이다. 다만 검색 성능에 관해서는 HashMap 이 TreeMap 보다 대부분 우수하므로 HashMap 을 사용하는 것이 좋다. range search 나 sorting 의 경우에는 TreeMap 이 우수하다.

 

11. Properties

   Hashtable 을 상속받아 구현한 것으로 key - value 값을 String, String 형태로 저장한다. 어플리케이션의 환경설정과 관련된 property 를 저장하는데에 주로 사용되며 데이터를 파일로부터 읽고 쓰는 편리한 기능을 제공한다. 

import java.util.Enumeration;
import java.util.Properties;

class source{
    public static void main(String[] args) {
        Properties prop = new Properties();

        prop.setProperty("timeout", "30");
        prop.setProperty("language", "kr");
        prop.setProperty("size", "10");
        prop.setProperty("capacity", "10");

        Enumeration e = prop.propertyNames();

        while(e.hasMoreElements()){
            String element = (String)e.nextElement();
            System.out.println(element + "=" + prop.getProperty(element));
        }

        System.out.println();
        prop.setProperty("size", "20");
        System.out.println("size=" + prop.getProperty("size"));
        System.out.println("capacity=" + prop.getProperty("capacity", "20"));
        System.out.println("load-factor=" + prop.getProperty("load-factor", "0.75"));

        System.out.println(prop);
        prop.list(System.out);
    }
}

12. Collections

   Collections 클래스는 컬렉션과 관련된 fill, copy, sort, binarySearch 등의 메서드를 제공한다. multi-thread 프로그래밍에서 하나의 객체를 여러 thread 가 동시에 접근할 수 있어서 data inconsistency 를 위해서는 공유되는 객체에 synchronization 을 해주어야 한다. Vector, Hashtable 은 자체적으로 동기화 처리가 되어있지만 multi-threading 을 사용하지 않는 경우에는 성능을 저하시키는 요인이 되므로, JAVA 에 새로 추가된 ArrayList 와 HashMap 등은 동기화 처리가 되어있지 않은데, 이는 필요한 경우에만 java.util.Collections 에서 Synchronization 메서드를 이용해서 처리해주도록 하기 위함이다. 

  또한 컬렉션의 데이터를 보호하기 위해 read - only 로 만들어야 할 경우가 발생하는데 이는 Collection 의 unmodifiable... 메서드를 사용하면 된다. 그리고 오직 하나의 객체만 저장하는 컬렉션(싱글톤 컬렉션)을 만들고자 할 때에는 singleton... 메서드를 사용하면 된다. 컬렉션에 한 종류의 객체만 저장하도록 하는 경우에는 checked ... 메소드를 사용하면 된다. 

---

References

http://www.yes24.com/Product/Goods/24259565

Java의 정석 - YES24