심플하고 차분하게

|  요약

- 운영체제는 커널 + 기타 기능
- 운영체제는 시스템 콜을 제공 (쉘은 사용자와 OS간 인터페이스)
- 프로그램 언어별로 OS별 API를 제공
- 응용 프로그램에서 API로 시스템 콜 호출 시, 커널 모드로 변환, OS내부에서 명령 처리 후 리턴

|  운영체제란?

운영체제 (OS : Operating System) : 
사용자의 편의를 위한 환경을 제공하는 시스템 소프트웨어

- 종류 : 윈도우, 유닉스 계열(리눅스), MacOS

- 운영체제는 일반적으로는 커널에 여러가지가 추가된 상태를 의미하지만, 좁은 의미로 "커널(kernel)" 자체를 말합니다.

pf. General Purpose OS vs Embeded OS

 안드로이드는 Embeded OS

  아래 안드로이드 구조를 보면 안드로이드에는 리눅스 커널만 들어가고 

  일반적인 PC의 OS의 나머지 기능들은 추가되어 있지 않습니다. (정말 모바일을 위해 만들어진 녀석이에요)

  안드로이드는 리눅스 커널 위에 라이브러리와 프레임워크를 제공해서 안드로이드 앱이 작동하게 합니다.

|  커널과 쉘

커널(코어, 핵심): 
: 컴퓨터 운영 체제의 핵심이 되는 컴퓨터 프로그램 [출처 : 위키백과]

쉘(Shell)
: 사용자가 운영체제 기능과 서비스를 조작할 수 있도록 시스템 콜을 하는 프로그램
: 사용자와 운영체제 사이에 일종의 다리 역할을 한다.

*시스템 콜의 user(shell) <-> provider(kernel)

- 쉘은 커널 위에서 동작하는 응용 프로그램 중 하나입니다.

- 사용자가 어떤 "명령"을 하면, 프로그램을 구동시킬 수 있는데, 그런 명령을 운영체제에 전달하는 역할을 하는 게 쉘이에요.

- 쉘 중에서도 유명한 쉘로 "리눅스 bash"가 있는데, 해당 내용은 이후 공부하면서 정리하려고 해요.

터미널(CLI)
그래픽 사용자 인터페이스(GUI)	사용자가 편리하게 사용할 수 있도록 입출력 등의 기능을 알기 쉬운 아이콘 따위의 그래픽으로 나타낸 것  [출처 : 위키피디아]

|  시스템 콜

- 시스템 콜은 운영체제에게 어떤 기능을 사용하라고 요청하는 명령 또는 함수를 말하는데요.

- 시스템 콜이라고도 하고, 시스템 콜 인터페이스라고도 합니다.

- 쉽게 풀어서, 운영 체제를 깨워서, "이 작업을 해줘!" 라고 하는 명령을 말합니다.

- 시스템 콜은 커널이 제공하고 있고, 쉘은 시스템 콜을 사용해서 커널이 제공하는 서비스(기능)에 접근합니다.

시스템 콜 : 
운영 체제의 커널이 제공하는 서비스에 대해, 응용 프로그램의 요청에 따라 
커널에 접근하기 위한 인터페이스 [출처 : 위키백과]

|  API

- 프로그램 언어별로 운영체제에 맞는 API가 있습니다.

  : OS는 주로 C언어로 구성되어 있다고 합니다.

    그런데 생각해보면, 응용프로그램들은 자바, 자바스크립트, 기타 C언어가 아닌 언어들로 작성이 된 경우가 많아요.  

    그럼 어떻게 응용프로그램들은 다른 언어로 구성된 OS의 시스템콜을 호출할까요?

    그건 프로그램 언어별로 제공되는 API가 있기 때문입니다.

API(Application Programming Interface)
: 필요할 때 운영체제의 시스템 콜을 호출하는 형태로 만들어진 인터페이스이다.
: 쉽게 말해,함수,패키지,라이브러리이다.

ex. 
Java는 각 OS별로 서로다른 JDK를 통해 개발을 한다.
-> Java의 api 곧, 라이브러리 중 하나로 IO가 있는데, IO는 OS에 입출력을 위한 시스템콜을 호출한다

Q1.  왜 응용프로그램마다 운영체제별로 다른 프로그램을 제공할까요?

- 각각의 운영체제마다 시스템콜은 다릅니다. 그렇기에 각 운영체제에 맞는 API도 다를 수 밖에 없어요.

Q2. 자바 언어로 작성하면 왜 운영체제별로 다른 프로그램을 만들지 않아도 될까요?

- 자바에는 JRE라는 일종의 대안적 운영체제가 존재합니다.

- JRE는 가상머신(JVM)을 통해 데이터를 처리하고 저장합니다.

- 이러한 JRE는 운영체제 위에 덧씌워져 있는 것과 같이 동작하기 때문에,

  결국 자바로 작성한 프로그램은 하나의 소스코드로 여러 개의 운영체제에서 실행할 수 있는 것입니다.

|  커널 모드와 사용자 모드

- 예를 들어, 카카X맵을 처음 설치해서 실행한다고 예를 들어볼게요.

  카카오X맵은 나의 실시간 위치를 확인하기 위해 [실시간 위치 정보 제공]에 대한 [권한]을 요청합니다.

  이러한 권한 요청을 하는 이유는 뭘까요? 그 이유가 바로 위의 사용자 모드와 연관이 되어 있습니다.

