[Java] 컬렉션 프레임워크(Collections Framework)

 

Collections Framework

💡Collections vs. Collection
- Collections : util 클래스

Collections.sort(list);​

 

- Collection  : 인터페이스

 

Collections

컬렉션을 위한 메서드(static)를 제공

💡 유용한 static 메서드를 제공하는 클래스
- Object : 객체
- Arrays : 배열
- Collections : 컬렉션

 

 

 

 

 

 

List

* ArrayList

연속적인 배열

장점 : 구조가 간단하고 데이터를 읽는 데 걸리는 시간이(접근 시간, access time)이 짧다.

단점 :

- 크기를 변경할 수 없다.(크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야함.

크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.)

- 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다. (그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

 

 

* LinkedList

불연속적 배열(참조로 이루어짐)

배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(Link)

장점 : 데이터 삭제(단 한 번의 참조 변경만으로 가능), 데이터 추가(한 번의 Node객체 생성과 두 번의 참조변경만으로 가능)

단점 : 연결리스트. 데어터 접근성이 나쁨

배열처럼 한 번에 데이터를 접근할 수 있는 게 아님. 불연속적이기 때문에

 

Doubly Linked List - 이중 연결 리스트

이중 연결리스트, 접근성 향상

연결을 앞뒤로 하고 있음.

배열보다 접근성은 여전히 낮음

 

Doubly Circular Linked List 이중 원형 연결리스트

원형으로 되어 있어서 다시 맨앞으로 갈 수 있음

 

 

1. 순차적으로 데이터 추가/삭제 - ArrayList가 빠름

2. 비순차적으로 데이터를 추가/삭제 - LinkendList가 빠름

3. 접근시간(access time) - ArrayList가 빠름

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

 

컬렉션	읽기(접근시간)	추가 / 삭제	비 고
ArrayList	빠르다	느리다	- 순차적인 추가/삭제는 빠름 - 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을 수록 접근성이 떨어짐

 

 

 

Stack과 Queue

 

 

Iterator, ListIterator, Enumeration

컬렉션에 저장된 데이터를 접근(읽어오기)하는데 사용되는 인터페이스

컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것

컬렉션에 iterator()를 호출해서 iterator를 구현한 객체를 얻어서 사용

ArrayList list  = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");

ListIterator it = list.literator(); // 1회용

while(it.hasNext()) { // boolean hasNext() : 읽어올 요소가 있는 확인. 
	System.out.print(it.next()); // Object next() : 읽어온다.
    // 순방향으로 진행하면서 읽어온다.
}

while(it.hasPrevious()) {
	System.out.print(it.next()); 
    // 역방향으로 진행하면서 읽어온다.
}


// 💡 삭제
// Iterator의 remove()는 단독으로 쓰일 수 없고, next()와 같이 써야한다.
// 특정위치의 요소를 삭제하는 것이 아니라 읽어 온 것을 삭제한다.
// next() 호출없이 remove()를 호출하면, IllgalStateException이 발생한다.
ListIterator it = list.literator(); // Iterator은 재사용이 안되므로,다시 얻어와야 한다.(1회용)

ArrayList copy = new ArrayList(5);

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

 

 

Set

HashSet

- Set 인터페이스를 구현한 가장 대표적인 컬렉션이며, Set 인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다.

- 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.

- HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인한다.

같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.

for(int i = 0; i < objArr.length; i++){
    set.add(objArr[i]);
    // true/false 인지 결과가 나온다.이것이 같은 객체가 있는지 확인하는 것이다.
}
system.out.printIn(set);

- boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출한다.

equals()와 hashCode()가 오버라이딩되어 있어야 한다.

 

 

 

TreeSet - 범위 탐색, 정렬

- 이진 탐색(검색) 트리(binary search tree)로 구현. 범위 탐색(from~to)과 정렬에 유리하다.

- 이진 트리는 모든 노드가 최소 0개에서 최대 2개의 하위노드를 갖는다. (하위노드가 2개를 가질 수 있기 때문에 이진(binary) 트리이다.

- 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)한다. (요소 하나하나를 node라고 한다.)

- 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다. (이런 순서가 없으면, 그냥 '이진트리'이다.)

단점

- 데이터가 많아 질수록 추가/삭제에 시간이 더 걸린다.(비교 횟수가 증가하기 때문에)

장점

- 대신 배열이나 LinkedList에 비해 검색과 정렬기능이 더 뛰어나다.

💡 TreeSet은 저장할 때 이미 정렬하기 때문에 잃어올때 따로 정렬할 필요가 없다.

 

💡데이터 저장 비교 boolean add(Object o)
- TreeSet은 compare()를 호출해서 비교
- HashSet은 equals(), hashCode()로 비교
-> 비교 방법을 안알려 주면, 오류가 뜬다.

 

 

 

 

Map

HashMap, Hashtable

- 순서X, 중복(키X, 값O)

 

 

💡해싱(Hashing)이란

해시함수(Hash Function)를 이용하여 해시 테이블(Hash Table)에 데이터를 저장하는 방법이다.

해싱에서 사용하는 자료구조는 배열과 링크드리스트의 조합이며, 자세히 보면 배열의 요소안에 링크드 리스트가 저장되어 있는 구조이다.

💡 해시 테이블(Hash Table)

- 해시 테이블은 배열(접근성이 좋다)과 링크드 리스트(변경에 유리하다)가 조합된 형태.

- 2차원 배열처럼 생겨서 테이블이라고 한다.

- 아래 이미지에서 왼쪽이 효율이 안좋은 해시테이블, 오른쪽이 이상적인 해시테이블이라고 할 수 있다.
- 오른쪽의 해시테이블은 링크드리스트가 각 방마다 1개씩 있는 형태를 가지기 때문에, 검색속도가 매우 뛰어나다.
- 이러한 해시테이블을 구현하기 위해서 가장 중요한 것은 해시함수이다.
- 해시함수가 각각의 key마다 다른 해시코드를 반환하도록 구현한다면, 이상적인 해시테이블의 구조를 구현할 수 있을 것이다.

출처 : 자바의 정석

 

💡해시테이블에 저장된 데이터를 가져오는 과정
1. 키로 해시함수를 호출해서 해시코드를 얻는다.
2. 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다.
3. 링크드리스트에서 키와 일치하는 데이터를 찾는다.
** 해시함수는 같은 킹 대해 항상 같은 해시코드를 반환해야 한다.
** 서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.

 

 

 

참고 : https://kor-shin.github.io/java/hashing/

해싱(Hashing)과 해시함수(Hash Function)

 

 

 

 

 

💡데이터 저장
- List와 Set은 boolean add(Object o)로 저장.
- Map은 Object put(Object key, Object vaule)로 저장.