23장 자바랭 다음으로 많이 쓰는 애들은 컬렉션 - Part2(Set과 Queue)

▩ 목 차 ▩

1. set이 왜 필요할까 ? 

 

2. HashSet에 대해서 파헤쳐 보자 [Set]

      2-1. HashSet의 생성자들도 여러 종류가 있다.

      2-2. HashSet의 주요 메소드를 살펴보자

 

3. Queue는 왜 필요할까 ? [LinkedList]

      

4. LinkedList를 파헤져 보자

      4-1. LinkedList의 생성자와 주요 메소드를 살펴보자 [ addfirst(), add() ,getfirst(), getlast(), contains(), indexOf() , remove() ]

      4-1-1 . LinkedList에 데이터(값)를 추가하는 메소드 [ addfirst(), add() ]

      4-1-2 . LinkedList에 데이터(값) 특정 위치의 데이터를 꺼내는 메소드들 [getfirst(), getlast() ]

      4-1-3 . LinkedList에 어떤 객체가 포함되어 있는지를 확인하는 메소드 [ contais(), indexOf, lastIndexOf ]

      4-1-4 . LinkedList 객체에서 삭제하고, 데이터를 리턴해주는 메소드 [ remove() ]

      4-1-5 . LinkedList 객체를 하나씩 검색하기 위한 Iterator 객체

 

5. 정리

---

■ 1. set이 왜 필요할까 ? ■

 

Collection을 확장한 배열과 비슷한 역할을 하는 3개의 인터페이스가 있다고 했다. 바로 List, Set, Queue다.

여기서 List는 순서가 중요한 데이터를 담을 때 사용된다.

set은 어디서 사용되는 것일까?

==> Set은 순서에 상관없이, 어떤 데이터가 존재하는지를 확인하는 용도로 많이 사용된다. 즉, 중복되는 것을 방지하고, 원하는 값이 포함되어 있는지를 확인하는 것이 주 용도다.

[ 예를 들어, 어떤 서버에 1분간 사용자가 요청한 로그가 있다고 가정하자. 이 서버에 붙어서 요청한 IP를 기준으로 사용자의 수가 얼마나 되는지 확인한다고 가정해보면, 1분간 동일한 서버에 요청하는 중복 사용자의 수는 매우 많다. 이러한 경우에 배열로 확인하려고 한다면, IndexOf()메소드로 해당 객체가 존재하는지 확인 한 후, add() 메소드로 추가하는 작업을 반복해야만 한다.

하지만, Set을 구현한 클래스를 사용한다면 자동으로 데이터가 중복되지 않고 저장된다. 이 때 각 사용자가 사용한 IP의 순서는 중요하지 않다. ]

 

자바에서 Set 인터페이스를 구현한 주요 클래스는 HashSet, TreeSet, LinkedHashSet이 있다.

• HashSet : 순서가 전혀 필요없는 데이터를 해시 테이블에 저장한다. Set 중에 가장 성능이 좋다.
• TreeSet : 저정된 데이터의 값에 따라서 정렬되는 셋이다. red-black이라는 트리타입으로 값이 저장되며, HashSet보다 약간 성능이 느리다.
• LinkedHashSet : 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라서 값이 정렬된다. 대신 성능이 이 셋 중에서 가장 나쁘다.

==> 이러한 성능 차이가 발생하는 이유는 데이터 정렬 때문이다. HashSet이 가장 성능이 좋은 이유는 별도의 정렬 작업이 없기때문이다.

 

red-black 트리는 각 노드의 색을 붉은색 혹은 검은색으로 구분하여 데이터를 빠르고, 쉽게 찾을 수 있는 구조의 이진트리를 말한다.

 

우리는 Set을 구현한 여러 클래스 중에서 HashSet을 자세히 살펴보자.

 

---

■ 2. HashSet에 대해서 파헤쳐 보자 [Set] ■

 

먼저 HashSet 클래스의 상속 관계를 보자

AbstractCollection을 확장한 것은 ArrayList와 동일하다. 하지만, HashSet은 AbstactSet을 확장했다.

