코딩일기

Stack : 쌓아 올리는 것

자료를 정해진 방향으로만 쌓을 있다.
가장 마지막에 입력된 자료가 가장 먼저 출력된다. (후입선출구조 LIFO)

※ LIFO (Last In First Out)

• 자료 저장 push
• 자료 읽기 pop

주 사용처 : 브라우저 사용 기록, 실행 취소

주요 메소드

• push( ) : 객체입력
• peek( ) : 스택의 맨 위 객체를 가져온다. 제거 x
• pop( ) : 스택의 멘 위 객체를 가져온다. 제거 o

ex)

Stack<String> st = new Stack<String>();
st.push("1");
st.push("2");
st.push("3");
st.push("4");
st.push("5");

while (!st.isEmpty()) {
	String str = st.pop();
	System.out.println(str);
}

[실행결과]

5

4

3

2

1

Queue : 줄 서서 기다리는 것

한쪽에서는 입력이, 다른 쪽에서는 출력이 실행된다.
가장 먼저 입력된 자료가 가장 먼저 출력된다. (선입선출구조 FIFO)

※ FIFO (First In First Out)

주 사용처 : 프린트 출력, 프로세스 실행

주요 메소드

• offer( ) : 객체 입력
• peek( ) : 큐의 객체를 가져온다. 제거X
• poll( ) : 큐의 객체를 가져온다. 제거O

ex)

Queue<String> qu = new LinkedList<String>();
qu.offer("1");
qu.offer("2");
qu.offer("3");
qu.offer("4");
qu.offer("5");