- 카카X맵(응용프로그램)을 키고 쓸 때 운영체제의 도움이 필요 없었다면 이 때는 사용자 모드인 상태입니다.

  그러나, 실시간 위치 정보는 운영체제(여기서는 모바일이라서 안드로이드이지만 무시할게요)에서 관리하는 정보입니다.

  따라서, 카카X맵이 실시간 위치 정보를 얻으려면 운영 체제에게 시스템 콜을 해야 하죠. 

- 이제, 시스템 콜이 이루어지고 운영체제가 작동하면 커널 모드가 시작됩니다.

  사용자의 눈으로 볼 때, 권한 요청이 수락되고 비로소 카카X맵에서 길찾기가 정상 작동됩니다. 

- 이렇듯, 응용 프로그램이 직접적으로 내장 기기의 파일이나 중요 기능을 건드리지 않도록 

  사용자 모드와 커널 모드를 분리하는 것은 매우 중요합니다.

** 더보기 : CPU protection rigns에 대한 자세한 설명 링크

|  운영체제의 역할

1. 시스템 자원 (하드웨어) 관리

2. 사용자와 컴퓨터 간 커뮤니케이션을 지원합니다.

3. 응용 프로그램을 제어합니다. (프로세스 관리, 파일 관리, 입출력관리, 네트워크 보안 등)

[ 추천된 책 ]

Operating System Concepts

[ 출처 및 참조 ]

부트캠프 수업을 들은 후 여러 자료를 참조하여 정리한 내용입니다.

https://www.techtarget.com/iotagenda/definition/embedded-operating-system

https://velog.io/@gndan4/OS-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EC%9E%90-%EB%AA%A8%EB%93%9C%EC%99%80-%EC%BB%A4%EB%84%90-%EB%AA%A8%EB%93%9C

https://medium.com/@su_bak/os-%EC%BB%A4%EB%84%90-kernel-%EC%9D%B4%EB%9E%80-b6b8aae8d0b4

https://coding-factory.tistory.com/300

|  캡슐화 (정보 은닉)

앞에서 상속과 다형성을 이야기할 때, 캡슐화의 원칙에 대해 언급했었다.

- 상속의 단점으로 상위 객체의 정보가 하위 객체에서 노출될 수 있고, 그것은 곧 캡슐화의 원칙을 깨는 것이라고 했다.

- 다형성 또한 instanceof를 통해 부모가 참조하고 있던 실제 자식 인스턴스를 외부에서 노출하면 캡슐화의 원칙이 깨졌다.

여기에서도 유추할 수 있는 캡슐화의 의미는 "정보 은닉"이다.

캡슐화 : 정보를 객체 내부로 숨겨 외부로부터 감추는 것

|  접근 제어자와 참조변수

1. 접근 제어자의 UML 표현

- 캡슐화를 이루기 위해서는

  먼저 맴버 변수에 private 접근제어자를 사용하여 외부에서 맴버변수에 접근하지 못하도록 해야한다.

- private의 경우, 파생 클래스의 경우에도 접근이 불가하다.

2. 참조변수의 복사

기본 타입의 변수 값을 가져올 때는 call by value라 하여 값을 복사한다.

int x = 10;
int y = x; // y = 10; call by value
int z = x + y; // 20

x값을 y에 줄 때는 값을 복사해서 전달한다. 하지만 참조변수를 쓸 때는 call by reference라 하여 값을 복사하지 않는다.

// list1과 list2는 모두 같은 곳을 가리킨다
List<Integer> list1= new ArrayList();
list2 = list1;

참조변수는 포인터, 곧 주소를 담고 있는 변수이고, 그 주소는 실제 값이 저장되어 있는 메모리 공간을 의미한다.

그렇기에 포인터 = 가리킨다, 라는 말을 사용한다. 

|  캡슐화와 응집도

- 캡슐화가 되려면 앞서서 "실질적인 정보 은닉"이 이루어져야한다.

- 위에서 배운 접근제어자 private과 게터/세터를 사용하면 아래와 같이 클래스를 만들 수 있다.

public class User{

    private String name;
    
    public String getName(){ 
    	return this.name;
    }
    
    public String setName(String name){
    	this.name = name;
    }
}

- 응집도는 정보은닉에서 더 나아간 개념으로, 하나의 모듈은 하나의 기능을 수행하는 것을 의미한다.

- 응집도에 대한 자세한 내용 : https://computer-science-student.tistory.com/140

|  캡슐화의 장점

[참조]

스프링 입문을 위한 자바 객체 지향의 원리와 이해

https://mangkyu.tistory.com/195

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=knix008&logNo=220699796327 

https://siyoon210.tistory.com/33

https://bperhaps.tistory.com/entry/%EC%BA%A1%EC%8A%90%ED%99%94%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80-%EC%96%B4%EB%96%A4-%EC%9D%B4%EC%A0%90%EC%9D%B4-%EC%9E%88%EB%8A%94%EA%B0%80

|  다형성 (사용 편의성)

다형성이란, 하나의 객체가 여러가지 타입을 가질 수 있는 것을 의미한다.

다형성은 오버로딩과 오버라이딩을 통해 구현할 수 있다.

오버라이딩이 가능한 이유는 뭘까? 그건 동적 바인딩 때문이다.