AbstractSet 클래스는 이름 그대로 abstact 클래스이다. 구현되어 있는 메소드는 Object 클래스에 선언되어 있는 equals(), hashCode()메소드와 이 클래스(AbstractSet)에서 추가한 removeAll()뿐이다.

 

Set은 무엇보다도 데이터가 중복되는 것을 허용하지 않으므로, 데이터가 같은지 확인하는 작업은 Set의 핵심이다.

equals()와 hashCode()메소드를 구현하는 부분은 Set에서 매우 중요하다. 추가로 removeAll()메소드는 컬렉션을 매개변수로 받아, 매개 변수 컬렉션에 포함된 모든 데이터를 지울 때 사용한다.(ArrayList의 removeAll()메소드와 같음)

 

상속관계를 보았으니 HashSet이 어떤 인터페이스를 구현 했는지 보자.

각 인터페이스에 대해서 List의 인터페이스 구현과 동일하니 넘어가도록 하겠다.

여기서 Set 인터페이스에 정의되어 있는 메소드는 대부분 List와 비슷하다.

그렇다면 List에 정의되어 있지만, Set에 정의되어 있지 않은 메소드는 어떤 것이 있을까?

==> Set은 순서가 없다. 따라서, 순서가 매개변수로 넘어가는 메소드는 수행결과가 데이터의 위치와 관련된 메소드는 필요 없다.

그러므로 get(int index)나 indexOf(Object o)와 같은 메소드들은 Set에 존재하지 않는다.

---

■ 2-1. HashSet의 생성자들도 여러 종류가 있다.

위에서 자주 나오는 로드 팩터라는 것은 뭘까?

==> 로드팩터는 (데이터의 개수)/(저장공간)을 의미한다. 만약, 데이터의 개수가 증가하여 로드 팩터보다 커지면, 저장 공간의 크기는 증가되고 해시 재정리 작업을 해야만 한다. 데이터가 해시 재정리 작업에 들어가면, 내부에 갖고 있는 자료 구조를 다시 생성하는 단계를 거쳐야 하므로 성능에 영향이 발생한다.

 

로드 팩터라는 값이 클수록 공간은 넉넉해지지만, 데이터를 찾는 시간이 증가한다.

==> 따라서, 초기 공간 개수와 로드 팩터는 데이터의 크기를 고려하여 산정하는 것이 좋다. 왜냐하면 초기 크기가 (데이터의 개수)/(로드 팩터) 보다 클 경우에는 데이터를 쉽게 찾기 위한 해시 재정리 작업이 발생하지 않기 때문이다. 따라서, 대량의 데이터를 담아 처리할 때에는 초기 크기와 로드 팩터의 값을 조절해 가면서 가장 적당한 크기를 찾아야만 한다.

[ 대부분의 초급 개발자들은 로드 팩터를 건드릴 필요가 거의 없으므로, 매개 변수가 없는 생성자를 사용하거나 초기 크기만 지정하는 생성자를 사용하면 된다. ]

---

■ 2-2. HashSet의 주요 메소드를 살펴보자

HashSet에 선언되어 있는 메소드는 많지 않다. 부모 클래스인 AbstarctSet과 Collection에 선언 및 구현되어 있는 메소드를 그대로 사용하는 경우가 많다.

 

예를 들어, 어느 회사에 직원들이 보유하고 있는 차의 종류가 몇 개나 되는지 확인해보려고 한다. 어떻게 하면 직원들의 차 종류의 개수를 쉽게 확인해 볼 수 있을까?

[EX] - 배열의 데이터 개수 확인 [ 데이터 중복 가능 ]

package part23;

import java.util.ArrayList;

public class SetSample {

	public static void main(String[] args) {
		SetSample sample = new SetSample();
		String cars[] = new String[] {
				"Tico","Sonata","BMW","Benz"
				,"Lexus","Mustang","Grandeure"
				,"The Beetle","Mini Cooper","i30"
				,"BMW","Lexux","Carnibal","SM5"
				,"SM7","SM3","Tico" };
		sample.getCarKinds(cars);
		}
	
	public void getCarKinds(String[] cars) {
		int count = 0;
		
		for(String tempdata : cars) {
			count++;
		}
		System.out.println(count);
		
//		return count;
		
	}
}

17

