컬렉션(Collection) - (1)

<클래스(Class)란?>
- 객체를 만들어 내기 위한 설계도 혹은 틀
- 연관되어 있는 변수와 메서드의 집합




<객체(Object)란?>
- 소프트웨어 세계에 구현할 대상
- 클래스에 선언된 모양 그대로 생성된 객체




[특징]
- '클래스의 인스턴스(instance)'라고도 부른다
- 객체는 모든 인스턴스를 대표하는 포괄적인 의미를 갖는다
- opp관점에서 클래스 타입으로 선언되었을 때 '객체'라고 부른다





<인스턴스(Instance)란?>
- 설계도를 바탕으로 소프트웨어 세계에 구현된 구체적인 실체
  즉, 객체를 소프트웨어에 실체화 하면 그것을 '인스턴스'라고 부른다
- 실체화된 인스턴스는 메모리에 할당된다


[특징]
- 인스턴스는 객체에 포함된다고 볼 수 있다
- 추상적인 개념(또는 명세)과 구체적인 객체 사이의 관계에 초점을 맞출 경우에
  사용한다
- '~의 인스턴스'의 형태로 사용된다
- 객체는 클래스의 인스턴스이다
- 실행 프로세스는 프로그램의 인스턴스이다
- 인스턴스는 어떤 원본(추상적인 개념)으로부터 '생성된 복제본'을 의미한다






<클래스(Class) VS 객체(Object)>
- 클래스는 '설계도', 객체는 '설계도로 구현된 모든 대상'을 의미한다





<객체(Object) VS 인스턴스(Instance)>
- 클래스 타입으로 선언되었을 때 객체라고 부르고, 그 객체가 메모리에 할당되어
  실제 사용될 때 인스턴스라고 부른다
- 객체는 현실 세계에 가깝고, 인스턴스는 소프트웨어 세계에 가깝다
- 객체는 '식체', 인스턴스는 '관계'에 초점을 맞춘다
- 객체를 '클래스의 인스턴스'라고도 부른다





*추상화 기법
1. 분류(Classification)
- 객체 -> 클래스
- 실재하는 객체들을 공통적인 속성을 공유하는 범부 또는 추상적인 개념으로
  묶는 것

2. 인스턴스화(Instantiation)
- 클래스 -> 인스턴스
- 분류의 반대 개념
- 범주나 개념으로부터 실재하는 객체를 만드는 과정
- 구체적으로 클래스 내의 객체에 대한 특정한 변형을 정의하고 이름을 
  붙인 다음, 그 물리적인 어떤 장소에 위치시키는 등의 작업을 통해
  인스턴스를 만드는 것을 말한다
- '예시(Exemplification)'라고도 부른다




[객체(실제 메모리에 정의된 것)]
- 클래스
  - 속성(property) : 멤버변수 필드
  - 기능(function) : 메서드 함수

- 클래스의 인스턴스화(Instantiate)
인스턴스 생성-> 클래스명 변수명 = new 클래스명()
                          Tv         t       = new Tv();
참조변수(인스턴스를 가리키는 클래스형 변수)t가 
Tv인스턴스를 가리키고 있다
인스턴스는 오직 참조변수를 통해서만 다룰 수 있다




<클래스 생성>
클래스형 변수이름 = new 생성자;
ex)Student StudentLee = new Student();
- new 예약어 사용 및 생성자 선언
- 클래스 자료형 변수 선언 -> new 예약어로 생성자 호출하여 대입 -> 새로운 클래스 생성
- 클래스가 생성된다는 것 : 클래스를 실제 사용할 수 있도록 메모리 공간(힙 메모리)를
  할당 받는다는 뜻
- 실제로 사용할 수 있도록 생성된 클래스 : 인스턴스
- 인스턴스를 가리키는 클래스형 변수 : 참조변수


<인스턴스와 참조변수>
- 객체 : 객체 지향 프로그램의 대상 또는 생성된 클래스의 인스턴스
- 클래스 : 객체를 코드로 구현한 것


1. 인스턴스
- 인스턴스 : 클래스가 메모리 공간에 생성된 상태
- 클래스의 생성자 호출 -> 인스턴스 생성
- 클래스는 하나이지만 여러 개의 각각 다른 인스턴스를 생성 가능


2. 참조변수
참조변수.멤버변수
참조변수.메서드