여기서 동적 바인딩이란 메서드가 실행 시점에서 성격이 결정되는 것을 말한다.

- 자바에서는 static 메소드의 경우 정적바인딩을, 일반 메소드의 경우 동적바인딩을 사용한다.

|  다형성의 장단점

|  다형성 구현 - 오버로딩과 오버라이딩

다형성을 개념적으로, 구현적으로 나누기도 하는 걸 봤었는데, 결국 핵심은 오버로딩과 오버라이딩이었다.

여기에 어떤 분들은 추가적으로 함수형 인터페이스를 함께 소개하기도 해서, 아래와 같이 넣어보았다.

1. 오버로딩 

- 오버로딩의 대표적인 예로, PrintStream의 println()이 있다.

public class PrintStream extends FilterOutputStream
        implements Appendable, Closeable
{

    public void println() {
        newLine();
    }

    public void println(boolean x) {
        synchronized (this) {
            print(x);
            newLine();
        }
    }

    public void println(char x) {
        synchronized (this) {
            print(x);
            newLine();
        }
    }

    public void println(int x) {
        synchronized (this) {
            print(x);
            newLine();
        }
    }

    public void println(long x) {
        synchronized (this) {
            print(x);
            newLine();
        }
    }

}

2. 오버라이딩

[1] 상위 클래스를 상속하고 메소드를 오버라이딩하는 경우 

- 지난번 상속에서 사용한 Vehicle를 조금 변형해서 '움직인다(move)' 기능만 만들어 보았다.

- Vehicle을 상속하는 Car, Train, Airplane은 move를 오버라이딩하여 저마다의 소리를 낸다.

package polymorphism;

class Vehicle {
	
	public void move() {
		System.out.println("unknown");
	}
	
}

class Car extends Vehicle{
	
	public void move() {
		System.out.println("부릉부릉");
	}
}

class Train extends Vehicle{
	
	public void move() {
		System.out.println("칙칙폭폭");
	}
}

class Airplane extends Vehicle{
	
	public void move() {
		System.out.println("위잉위잉");
	}
}

- 메인 함수에서의 출력

 각 하위 인스턴스들을 부모 참조변수인 Vehicle로 통일하여 참조하는 걸 아래에서 볼 수 있다.

 이렇게 부모 참조변수로 자식 인스턴스를 참조하는 것을 업캐스팅이라고 한다.

package polymorphism;

public class Test {
	public static void main(String[] args) {
		Vehicle car = new Car();
		car.move();
		System.out.println();
		
		Vehicle train = new Train();
		train.move();
		System.out.println();
		
		Vehicle air = new Airplane();
		air.move();
		System.out.println();
	}
}

부릉부릉

칙칙폭폭

위잉위잉

[2] 인터페이스를 사용하는 경우

- 위와 같이만 만들 경우에는 사실 다형성의 장점인, '느슨한 결합'을 온전히 지키기 어렵다.

- 왜냐하면 여전히 부모의 객체를 수정할 때, 자식에게 미치는 영향이 있기 때문에 (객체 간 의존성 ↑) 자식 입장에서 부모의 정보를 잘 알고 있어야 하기 때문이다.

- 그렇기에 공통 기능, '움직인다(move)'를 뽑아 movable인터페이스를 만드는 것이 느슨한 결합을 만들기에 더 좋다.

package polymorphism;

public interface Movable {
	public abstract void move();
}

class Car implements Movable{

    @Override
    public void move() {
    	System.out.println("부릉부릉");
    }
}

class Train implements Movable{
    
    @Override
    public void move() {
    	System.out.println("칙칙폭폭");
    }
}

class Airplane implements Movable{
    
    @Override
    public void move() {
    	System.out.println("위이위잉");
    }
}

- 메인 함수에서의 출력

package polymorphism;

import java.util.Arrays;
import java.util.List;

public class Test {
	public static void main(String[] args) {
            List<Movable> movables = Arrays.asList(new Car(), new Airplane(), new Train());
            for (Movable one : movables) {
                one.move();
            }
	}
}

3. 함수형 인터페이스

함수형 인터페이스는 한 개의 추상 메소드를 가진 인터페이스를 말한다.

함수형 인터페이스는 람다식을 통해 간편하게 사용할 수 있는데,

앞서 쓴 movable 인터페이스를 람다식으로 바꿔 쓰면 아래와 같다.

// 함수형 인터페이스 사용
public class Test {
	public static void main(String[] args) {
            List<Movable> movables = Arrays.asList(new Car(), () -> System.out.println("다그닥다그닥"));
            for (Movable one : movables) {
                one.move();
            }
	}
}

4. 객체 타입을 확인하는 instanceof, 지양해야할까?

instanceof 를 통해 부모참조변수가 참조하는 인스턴스가 무엇인지 알 수 있다.

그런데 instanceof를 사용하는 것을 지양하라는 이야기가 있다. 왜 그런 걸까?

아래의 코드를 보면, instanceof를 사용해서 실제 참조하는 인스턴스가 무엇인지 볼 수 있다.

class Test {
    public static void main(String[] args) {
        List<Movable> movables = Arrays.asList(new Car(), new Airplane(), new Train());

        for (Movable one : movables) {
            if (one instanceof Car) {
                System.out.println("This is a Car");
                one.move();
            } else if (one instanceof Airplane) {
                System.out.println("This is an Airplane");
                one.move();
            } else if (one instanceof Train) {
                System.out.println("This is a Train");
                one.move();
            }
        }
    }
}