while (!qu.isEmpty()) {
String str = qu.poll();
System.out.println(str);​

[실행결과]

1
2
3
4
5

Map

Key(키)와 Value(값)를 가진 중복을 하용하지 않는 집합이다. (키는 중복x 값은 중복o)

즉 한개의 Key와 한개의 Value가 매칭된다.

Map 선언하기

Map<자료형, 자료형> 객체명 = new HashMap<자료형, 자료형>();

※ Map, HashMap import 필요

HashMap

Map Interface를 implements한 클래스로, 중복을 허용하지 않는다.

Map의 특징인 Key - Value의 한 쌍으로 구성된다.

Key 또는 Value의 값으로 null을 허용한다.

HashTable

HashMap과 동일한 내부 구조를 가지고 있다.

hashCode( )와 equals( )를 재정의 하여 동등 객체가 될 조건을 정해서 키로 사용한다.

동기화된 메소드로 구성되었기 때문에 멀티 스레드가 동시에 이 메소드를 실행할 수 없고,

하나의 스레드가 실행을 완료해야 다른 스레드가 실행할 수 있다.

즉 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있다.

이것을 스레드 안전(thread safe) 이라고 한다.

주요 메소드

값 추가하기

{a=b} 

※ 중복된 key가 들어올 경우 덮어쓴다.

Map<String, String> map = new HashMap<String, String>();

System.out.println(map);

map.put("1", "홍길동");
map.put("2", "김길동");
map.put("3", "김길동");
map.put("1", "홍길동2");		//중복된 key가 들어올 경우 덮어쓰여진다

System.out.println(map);
System.out.println(map.size());

[실행결과]

{}
{1=홍길동2, 2=김길동, 3=김길동}
3

값 반환하기

get("key")

key에 해당하는 값(value) 반환

System.out.println(map.get("1"));

[실행결과]

홍길동2

Set으로 반환하기

keySet( )

key들을 set으로 반환 

List<String> list = new ArrayList<String>(map.keySet());
System.out.println(list);

[실행결과]

[1, 2, 3]

해당 값을 key로 가지고 있는지 확인

containsKey("a")

True or False

System.out.println(map.containsKey("1"));
System.out.println(map.containsKey("10"));

[실행결과]

true
false

해당 값을 value로 가지고 있는지 확인

containsValue("a")

True of False

System.out.println(map.containsValue("홍길동2"));
System.out.println(map.containsValue("김길동2"));

[실행결과]

true
false

value값 반환

values( )

System.out.println(map.values());

[실행결과]

[10, 20, 30, 40, 50]

전체 코드

Map<String, String> map = new HashMap<String, String>();	//Map 선언

System.out.println(map);

map.put("1", "홍길동");						//값 추가
map.put("2", "김길동");
map.put("3", "김길동");
map.put("1", "홍길동2");		

System.out.println(map);
System.out.println(map.size());

System.out.println(map.get("1"));				//값 반환

List<String> list = new ArrayList<String>(map.keySet());	
System.out.println(list);					//값 Set으로 반환

System.out.println(map.containsKey("1"));			//해당 값을 Key로 가지고 있는지 확인
System.out.println(map.containsKey("10"));

System.out.println(map.containsValue("홍길동2"));		//해당 값을 Value로 가지고 있는지 확인
System.out.println(map.containsValue("김길동2"));

System.out.println(map.values());				//value값 반환

예제 1.

<key값 출력하기>

Map<String, String> map = new HashMap<String, String>();
map.put("1", "홍길동");
map.put("2", "김길동");
map.put("3", "김길동");
map.put("1", "홍길동2");

//1. map -> list -> for
List<String> list = new ArrayList<String>(map.keySet());
for (int i = 0; i < map.size(); i++) {
	System.out.print(list.get(i) + " : ");
	System.out.println(map.get(list.get(i)));
}

System.out.println("==========");

//2. map -> set -> iterator
Set<String> set = map.keySet();
Iterator<String> it = set.iterator();
while (it.hasNext()) {
	String key = it.next();
	System.out.print(key + " : ");
	System.out.println(map.get(key));
}

System.out.println("==========");

//3. map -> set -> foreach
for (String str : map.keySet()) {
	System.out.print(str + " : ");
	System.out.println(map.get(str));
}

System.out.println("==========");

//4. Map.Entry : map 데이터를 key value 한쌍씩 뽑아내기 
//.getKey(), .getValue() 를 이용하여 직접 값 추출
for (Map.Entry<String, String> ele : map.entrySet()) {
	System.out.print(ele.getKey() + " : ");
	System.out.println(ele.getValue());
}

System.out.println("==========");

//5. map -> set -> Array -> for
//배열로 변환 (set -> Array)
Object[] keyArray = map.keySet().toArray();

for (int i = 0; i < keyArray.length; i++) {
	String key = (String) keyArray[i];
	System.out.println(key + " : " + map.get(key));
}

• map.entrySet( ) : 해당 map에 담겨있는 key value의 연결들(mapping)을 반환

[실행결과]

1 : 홍길동2
2 : 김길동
3 : 김길동
==========
1 : 홍길동2
2 : 김길동
3 : 김길동
==========
1 : 홍길동2
2 : 김길동
3 : 김길동
==========
1 : 홍길동2
2 : 김길동
3 : 김길동
==========
1 : 홍길동2
2 : 김길동
3 : 김길동

예제 2.

<map으로 로그인 하기>

//key = id, value = password
Map<String, String> login = new HashMap<String, String>();
login.put("poseidon", "01234567");
login.put("temp", "temp0000");
login.put("admin", "00000000");
login.put("root", "rootroot");
		
Scanner sc = new Scanner(System.in);
System.out.println("아이디를 입력하세요.");
String id = sc.next();
		
System.out.println("비밀번호를 입력하세요.");
String pw = sc.next();
		
if(login.containsKey(id)) {
	if(login.get(id).equals(pw)) {
		System.out.println("정상 로그인입니다.");
	}else {
		System.out.println("비밀번호가 일치하지 않습니다.");
	}
}else {
	System.out.println("해당 ID는 시스템에 없습니다.");
}

[3가지 경우 실행결과]

아이디를 입력하세요.
roo
비밀번호를 입력하세요.
root
해당 ID는 시스템에 없습니다.

..........................................................

아이디를 입력하세요.
root
비밀번호를 입력하세요.
root
비밀번호가 일치하지 않습니다.

..........................................................

아이디를 입력하세요.
root
비밀번호를 입력하세요.
rootroot
정상 로그인입니다.

HashSet

Set 인터페이스를 상속받은 구현클래스

Set의 성질을 상속받았기 때문에 객체들의 중복을 허용하지 않고 순서를 가지지 않는다. 즉 인덱스가 없다.

(순서를 가지고 싶다면 LinkedHashSet을 구현해야한다)

여기서 HashSet이 판단하는 동일 객체란 꼭 같은 인스턴스를 뜻하진 않는다.

HashSet은 객체를 저장하기 전에 객체의 hashCode( )메소드를 호출해서 해시코드를 얻어낸 후,

이미 저장된 객체의 해시코드와 비교한다.

만약 동일한 해시코드가 나왔을 경우 equals( ) 메소드로 두 객체를 비교해서 
true가 나온다면 동일한 객체로 판단하고 중복 저장을 하지 않는다.

위와같은 순서로 동일 객체인지 확인하기 때문에 

서로 다른 String 객체인 경우에도 같은 문자열을 갖고 있을 때 중복으로 취급될 수 있다.

문자열을 HashSet에 저장하는 경우,

같은 문자열을 갖는 String 객체는 동등한 객체로 간주되고

다른 문자열을 갖는 String 객체는 다른 객체로 간주되는데,

그 이유는 String 클래스가 hashCode( )와 equals( )메소드를 재정의해서
같은 문자열의 경우 hashCode( )의 리턴값을 같게, equals( )의 리턴값을 참으로 나오게 하기 때문이다.

String 객체 뿐만 아니라 임의의 객체들도 hashCode( )메소드와 equals( )메소드를 재정의하면

서로 다른 객체들이라도 중복으로 취급되게 만들 수 있다.

자주 사용하는 메소드

• add(Object o) : 지정된 요소가 집합에 포함되어 있지 않다면 추가한다.
  
  
• clear( ) : 집합의 모든 요소들을 제거한다.
  
  
• contains(Object o) : 집합이 지정된 요소를 포함하고 있다면 true를 반환한다.
  
  
• equals(Object o) : 지정된 객체가 리스트와 동일한지 비교한다.
  
  
• isEmpty( ) : 집합이 요소를 하나도 포함하고 있지 않다면 true를 반환한다.
  
  
• remove(Object o) : 집합에서 지정된 요소를 제거한다.
  
  
• size( ) : 집합의 크기를 반환한다.
  
  
• toArray( ) : 집합에 포함된 모든 요소를 배열로 반환한다.

Set에서 Iterator(반복자) 사용하기

Set 객체는 .get() 메서드가 제공되지 않으므로 다음과 같이 iterator를 활용하여 객체를 순회함

Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());