ex)StudentLee.StudentName="이해선" //멤버변수(StudentName)사용
    System.out.println(StudentLee.getStudetnName()); //메서드(getStudentName())사용
- 참조변수를 사용하여 인스턴스의 멤버 변수와 메서드 참조하여 사용 가능
- 도트(.)연산자 사용




<힙 메모리>
- 동적 메모리(dynamic memory)공간
- 객체가 생성될 때 사용하는 공간
- 사용이 끝나면 메모리를 해제해 주어야 하지만 자바에서는 가비지 컬렉터가
  자동으로 메모리를 해제해준다

- new Student()를 선언하면 Student하나가 생성, 
  Student는 StudentID, studentName 등 멤버변수를 가지고 있다
- 멤버 변수를 저장할 공간이 필요 -> 힙 메모리(Heap Memory)
- 클래스 생성자를 하나 호출하면 인스턴스가 힙 메모리에 생성되는 것
  Student StudentLee = new Student();
             참조변수              인스턴스
-> 생성된 클래스를 StudentLee변수에 대입하면, 인스턴스가 저장된 메모리를
     StudentLee변수가 가리킨다

[스택 메모리]     [힙 메모리]
StudentLee        Student 클래스 생성
- 지역변수         - 인스턴스
즉, 지역변수 StudentLee에 생성된 인스턴스를 대입하는 것
=> StudentLee에 인스턴스가 생성된 힙 메모리에 주소를 대입한다는 것




for(String s : listA){ html.append("<li>" + s + "</li>"); }
- ListA에 있는 값을 s에 대입
- ":"는 in 또는 of라는 의미




<Set 컬렉션>
- 인덱스로 객체를 검색해서 가져오는 메소드가 없다->순서 지정X
- 전체 객체를 대상으로 한 번씩 반복해서 가져오는 반복자(Iterator)을 제공
- 반복자는 Interator인터페이스를 구현한 객체를 말하며, iterator() 메소드를
  호출하면 사용할 수 있다




<Set의 구조>
- Array와 달리 set은 요소들을 순차적으로 저장하지 않는다
- Set에서 요소들이 저장될 때 순서
  1. 저장할 요소의 값의 hash값을 구한다
  2. 해쉬값에 해당하는 공간(bucket)에 값을 저장한다
- set에 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에
  순서가 없다 -> 순서가 없기 때문에 indexing도 없다
- 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없다

*hash는 단방향(one way)암호화이다
  단방향이란 한 번 암호화 하면 복호화가 안된다는 뜻이다
  실제 값의 길이와 상관없이 hash값을 일정한 길이를 가진다
  따라서, Hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된
  길이의 데이터로 매핑할 때 사용된다





<Hash란?>
- 데이터를 다루는 기법 중 하나로 검색과 저장이 빠르게 진행된다
- 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환(매핑)하는 것
- 위와 같은 기능을 하는 함수를 '해시 함수(Hash Function)'이라고 한다
- 단방향(one way)암호화
- 입력 데이터를 변환하여 원본 데이터로 복호화할 수 없도록 하는 과정





<HashSet>
- Set 인터페이스의 구현 클래스이다
- 객체들을 순서 없이 저장하고 동일한 객체는 중복 저장하지 않는다

[HashSet 생성]
Set<E> = new HashSet<E>();
- 타입 파라메터 E는 컬렉션에 저장할 객체 타입을 지정하면 된다




<해시 함수(Hash Function)>
- 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수

ex)Apple, Banana를 해쉬테이블로 저장하고 싶고,
   알파벳의 3번째 글자를 집어넣는다는 규칙(해쉬함수)를 정할 때,
   해쉬테이블에 넣으면
apple -> 'p'
banana -> 'n'
   해쉬함수는 사용자가 정의한다
즉,
Hash[p] = apple
Hash[n] = banana





<해시 충돌>
ex)Lee -> 해싱함수 -> 5
    Kim -> 해싱함수 -> 3
    Park -> 해싱함수 -> 2
    ...
    Chun -> 해싱함수 ->5 //Lee와 해싱값 충돌
- 데이터가 많아지면 다른 데이터가 같은 해시 값으로 충돌하는 현상이 발생





<해시코드(HashCode) | 해싱(Hashing)>
- 매핑하기 전 입력 데이터 값을 키(Key),
  매핑 후 출력 데이터 값을 해시코드(HashCode), 
  매핑하는 과정 자체를 해싱(Hashing)이라고 한다