이렇게 실제 인스턴스를 보게 주게 되면 외부의 객체에 정보를 고스란히 노출하는 것이기 때문에, 캡슐화가 깨지게 된다.

캡슐화란, 객체가 가진 상태나 행위를 다른 이가 사용하거나 보지 못하도록 숨기는 것

[출처] https://tecoble.techcourse.co.kr/post/2021-04-26-instanceof/

따라서, 되도록 instanceof는 사용하는 것을 지양하는 것이 좋다.

[ 참고 ]

자바의 정석

스프링 입문을 위한 자바 객체 지향의 원리와 이해

instanceof의 지양, https://tecoble.techcourse.co.kr/post/2021-04-26-instanceof/

https://tecoble.techcourse.co.kr/post/2020-10-27-polymorphism/

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=next7885&logNo=130068105493 

https://life-with-coding.tistory.com/485

http://www.tcpschool.com/java/java_polymorphism_concept

https://secretroute.tistory.com/entry/140819

https://todayscoding.tistory.com/16

|  요약

- 해시 테이블은 키와 값을 대응시켜 저장하는 구조로, 키를 통해 빠르게 값을 찾을 수 있다는 장점을 가진다.

- 단순히 [ 키 : 값 ] 로 대응시키는 것이 아니라 "해싱"을 통해 키를 변환시킨다.

- 일상생활에서 해시 테이블은 구매내역이나 To-do 체크리스트, 그리고 영어사전에서도 볼 수 있다. 

물품 - 가격이 매칭	체크박스 - 한 줄 문자열 매칭	단어 - 뜻이 매칭
출처 : https://witchform.com/	출처 : https://www.yesform.com/	출처 : https://gonggam.korea.kr/

|  해시함수와 해시값 그리고 해시 충돌

1. 해싱이란?

키를 해시 함수(어떤 계산식)를 통해서 바꾸어 값에 접근하도록 하는 과정

- 키 : 입력값 -> 해시 함수 : 키를 해시 값으로 매핑 -> 해시 값 : 해시 테이블의 인덱스 -> 해시 테이블 : 키-값 저장하는 구조

2. 해시 충돌이란? 

서로 다른 키에 대한 해시 값이 동일한 경우, 같은 공간에 값을 저장하게되는 충돌이 발생하는 것.

* 위의 표에 키를 하나 더 넣어서 해시 충돌을 임의로 일으켜 보자.

서로 다른 키 값 0과 30의 해시 값, 곧 인덱스가 0으로 동일하다. 이렇게 될 경우, 새로 들어간 400이 0자리에 덮어써진다.

|  해시 충돌을 해결하는 방법

- 해시 충돌을 해결하는 방법은 구글을 검색했을 때 정말 많이 나왔는데, 그 중에서도 대표적으로 크게 두 가지,

[1] 개방 주소법 [2] 분리연결법 를 이야기하려고 한다.

1. 개방주소법

- 해시테이블을 구현한 클래스 MyHashtable이 있다고 하자. 

- 나머지는 다 생략하고 해시 함수만 놓고 보았을 때 클래스 내 코드는 아래와 같은 상태일 것이다.

- 이 상태에서 개방주소법의 여러가지 종류, 선형탐사법, 제곱탐사법, 이중해싱을 다뤄보려 한다.

class MyHashTable{

    Integer table[];

    // 해시 함수
    public int getHash(int key) {
        return key % this.table.length;
    }
}

[1] 선형 탐사법 (Linear Probing)

: 충돌이 난 지점부터 +1를 하여 값이 없는 곳에 값을 넣는다.

- 코드를 보면 좀 더 이해하기 쉬울 것 같다.

- 아래 코드에서 보면 else 부문 안에 충돌 지점부터 배열의 인덱스를 하나씩 올리는 걸 볼 수 있다. 이처럼 선형탐사법은 사실상 배열의 인덱스값을 하나씩 올려주면서 배열의 빈 공간을 찾아 순회하는 걸 말한다.

class MyHashTable{

    Integer table[];

    // 해시 함수
    public int getHash(int key) {
        return key % this.table.length;
    }
    
    // 선형 탐사법 : 충돌난 지점부터 +1을 해서 비어있는 곳을 찾는다.
    public void put(int key, int value) {
        int idx = getHash(key);
    
    	if (this.isFull()){
            System.out.println("it is full!");
            return;
        } else if (this.table[idx] == null){
            this.table[idx] = value; // 키의 해시값(인덱스)에 값이 없으면 넣기
        } else {
            int newIdx = idx;
            while (true) { // 충돌지점부터 +1하여 값이 없는 곳 찾기 
               newIdx = (newIdx + 1) % this.table.length; 
               if (this.table[newIdx] == null) {
                  break;
               }
            }
            this.table[newIdx] = value;
        }
    }
}

- 단점 : 일차 군집화 문제가 발생할 수 있다.

- 일차 군집화는 뭘까?

충돌이 발생했던 지점에서 +1을 해서 비어있는 곳을 찾다보면, 충돌된 지점의 주위로 어느새 데이터들이 몰리는 현상이 발생한다. 이런 상황을 일차 군집화라고 한다. 