나였으면 이렇게 코드를 짰을 것이다. 또는 아래와 같이 짰을 것이다. 

[EX] -  ArrayList에 배열의 데이터를 넣고 size()메소드를 이용하여 배열의 데이터 개수 확인 [ 데이터 중복 가능 ]

	public void getCarKinds(String[] cars) {

		ArrayList<String> list = new ArrayList<String>();
		for(String car : cars) {
			list.add(car);
		}
		System.out.println(list.size());

		
	}

 

위 아래의 코드 결과는 17. 즉, 중복을 처리하지 않았다. 어떻게 중복을 처리하면서 데이터를 처리하는 코드를 짤까?

[EX] - Set을 이용하여 데이터 중복 안되게 처리

	public int getCarKinds2(String[] cars) {
		if(cars==null) {
			return 0; //1
		}
		if(cars.length==1) {
			return 1; //2
		}
		Set<String> carSet = new HashSet<String>(); //3
		for(String car:cars) { //4
			carSet.add(car);
		}
		return carSet.size(); //5
	}

위 코드의 숫자 주석을 보자.

1. 가장 먼저 cars라는 배열이 null 인지를 확인했다. 이 확인 작업을 수행하지 않으면, null인 배열을 매개 변수로 받을 경우 NullPointerException이 발생한다.
2. cars 배열의 크기가 1인지를 확인했다. 만약 배열의 크기가 1이면, 확인할 필요도 없이 결과도 1이기 때문이다.
3. carSet이라는 HashSet 객체를 생성했다.
4. 생성한 CarSet객체에 cars 배열의 값들을 하나씩 담았다. 이렇게 하면, 중복된 값은 없고 유일한 자동차 이름만 남는다.
5. carSet의 크기를 리턴했다.

위와 같이 HashSet과 같은 Set을 이용하면 여러 중복되는 값을들을 걸러내는데 매우 유용하다.

 

그러면 HashSet에 저장되어 있는 값을 어떻게 꺼낼까?

==> 가장 편한 방법은 for each루프(콜론)를 사용하는 것이 편하다.