<해시(Hash)의 특징>
- 동일한 입력 값에 대해서는 항상 동일한 출력 값이 보장된다
- 출력 데이터 값을 가지고 원본 데이터의 값을 알아낼 수가 있다
- CPU, 메모리 자원을 크게 소비하지 않는다
- 입력 값의 범위보다 출력 값의 범위가 좁기 때문에 다른 입력 데이터에 대해
  드물게 동일한 출력 값이 나올 수 있다(충돌)





<해싱(Hashing)>
- 해시함수(Hash Function)를 이용해서 해시테이블(Hash Table)에 저장하고 
  검색하는 기법
- 해싱(Hashing)에서 사용되는 자료구조는 array+linkedlist가 조합된 형태 





<해시셋(HashSet)>
- 데이터의 중복을 허용하지 않는 자료구조로, 중복된 데이터를 제거하거나
  이미 데이터가 추가되어 있는지를 검사한다
- 저장된 데이터의 순서를 파악하는건 불가능하다





<해시코드(HashCode)란?>
- 객체 해시코드란 객체를 식별하는 하나의 정수값을 의미
- Object의 hashCode() 메서드는 객체의 메모리 번지를 이용해서 해시코드를
  만들어 리턴하기 때문에 객체마다 다른 값들을 가지고 있다
- 두 객체가 같은 객체인지 동일성을 비교한다
- 어떠한 객체와 다른 객체의 equals결과가 true라면 그 둘의 hashCode 값은 
  반드시 같아야 하지만 haschCode값이 같다고 해서 반드시 equals결과가
  true일 필요는 없다

즉,

hashCode() 메소드를 실행해서 리턴된 해시코드 값이 같은지를 확인한다
해시 코드값이 다르면 다른 객체로 판단하고 해시코드값이 같으면

equals() 메소드로 다시 비교한다 
이 두 개가 모두 맞아야 동등 객체로 판단한다




<Class Object의 존재>
Class A { ... } 는
Class A extends Object{ ... }와 같은 의미
- 모든 클래스는 Object 클래스에 있는 메서드를 마음껏 오버라이딩(재정의)해서
  사용할 수 있다는 의미
- equals(Objext obj)는 Object클래스의 메서드 중 하나이다




<Iterator란?>
- 자바의 컬렉션 프레임워크에서 컬렉션에 저장되어 있는 요소들을 읽어오는 
  방법을 표준화 하였는데 그 중 하나가 Iterator
- 컬렉션 프레임워크란 데이터를 저장하는 클래스들을 표준화한 설계이다
- Iterator는 인터페이스이다




<Iterator 메소드>
- hasNext() : 읽어올 요소가 남아있는 지 확인
  요소가 있으면 true, 없으면 false
- next() : 하나의 객체를 가져올 때 또는 값을 읽을 때 사용
- remove() : next()로 읽어 온 요소를 삭제
*메소드 호출 순서 : hasNext() -> next() -> remove()


<컬렉션 프레임워크>
[Collection]
1. Set(interface)
  a. HashSet(class)
  b. TreeSet(class)

2. List(interface)
  a. Vector(class)
  b. LinkedList(class)
  c. ArrayList(class)

[Map - interface]
  a. TreeMap(class)
  b. Hashtable(class)
  c. HashMap(class)



ex)Iterator<String> iter = list.literator()
    while(iter.hasNext(){ //읽어 올 요소가 남아 있으면 true, 없으면 false
      System.out.println(iter.next());
}



<Interface란?>
- 자바에서는 클래스르 통한 다중 상속은 지원하지 않기 때문에
  인터페이스(interface)라는 다른 클래스를 작성할 때 기본이 되는 틀을 
  제공하면서, 다른 클래스 사이의 중간 매개 역할까지 담당하는 일종의
  추상 클래스를 의미
- 추상 클래스는 추상 메소드, 생성자, 필드, 일반 메소드를 포함하지만,
  인터페이스는 오로지 추상 메소드와 상수만을 포함한다
- 인테페이스는 인터페이스로부터만 상속을 받을 수 있으며
  여러 인터페이스를 상속받을 수 있다




<List 인터페이스>
- 순서 유지O | 데이터 중복O 데이터의 집합

1) ArrayList
- 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능에 
  성능이 뛰어남