[2] 제곱 탐사법 (Quadratic Probing)

: 충돌이 난 지점부터 n^2만큼의 간격을 두고 탐사하는 방법이다.

- 단점 : 이차 군집화 문제

- 이차 군집화란, 특정 구간에 데이터가 몰리는 현상이 이차적으로 발생한다는 의미이다. 일차 군집화와 의미는 거의 비슷한데 발생 시점이 두번째라는 게 차이라 보인다.

* 위의 코드에서 else {} 지점만 빼서 수정한다면 아래와 같다.

class MyHashTable{

    /* 생략 */
    
    // 제곱 탐사법 : 충돌이 난 지점부터 n^2로 탐사
    public void put(int key, int value) {
        
        /* 생략 */
        
        } else {
            int newIdx = idx;
            int n = 1;
            while (true) { 
               newIdx = (newIdx + (int)Math.pow(n, 2)) % this.table.length; 
               if (this.table[newIdx] == null) {
                  break;
               }
               n++;
            }
            this.table[newIdx] = value;
        }
    }
}

[3] 이중 해싱 (Double Hashing)

- 말이 참 어려운데 풀이하면 해싱을 한 번 더 하겠다는 의미이다.

- 첫번째 해시함수로는 최초의 해시(인덱스)를 구하고, 충돌이나면 두번째 해시함수로 이동 간격을 잡고 빈 곳을 찾는다.

- 마찬가지로 아래 코드를 보면, 해싱을 두번 하는 코드가 나오는 걸 볼 수 있는데, 두번째의 해싱에서는 해시테이블의 크기보다 조금 작은 소수를 통해 해시값을 %해주고, 거기에 다시 *1, *2, *3..을 하는 방식으로 이중해싱을 하는 걸 볼 수 있다. 이러한 방식으로 하다보면, 선형 탐사나 제곱 탐사보다는 데이터가 골고루 분포된다.

class MyHashTable{

    char p; // Hashtable의 size 보다 조금 작은 소수
    
    /* p를 구하는 함수 생략 */
    
    // 해시 함수1 - 최초 해싱
    public int getHash(int key) {
        return key % this.table.length;
    }
    
    // 해시 함수2 - 충돌 시 2차 해싱
    public int getHash2(int key) {
        int hash = 1 + key % this.p;
        return hash % this.table.length;
    }
    
    // 이중 해싱 : 충돌이 난 지점에서 2차 해싱
    public void put(int key, int value) {
        
        /* 생략 */
        
        } else {
            int newIdx = idx;
            int cnt = 1;
            while (true) { 
               newIdx = (newIdx + getHash2(newIdx) * cnt) % this.table.length; 
               if (this.table[newIdx] == null) {
                  break;
               }
               cnt++;
            }
            this.table[newIdx] = value;
        }
    }
}

2. 분리 연결법

- 충돌이 발생했을 때, 동일한 버킷(Bucket - 지점)에서 연결리스트 형태로 데이터를 연결하는 방식

- 위에서도 표로 잠깐 보여주었던 것처럼 충돌지점에 데이터를 이어 붙이는 걸 볼 수 있다.

- 이번에는 구현 코드보다 자바 라이브러리로 분리 연결법을 사용할 때를 예를 들어보려고 한다.

// 분리연결법을 사용한 경우1 : 이름을 연결할때
// ex. a - amanda, avril, aeron...
Hashtable<String, LinkedList<String>> nameTable = new Hashtable();

// 분리연결법을 사용한 경우2 : (이름, 전화번호)를 담는 2차 배열을 연결할 때
// es. a - (amanda, 123-234-2342), (avril, 123-234-2213)...
Hashtable<String, LinkedList<ArrayList<String>>> phoneTable = new Hashtable();

|  Java 해시맵과 해시테이블의 차이점

* 참조 : 멀티스레드용 HashMap이 별도로 있다 -- synchronizedMap, ConcurrentHashMap 

++ 유용하게 쓸만한 HashMap 메소드 - putIfAbsent(), getOrDefault()

// HashMap의 getOrDefault()
int[] nums = {3, 2, 1, 1, 2, 3, 5};
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
	// getOrDefault(key, defaultValue) - val가 있으면 val가져오고, 아니면 default로 세팅
    map.put(num, map.getOrDefault(num, 0) + 1); 
}

HashMap<Character, Node> map2 = new HashMap<>();
String word = "apple";
for (int i = 0; i < word.length(); i++) {
    char c = word.charAt(i);
    // putIfAbsent(key, val) : key가 없으면 val생성하고, 있으면 넘어간다.
    map2.putIfAbsent(c, new Node());
}

|  해시 관련 문제집

https://school.programmers.co.kr/learn/courses/30/parts/12077

[ 참고 ] 

https://hbase.tistory.com/185

위키백과 https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

https://baeharam.github.io/posts/data-structure/hash-table/

https://velog.io/@roro/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94

|  스택

- 스택은 마치 옷을 겹겹히 쌓듯 데이터를 쌓아 올렸다가 맨 위에서부터 꺼내는 구조이다.

- 스택에 대한 알고리즘 문제를 보면, "괄호 검사", "후위 연산", "문자열의 역순 출력", "실행 취소"와 같이 

  [ 넣었다가 위에서부터 빼는 행위 ]를 통해 문자열의 특정 문자를 검사하고, 어떤 행위를 역전 시키는 걸 볼 수 있다.