[EX] - for 루프(콜론)을 이용하여 HashSet에 저장되어 있는 값을 꺼내기

	public void printCarSet(Set<String> carSet) {
		for(String temp:carSet) {
			System.out.println(temp);
		}

	public int getCarKinds2(String[] cars) {
		if(cars==null) {
			return 0; //1
		}
		if(cars.length==1) {
			return 1; //2
		}
		Set<String> carSet = new HashSet<String>(); //3
		for(String car:cars) { //4
			carSet.add(car);
		}
		System.out.println("total count : " + carSet.size());
		printCarSet(carSet);
		return carSet.size(); //5
	}

total count : 15
Mustang
Lexus
Tico
i30
Grandeure
Carnibal
Sonata
BMW
Benz
SM3
The Beetle
SM5
Mini Cooper
Lexux
SM7

위의 코드를 보자.

printCarSet()이라는 메소드는 Set 객체를 매개변수로 받고 이 매개변수로 받은 Set 객체를 for(콜론)을 통해 안에 있는 데이터들을 출력하는 메소드다. 이 printCarSet()를  getCarKinds2()라는 메소드에서 만든 CarSet객체를 printCarSet()메소드의 매개변수로 전달하는 로직이다. 

결과를 보게 되면 Set에 저장한 순서대로 출력되지도 않고, 뒤죽박죽으로 출력된 것을 볼 수 있다. 계속해서 얘기하지만, Set은 데이터가 보관되어 있는 순서가 전혀 중요하지 않을 때 사용해야만 한다.

데이터를 출력하는 방법은 한가지만 존재하는 것은 아니다.

==> Iterator 객체를 얻어서 사용하면 된다.

[EX] - Iterator 객체를 이용하여 Set 객체의 데이터 출력하기 [ while문을 이용하고 iterator클래스의 hasNext(), next() 메소드 사용]

	public void printCarSet2(Set<String> carSet) {
		Iterator<String> iterator = carSet.iterator(); //1
		while(iterator.hasNext()) { //2
			System.out.println(iterator.next()); //3
		}
		System.out.println();
	}

total count : 15
Mustang
Lexus
Tico
i30
Grandeure
Carnibal
Sonata
BMW
Benz
SM3
The Beetle
SM5
Mini Cooper
Lexux
SM7

위의 코드에서 숫자 주석을 봐보자.

1. iterator()라는 메소드를 사용하여 Iteratior 객체를 생성한다.
2. while()문을 사용하여 다음 데이터가 존재하는지 haNext()라는 메소드를 사용하여 지속적으로 확인한다.
3. next() 메소드를 사용하여 다음 값을 얻어낸다.

 

[ 해당 객체가 HashSept에 존재하는지를 확인하기 위해서는 contains()메소드를, 해당 객체를 HashSet에서 삭제하기 위해서는 remove()메소드를 사용하면 된다. ]

---

■ 3. Queue는 왜 필요할까 ? [LinkedList] ■

 

[ 앞에서 소개만 된 LinkedList라는 클래스가 있다. LinkedList라는 것은 자료구조에 대해서 배울 때 중요한 항목 중 하나이기 때문에 꼭 기억하고 있어야만 한다. ]

 

LinkedList를 가장 쉽게 이해하려면 열차를 생각해보면 된다. 

LinkedList에 A라는 하나의 값이 추가되면 열차의 맨 앞칸에 데이터를 집어 넣는다. 이 때, LinkedList의 가장 앞의 값도 A이며, 가장 끝에 있는 값도 A다.

이 상태에서 B라는 데이터를 더 집어넣자. 그러면 가장 앞에 있는 값은 A고, 가장 뒤에 있는 값은 B다. 여기서, A는 뒤에 B가 있다는 것을 B는 A가 앞에 있다는 것을 기억하고 있는다.

그 다음에 C라는 값을 집어넣자. 그러면 가장 앞에는 A, 그 다음에는 B, 마지막에는 C가 위치한다.

그런데,  LinkedList에서는 앞에 있는 애와 뒤에 있는 애만 기억한다. 다시 말해서 A는 뒤에 있는 값이 B라는 것만 알고, C가 있다는 것은 생각도 안한다 그리고, C라는 애도 앞에 B라는 것만 기억한다.

왜 이렇게 복잡한 LinkedList라는 것을 쓸 필요가 뭐가 있을까 ?

==> 만약 간단하게 배열과 같이 데이터를 담아서 순차적으로 뺄 경우에는 별 필요가 없을 수가 있다. 하지만, 배열의 중간에 있는 데이터가 지속적으로 삭제되고, 추가될 경우에는 LinkedList가 배열보다 메모리 공간 측면에서 훨씬 유리하다.

왜냐하면, 배열과 같은 ArrayList와 Vector는 각 위치가 정해져 있고, 그 위치로 데이터를 찾는다. 그런데, 맨 앞의 값을 삭제하면, 그 뒤에 있는 값들은 하나씩 앞으로 위치를 이동해야 제대로 된 위치의 값을 가지게 된다.

그에 반해 LinkedList는 중간에 있는 데이터를 삭제하면, 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결하면 그만이다.

즉, 위치를 맞추기 위해서 값을 이동하는 단계를 거칠 필요가 없다는 것이다.

 

LinkedList는 List 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다.

즉, LinkedList 자체가 List 이면서 Queue, Deque도 된다. 이 중 Queue를 먼저 살펴보자.

 

Queue는 FIFO[Firest In First Out] (선입선출)용도로 사용한다. 즉, 먼저 들어온 애가 먼저 나간다.

 

그렇다면 큐는 왜 사용할까?

==> 예를 들어, 웹서버에 100명의 사용자가 요청을  했다고 가정하자. 만약 LIFO로 처리해서 사용자에게 응답을 해준다면, 가장 먼저 와서 줄 서 있는 사용자가 가장 마지막에 응답을 받게 되므로, 마음 상해서 더 이사 그 웹서버를 사용하지 않을 것이다.

 

---

■ 4. LinkedList를 파헤져 보자 ■

 

LinkedList의 상속관계를 살펴보자.

ArrayList 클래스나 Vector 클래스와 상속관계는 비슷하지만, AbstractSequentialList가 부모 인 것을 볼 수 있다.

AbstractList와 AbstractSequentialList의 차이점은 add(), set(), remove() 등의 메소드에 대한 구현 내용이 조금 다른 정도이다.

 

LinkedList 클래스가 구현한 인터페이스의 목록을 살펴보자.

LinkedList클래스는 List도 되고 Queue도 된다. 두 인터페이스의 기능을 모두 구현한 특이한 클래스라고 볼 수 있다. 게다가 Deque 인터페이스도 구현하므로, 맨 앞과 끝의 데이터를 쉽게 처리할 수 있다.

---

■ 4-1. LinkedList의 생성자와 주요 메소드를 살펴보자 [ addfirst(), add() ,getfirst(), getlast(), contains(), indexOf() , remove() ]

LinkedList는 일반적인 배열 타입의 클래스와 다르게 생성자로 객체를 생성할 때 처음부터 크기를 지정하지 않는다. 왜냐하면, 각 데이터들이 앞 뒤로 연결되는 구조이기 때문에, 미리 공간을 만들어 놓을 필요가 없는것이다. 

 

■ 4-1-1 . LinkedList에 데이터(값)를 추가하는 메소드 [ addfirst(), add() ]

LinkedList 클래스는 구현한 인터페이스의 종류가 매우 많기 때문에, 메소드의 종류도 다양하다. 살펴보자.

각 메소드의 이름을 보면, 매우 중복된 기능을 수행하는 메소드가 많은 것을 알 수 있다.

==> LinkedList가 여러 종류의 인터페이스를 구현했기 때문에 이러한 상황이 발생한 것이다.

 

[EX] - LinkedList에 데이터(값)를 추가하는 메소드

package part23;

import java.util.LinkedList;

public class QueueSample {

	public static void main(String[] args) {
		QueueSample sample = new QueueSample();
		sample.checkLinkedList1();

	}
	public void checkLinkedList1() {
		LinkedList<String> link = new LinkedList<String>();
		link.add("A");
		link.addFirst("B");
		System.out.println(link);
		link.offerFirst("C");
		System.out.println(link);
		link.addLast("D");
		System.out.println(link);
		link.offer("E");
		System.out.println(link);
		link.offerLast("F");
		System.out.println(link);
		link.push("G");
		System.out.println(link);
		link.add(0,"H");
		System.out.println(link);
		System.out.println("EX="+link.set(0, "I"));
		System.out.println(link);
	}

}

[B, A]
[C, B, A]
[C, B, A, D]
[C, B, A, D, E]
[C, B, A, D, E, F]
[G, C, B, A, D, E, F]
[H, G, C, B, A, D, E, F]
EX=H
[I, G, C, B, A, D, E, F]

자바의 LinkedList 소스를 보면 맨 앞에 추가하는 메소드는 동일한 기능을 수행하는 어떤 메소드를 호출해도 addFirst()메소드를 호출한다. 맨 뒤에 추가하는 메소드는 동일한 기능을 수행하는 offer()관련 메소드를 호출하면 add()나 addLast()를 호출하도록 되어 있다.

[ 따라서 여러 메소드를 혼용하여 사용하기 보다 소스 코드의 가시성을 위해 한가지만 선정해서 사용하자. addfirst(), add() 추천 ]

 

■ 4-1-2 . LinkedList에 데이터(값) 특정 위치의 데이터를 꺼내는 메소드들 [getfirst(), getlast() ]

 많은 메소드들이 있다. 여기서 맨 앞에 있는 데이터를 리턴할 때에는 getFirst()를 추천하고 맨 뒤에 있는 데이터를 리턴할때에는 getLast()메소드를 추천한다.

 

■ 4-1-3 . LinkedList에 어떤 객체가 포함되어 있는지를 확인하는 메소드 [ contais(), indexOf, lastIndexOf ]

데이터의 값으로 위치를 찾거나, 존재하는지를 확인하려면 위에 표에 있는 메소드들을 사용하면 된다.

 

■ 4-1-4 . LinkedList 객체에서 삭제하고, 데이터를 리턴해주는 메소드 [ remove() ]

삭제 관련 메소드들은특정 데이터를 삭제하는 메소드를 제외하고는 모두 삭제된 데이터를 리턴한다.

맨 앞에 있는 데이터를 삭제하는 많은 메소드들은 모두 removeFirst()메소드를 내부적으로 호출하고

맨 뒤에 있는 데이터를 삭제하는 많은 메소드들은 모두 removeLast() 메소드를 내부적으로 호출한다.

[ 따라서, remove가 붙은 메소드를 사용할 것을 권장한다. ]

 

앞에서 말한 메소드들 말고도 크기를 확인하는 size()나 모든 데이터를 삭제하는 clear(), 데이터를 복제하는 clone, 배열로 만드는 toArray() 메소드들이 있다.

 

■ 4-1-5 . LinkedList 객체를 하나씩 검색하기 위한 Iterator 객체

ListIterator는 Iterator 인터페이스가 다음 데이터만을 검색할 수 있다는 단점을 보완하여, 이전 데이터도 검색할 수 있는 이터레이터다.

==> 따라서, next() 외에도 previous()메소드를 사용하면 이전 데이터를 확인할 수 있다.

---

■ 5. 정리 ■

 

■ java.util.Collection

• List, Set, Queue 타입 구현의 모태가 되는 인터페이스
• Iterable 인터페이스가 확장되어 있다.
• add(), addAll() : 데이터 담기용 메소드
• contains(), containsAll(), isempty(), equals(), size() : 데이터 확인용 메소드
• clear(), remove(), removeAll() : 데이터 삭제용 메소드

---

■ Collection-Set 인터페이스

Set은 List와 비슷하다. 하지만 데이터의 순서가 중요하지 않다.



Set 인터페이스

• 데이터를 목록 형태로 담아둔다.
• 데이터의 위치는 정해져 있지 않으며, 중복된 데이터가 포함될 수 없다.
• 중복되는 데이터를 없애고, 유일한 값만을 뽑아 내려고 할 때 용이하다.
• contains() 메소드를 사용하여 데이터가 포함되어 있는지를 확인할 때 유용하다.
• Collection 인터페이스를 확장하였다.
• Set 인터페이스를 구현한 클래스로는 AbstractSet, ConcurrentSkipListSet, CopyOnWriteArrySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet이 있으며, HashSet이나 TreeSet이 많이 사용된다. 

---

■ Collection-Queue 인터페이스

Queue는 데이터를 순차적으로 처리하기 위한 인터페이스다.

 

Queue 인터페이스

• FIFO(First In First Out, 선입선출) 구조로 되어 있어, 먼저 들어온 데이터를 처리하기 위해서 꺼내면, 그 뒤에 있던 두 번째 데이터가 맨 앞에 존재하게 된다.
• 데이터가 들어온 순서대로 빨리 처리할 때 용이하다.
• Collection 인터페이스를 확장하였다. 하지만, Collection에 선언된 add(), remove(), element() 메소드를 사용하는 것은 권장하지 않는다.
• offer() : 데이터를 저장할 때 사용
• poll() : 가장 앞에 있는 데이터를 꺼내고, 지운다.
• peek() : 가장 앞에 있는 데이터를 꺼내기만 하고, 지우지는 않는다.
• Queue() 인터페이스를 구현한 클래스로는 AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQeue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, PriorityBLockingQueue, PriorityQueue, SynchronousQueue 등이 있으며, 보통 LinkedList가 많이 사용된다.

---

Set은 주로 중복되는 데이터를 처리하기 위해서 사용된다.[ HasSet, TreeSet 많이 사용 ]

Queue[LinkedList 많이 사용]는 먼저 들어온 데이터틀 먼저 처리해주는 FIFO 기능(선입선출)을 처리하기 위해 사용된다.

[ 특히, Queue는 여러 쓰레드에서 들어오는 작업을 순차적으로 처리할 때 많이 사용된다. ]

LinkedList[Queue 구조]는 일반적인 배열 타입의 클래스와 다르게 생성자로 객체를 생성할 때 처음부터 크기를 지정하지 않는다. 왜냐하면, 각 데이터들이 앞 뒤로 연결되는 구조(쉽게, 열차구조)이기 때문에, 미리 공간을 만들어 놓을 필요가 없는것이다.

[ 사실 LinkedList는 List 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. ]