- 순차적인 추가 삭제는 빠르며, 비효율적인 메모리를 사용
- Read(Access Time) : 빠르다
- add/remove : 느리다

2) LinkedList
- 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만
  수정하면 되기에 유용
- 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰임
- 데이터가 많을수록 접근성이 떨어진다
- Read(Access Time) : 느리다
- add/remove : 빠르다

3) Vector
- 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나
  비교적 성능이 좋지 않고 무거워 잘 쓰이지 않는다




<Set 인터페이스>
- 순서 유지X | 데이터 중복X | 정렬저장O 데이터 집합

1) HashSet
- Set 인터페이스 중 가장 빠른 임의 접근 속도
- 순서를 예측할 수 없다

2) TreeSet
- 검색 | 정렬이 뛰어나다
- 데이터의 추가, 삭제는 느리다
- 객체의 정렬에 사용되는 클래스
- 내부적으로 이진 검색 트리(binary search tree)로 구현되어 있다
- 객체 비교를 위해 Comparable이나 Comparator 인터페이스를 구현해야한다




<Map 인터페이스>
- 순서 유지X | 키(key)는 중복X | 값(value)은 중복O

1) Hashtable
- HashMap보다는 느리지만 동기화 지원
- null불가

2) HashMap
- 중복과 순서가 허용되지 않으며 null값이 올 수 있다

3) TreeMap
- 정렬된 순서대로 키(key)와 값(value)을 저장하여 검색이 빠르다
- key에 사용되는 클래스에 Comparable, Comparator 인터페이스를 구현

  a. Comparable
  - compareTo() 메서드 구현 : 매개변수와 객체 자신을 비교

  b. Comparator
  - compare() 메서드 구현 : 두 개의 매개변수를 비교, 생성자에 매개변수로 전달





<자료구조>
- 자료(데이터)를 효율적으로 접근하기 수정하기 위해 자료를 조직, 관리, 저장하는 방법
- 상황에 따라 데이터를 다루는데 시간과 메모리를 효율적으로 사용
- 형태에 따라 '선형 자료구조'와 '비선형 자료구조'로 나뉘어 진다

1. 선형 자료구조 - stack, queue, deque, list
- 자료를 구성하는 데이터들의 직선 형태로 순차적으로 나열되어 있는 구조
- 전후 데이터들 간에 일대일(1:1)관계이다

ex)자료1 - 자료2 - 자료3 - ...

2. 비선형 자료구조 - tree, graph
- 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 구조
- 전후 데이터들 간에 1:N관계를 가진다

ex)
자료1
  - 자료2
    - 자료4
    - 자료5
  - 자료3
...

<Stack & Queue & Deque>

1. Stack 
- '쌓다'라는 뜻(하노이의 탑의 구조와 비슷)
- LIFO(Last in First Out, 후입선출)구조 즉, 마지막에 저장된 것을 제일 먼저 꺼낸다
- 'top'으로 정한 곳을 통해서만 접근 가능하며, 가장 위(최근)에 있는 자료를 가리킨다
- 스택에서 자료를 삭제할 때도 'top'을 통해서만 가능하다
- top을 통해 
  1. 삽입하는 연산 : push
  2. 삭제하는 연산 : pop
- 스택의 활용 예시
  - 웹 브라우저 방문기록(뒤로 가기) : 가장 나중에 열린 페이지부터 보여준다
  - 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소
  - 후위 표기법 계산
  - 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)

2. Queue
- 먼저 집어 넣은 데이터를 먼저 꺼내게 되는 저장 구조
- FIFO(First in First Out, 선입선출)구조
- 큐의 가장 첫 원소를 'front', 가장 끝 원소를 'rear'
- 접근방법은 가장 첫 원소와 끝 원소로만 가능
- 큐의 활용 예시(입력된 시간 순서대로 처리해야 할 필요가 있는 상황)
  - 우선순위가 같은 작업 예약(프린터의 인쇄 대기열)
  - 은행 업무
  - 콜센터 고객 대기시간
  - 프로세스 관리
  - 너비 우선 탐색(BFS, Breath-First Search)구현
  - 캐시(Cache)구현

3. Deque(Double Endee Queue)
- 자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조




<동적배열(Dynamic Array)> 
- 크기가 고정되지 않은 배열
- C++의 Vector, Java의 ArrayList

<정적배열(Static Array)>
- 크기가 고정되어 있어 데이터를 크기 만큼만 저장할 수 있다