- 일상 생활에서 볼 수 있는 또다른 스택의 예시는, 제가 좋아하는 프링글스...위에서부터 뽑아먹는 재미가...

https://www.acmicpc.net/workbook/view/325

|  큐

- 큐는 스타벅스 앞에 줄을 서고 있는 사람들처럼 먼저 들어간 데이터가 먼저 빠지는 구조이다.

- 원형 큐는 원형 연결리스트와 구조적으로 동일하다. 앞과 끝은 있으나 그걸 원형으로 벤딩해놓은 형태. 

  (자바에서는 그러나 원형 큐도 딱히 지원하지 않기 때문에 차라리 데크를 쓰는 편이 수월한 것 같다.)

- 자바에서는 큐는 인터페이스로 제공하고, 큐를 구현하는 객체를 쓸 수 있는데, LinkedList를 쓰면 된다.

- 한 가지 알아두어야 할 점은, 큐에 데이터를 삭제할 때

   poll()를 쓰면 데이터가 없어도 null을 반환하지만,

   remove()를 쓰면 데이터가 없을 때 예외가 발생하기 때문에, 안전성을 위해서 remove()를 쓰는 게 더 좋다는 것!

https://www.acmicpc.net/workbook/view/1504

|  데크

- 데크는 마치 양 옆이 열린 파이프와 같은 형태라고 생각하면 쉬운 것 같다.

- 양쪽에서 데이터를 삽입하고 삭제할 수 있으며, 필요에 따라 양 옆을 제한 시켜 사용할 수도 있다.

- 데크 또한 큐와 마찬가지로 삭제를 할 때, remove()를 쓰는 것이 안전성의 측면에서 더 좋다. 

|  자바 컬렉션의 시간 복잡도

1. Queue

2. Stack

|  요약

- 연결리스트는 각 노드가 연결된 상태로, 삽입과 삭제가 용이하다.

- 다만, 연결리스트는 조회에는 취약한데 그 이유는 처음부터 노드를 순회해야 원하는 타켓을 조회할 수 있기 때문이다.

|  단방향 연결리스트, 양방향 연결리스트, 원형 연결리스트

- 연결리스트는 기본적으로 각각의 노드가 데이터와 포인터를 가진 구조로 되어있다.

- 단방향 연결리스트는 아래와 그림과 같이 각 노드가 next 포인터를 통해 한 방향으로만 연결된 구조인데

  이러한 구조에서는 head노드가 있고, tail은 없는 상태이다.

- 양방향 연결리스트는 아래의 두번째 그림과 같이 각 노드에 prev, next 포인터가 각각 있는 상태를 말한다.

  이 구조에서는 head 노드도 있으며, tail 노드도 존재한다.

  왜냐하면, 각각의 노드 뿐 아니라 전체적인 방향 자체가 양방향이기 때문에 tail이 필요하기 때문

- 원형 연결리스트는 tail 노드의 next가 head를 향하고 있는 상태로, 결과적으로 리스트를 순회하는 구조이다.

  만약, 양방향 연결까지 더해준다면 시계방향, 반시계방향 모두로 순회가 가능하다.

단방향	양방향	원형

* 이미지 출처 : 위키 백과

|  연결리스트의 시간 복잡도

- 연결리스트의 삽입과 삭제는 O(1) 의 시간 복잡도를 갖는다. 

  단순히 노드 사이에 연결만 이루어지면 되기 때문이다.

- 하지만 조회시에는 O(n)의 시간복잡도를 갖는다는 단점이 있다.

  배열과 같이 인덱스가 있는 것이 아니라 노드의 head부터 타겟지점까지 모두 순회해야 하기 때문이다.

|  연결리스트와 큐, 데크

- 연결리스트는 큐와 구조적으로 동일하다고 볼 수 있는데, 이유는 큐와 마찬가지로 선입선출이 가능하기 때문이다.

- 자바에서는 Java.util 라이브러리의 LinkedList를 통해 연결리스트를 사용할 수 있으며, 단방향연결리스트만 제공한다.

- 만약, 양방향 연결리스트가 필요한 경우, Doubly-LinkedList를 별도로 구현하거나 단방향을 활용하는 게 필요하다.

- 만약, 원형 연결리스트가 필요하다면, Deque를 대안적으로 사용할 수 있다.

|  연결리스트 문제집

https://www.acmicpc.net/workbook/view/1066

[ 참고 ] 

https://hbase.tistory.com/185

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

|  상속 (재사용 + 확장)

- 부모 - 자손의 상속 관점 보다는, 재사용과 확장으로 접근하는 것이 좋다

- 상속은, 상위 클래스의 특성을 하위 클래스에서 재사용하고, 거기에 덧붙여 확장할 수 있는 것을 말한다.

- 관계 : 상위 - 하위 / 슈퍼 - 서브

   * 상위로 갈수록 추상화, 일반화되며

   * 하위로 갈수록 구체화, 특수화된다. 

- 상속을 표현하는 문장 

- 오버라이딩 : 상속 관계에 있는 상위 클래스로부터 물려 받은 메소드를 재정의한 것

|  상속의 장단점