예제 1.

<HashSet의 동일 객체 취급 기준 확인하기>

class Member{
	public String name;
	public int age;
	
	public Member(String name, int age) {
		this.name = name;
		this.age = age;
	}
	
	@Override
	public int hashCode() {
		return name.hashCode() + age;
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj instanceof Member){
			Member member = (Member) obj;
			return member.name.equals(name) && member.age == age;
		}else {
			return false;
		}
	}
}

public class Set {
	public static void main(String[] args) {
		
		Set<Member> set = new HashSet<Member>();
		
		//Member m1 = new Member("홍길동", 150);
		//Member m2 = new Member("홍길동", 150);
		
		set.add(new Member("홍길동", 150));
		set.add(new Member("홍길동", 150));
		
		System.out.println(set.size()); //1
		System.out.println(set); //[collection.Member@33a4444] 
	}
}

• HashCode( ) 메소드와 equals( ) 메소드를 재정의하면
  같은 객체로 취급되어 중복으로 추가되지 않는 다는 것을 알 수 있다.

LinkedList

ArrayList와 달리 index와 무관하게 불연속적으로 존재하는 데이터의 연결

배열의 단점으로는 크게 두가지가 있는데 

첫째로는 배열의 길이를 미리 정해두어 크기를 변경하기 번거롭다는 것과,

둘째로는 비순차적인 데이터의 추가 및 삭제시 시간이 많이 소모된다는 것이다.

이러한 단점을 보완하기 위해 나온것이 LinkedList이다.

ArrayList와 LinkedList의 속도 비교

LinkedList 값 추가 / 삭제

LinkedList<String> ll = new LinkedList<String>();

ll.addFirst("A");
ll.addFirst("B");
ll.addFirst("C");
ll.addFirst("D");

System.out.println(ll);

ll.removeLast();
System.out.println(ll);

• removeLast( ) : 배열과 같은 컬렉션의 마지막 값을 제거

[실행결과]

[D, C, B, A]

[D, C, B]

예제 1.

<ArrayList와 LinkedList 중간 추가/삭제 속도 비교>

List<String> test1 = new ArrayList<String>();
List<String> test2 = new LinkedList<String>();

long startTime;
long endTime;

startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
test1.add(0, String.valueOf(i));
}
endTime = System.nanoTime();

System.out.println("ArrayList걸린 시간 : " + (endTime - startTime)); 

startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
test2.add(0, String.valueOf(i));
}
endTime = System.nanoTime();

System.out.println("LinkedList걸린 시간 : " + (endTime - startTime));

• System.nanoTime( ) : 시스템 시간과 무관하게 기준 시점에서부터 경과시간을 측정 (ns단위)

[실행결과]

ArrayList걸린 시간 : 4879900
LinkedList걸린 시간 : 1548100

실행결과를 통해 중간 추가/삭제 속도는 ArrayList가 LinkedList보다 느린 것을 확인할 수 있다.