* 모듈화 : 소프트웨어를 각 기능별로 나눈 단위. 여기에서는 객체화로 보아도 무방하다.

|  결합도와 응집도

- 상속에 대한 이야기를 할 때 자주 나오는 이야기가 결합도와 응집도인 것 같다.

- 결합도와 응집도란 그럼 뭘까?

- 상속에서는 여러 개의 하위 모듈이 하나의 상위 객체로부터 공통의 메소드를 사용하거나, 참조하기 때문에 지나치게 결합도가 높은 경우에는 차후에 수정을 할 때에 어려움이 발생할 수 있다. 

- 또한 상위 객체에서 접근제어자와 겟터(getter)/셋터(setter) 등으로 정보에 대한 접근을 제한하지 않았다면, 캡슐화(정보은닉)의 원칙도 깨어질 우려가 있다. 잘못하면 상속 후 하위 객체에서 상위 객체의 데이터에 접근을 할 수 있기 때문이다.

- 따라서, 상속 시 사전에 결합도와 응집도를 충분히 고려하는 게 필요하다.

|  상속시 메모리구조

- new 객체명() 를 통해 인스턴스를 생성할 때, 상속을 받은 경우, '나' 뿐만 아니라 '상위' 인스턴스도 함께 힙에 생성된다.

|  UML 표현 (출처 : https://gmlwjd9405.github.io)

(1) Logical

(2) Physical

|  상속을 표현한 코드

동물은 이름(name)과 나이(age)가 있으며, 자신을 소개(introduce)할 수 있다.

 '포유류'는 동물이다. (상속)

- Mammal is a kind of Animal.

포유류는 다른 동물처럼 이름과 나이가 있고, 자신을 소개할 수 있다.

포유류의 포유류의 평균 최대 수명(MAX_AGE)을 갖고 있다.

포유류는 자신을 소개할 때, 포유류의 평균 최대 수명을 함께 소개한다.

package inheritance;

// 동물
public class Animal {
    String name;
    int age;

    Animal () {}

    Animal (String name, int age) {
        this.name = name;
        this.age = age;
    }

    void introduce(){
        System.out.println("Hi, my name is " + name + ", and i am " + age + "years old.");
    }
}

// 포유류 
class Mammal extends Animal{
    final int MAX_AGE = 268;

    void introduce(){
        System.out.println("Hi, my name is " + name + ", and i am " + age + "years old.");
        System.out.println("I can only live MAX : " + MAX_AGE);
    }
}

// 파충류
class Reptile extends Animal{
    final int MAX_AGE = 20;

    void introduce(){
        System.out.println("Hi, my name is " + name + ", and i am " + age + "years old.");
        System.out.println("I can only live MAX : " + MAX_AGE);
    }
}

|  또다른 예시 코드

package inheritance;

class Vehicle {
	
	String name;
	double maxSpeed; 
	int maxCapacity;
	
	public Vehicle() {}
	
	public Vehicle(double maxSpeed, int maxCapacity) {
		super();
		this.maxSpeed = maxSpeed;
		this.maxCapacity = maxCapacity;
	}


	public void info() {
		System.out.println("== vehicle info ==");
		System.out.println("name : " + name);
		System.out.println("maxSpeed : " + maxSpeed);
		System.out.println("maxCapacity : " + maxCapacity);
	}
}

class Car extends Vehicle{
	
	final String name = "car";
	int gasDisplacement; // 배기량
	
	public Car() {}
	
	public Car(int gasDisplacement) {
		super(430,100);
		this.gasDisplacement = gasDisplacement;
	}

	public void info() {
		System.out.println("== Car info ==");
		System.out.println("name : " + name);
		System.out.println("maxSpeed : " + maxSpeed);
		System.out.println("maxCapacity : " + maxCapacity);
		System.out.println("gasDisplacement : " + gasDisplacement);
	}
}

class Train extends Vehicle{
	
	final String name = "train";
	final static String[] ALL_LINES = {"경부선", "호남선", "전라선", 
                                           "중앙선", "경의선", "경의선"}; // 나머지 생략  
	String line; // 노선
	
	public Train() {}
	
	public Train(String line) {
		super(330, 1000);
		this.line = line;
	}

	public void info() {
		System.out.println("== Train info ==");
		System.out.println("name : " + name);
		System.out.println("maxSpeed : " + maxSpeed);
		System.out.println("maxCapacity : " + maxCapacity);
		System.out.println("line : " + line);
	}
}

class Airplane extends Vehicle{
	
	final String name = "airplane";
	String departure;
	String arrival;
	
	public Airplane() {}
	
	public Airplane(String departure, String arrival) {
		super(1000, 200);
		this.departure = departure;
		this.arrival = arrival;
	}

	public void info() {
		System.out.println("== vehicle info ==");
		System.out.println("name : " + name);
		System.out.println("maxSpeed : " + maxSpeed);
		System.out.println("maxCapacity : " + maxCapacity);
		System.out.println("departure : " + departure);
		System.out.println("arrival : " + arrival);
	}
}

-- 테스트 코드

package inheritance;

public class Test {
	public static void main(String[] args) {
		Car car = new Car(1000);
		car.info();
		System.out.println();
		
		Train train = new Train(Train.ALL_LINES[1]);
		train.info();
		System.out.println();
		
		Airplane air = new Airplane("Seoul", "Reykjavik");
		air.info();
		System.out.println();
	}
}

== Car info ==
name : car
maxSpeed : 430.0
maxCapacity : 100
gasDisplacement : 1000

== Train info ==
name : train
maxSpeed : 330.0
maxCapacity : 1000
line : 호남선

== vehicle info ==
name : airplane
maxSpeed : 1000.0
maxCapacity : 200
departure : Seoul
arrival : Reykjavik

[참조]

스프링 입문을 위한 자바 객체 지향의 원리와 이해

https://madplay.github.io/post/coupling-and-cohesion-in-software-engineering

https://gmlwjd9405.github.io/2018/07/04/class-diagram.html

https://sujl95.tistory.com/32

|  추상화 (모델링)

- 현실 세계의 객체에서 필요한 부분만 뽑아 클래스로 만드는 작업을 말한다.

추상화란 구체적인 것을 분해하여 관심 영역에 있는 특성만 가지고 재조립하는 것(= 모델링)

[출처] 스프링 입문을 위한 객체 지향의 원리와 이해

|  추상화가 모델링인 이유

관심 영역(앱의 경계)에 따라 클래스 모델링이 달라진다.

- 현실 세계에서 물리적으로는 동일한 실체에 대해서도 관심 영역(여기서는 애플리케이션에 적용할 영역)이 어디냐에 따라서, 클래스 모델링이 달라진다.

Ex. 사람(객체)을 동물로 본다면 "다리 갯수", "자손 생식 방식" 등을 보겠지만, 고객으로 본다면 "연령대", "지출금액" 등을 볼 것이다.

|  추상화의 예시

[1] 상속을 통한 추상화와 구체화

- 상속 관계에서 상위 클래스로 올라갈 수록 추상화/일반화가 이루어지며,

- 상속 관계에서 하위 클래스로 내려갈 수록 구체화/특수화가 이루어진다.

[2] 인터페이스를 통한 추상화

- 인터페이스를 통해 공통된 메소드를 하나로 묶어 주는 것도 추상화이다.

- 예시 ) Map 인터페이스로부터 파생된, Hashtable과 HashMap

   * 두 객체는 기능적으로 거의 유사하지만 차이를 보인다.

   * Hashtable의 경우 key에 null을 넣을 수 없지만 HashMap은 가능하며, Hashtable은 HashMap과 달리 멀티 쓰레드 환경에 우수하다.

// Map 인터페이스로부터 구현된 클래스들

// 1. Hashtable
Hashtable<Integer, Integer> ht = new Hashtable<>();
ht.put(0, 10);
System.out.println(ht.get(0));

// 2. HashMap
HashMap<Integer, Integer> hm = new HashMap<>();
hm.put(0, 10);
System.out.println(hm.get(0));

|  UML 표현

- 앞에서 잠깐 언급했던 '사람'을 토대로 간단한 클래스 다이어그램을 만들면 아래와 같다.

[참조]

- [스프링 입문을 위한 자바 객체 지향의 원리와 이해], 김종민

- 기타 블로그

|  객체지향 프로그래밍 / 절차지향 프로그래밍

* 객체지향 프로그래밍은 하나의 방법론이지, 그것이 언어나 제품을 의미하는 것은 아니다.

* OOP나 PP 외에 CBD(Component-based development), SOA(Service-orient development)등 프로그래밍 방법론은 많다.

* OOP가 방법이라면, 자바는 언어이고, 스프링 프레임워크는 일종의 제품이다.

* OOP의 장점 중 자연스러운 모델링이라는 것은, 현실 세계와 가깝게 자연스러운 구현이 가능하다는 의미

[참조] 기계어 -> 어셈블리어 -> 컴파일언어(C언어) -> 자바 -> 스프링 프레임워크

|  자바 프로그램의 구동

1. 자바와 가상 머신

- 자바 프로그램은 가상머신 안에서 구동되는 프로그램이다.

- 현실 세계의 하드웨어가 자바 가상 머신으로 옮겨졌다고 보면 된다.

- 가상 머신을 통해서 OS에 독립적인 실행이 가능해진 것이다.

- 일반 하드웨어와 JVM이 메모리를 사용하는 방식

(1) 일반 하드웨어 : 코드 실행 영역 + 데이터 저장 영역

(2) JVM : 코드 실행 영역 + [스태틱 영역 + 스택 영역 + 힙 영역]

2. 구동 순서

(1) 전처리 : 스태틱 영역에, java.lang패키지를 넣고, 모든 import 패키지와 클래스를 넣는다.

(2) 스택 : 메인 메소드(변수 x = 10) -> 다른 메소드 -> 다른 메소드...

(3) 힙 : 배열, 인스턴스 ..... (중간중간 힙 사용)

|  객체

- 객체란? 세상에 존재하는 모든 사물(Object)

- 클래스(분류)와 객체(실체)를 구분하는 것 : 클래스는 분류, 객체는 유일무이한 실체

  "쫀떡이, 나이가 몇살이니?" --> 고양이는 클래스, 쫀떡이는 객체 

|  객체 지향의 4대 특성

|  객체 지향의 5가지 원칙 - SOLID

[참조]

- [스프링 입문을 위한 자바 객체 지향의 원리와 이해], 김종민

- https://www.nextree.co.kr/p6960/

- https://velog.io/@hanjoon_10/OOP-vs.-PP