Team Project (2021-2022)/CS Study

[4주차] 동기/비동기, HashMap 동작 방식, Array vs List vs Vector의 차이점

ddo0 2022. 2. 28. 22:38

Q1. 동기 vs 비동기

동기와 비동기는 프로세스 수행 순서에 대한 메커니즘이다.

→ 가장 많이 나오는 일반적인 예시 : 은행 업무를 볼 때

한 창구에서 한 줄로 서서 보는 업무 == “동기”
여러 업무 창구에서 보는 업무 == “비동기”

동기

의미

💡 synchronous : happening, existing, or arising at precisely the same time

→ 같은 시간에 발생하고 존재하는 것!

즉, 동기는 “작업의 요청과 응답이 동시에 일어난다는” 의미를 가진다.

→ 작업 a, b가 있을 때 작업 a의 요청이 먼저 들어왔다고 하자! (작업 a를 처리하는 데 100초가 걸린다.) a의 요청을 처리하는 동안, 즉, 100초의 시간 동안 대기하다가 처리가 완료되고 작업 a에 대한 응답이 전달되면 작업 b에 대한 요청이 진행된다.

⇒ 정리하자면, 동기는 여러 작업이 수행될 때, 시간이 얼마나 걸리더라도 한 작업이 먼저 처리되며, 이 작업의 응답이 발생할 때 다른 작업의 요청이 발생하는 것이다.

장점

직렬적 수행 → 설계가 매우 간단하고 직관적임

단점

결과가 주어질 때까지 아무것도 못하고 대기해야 한다.

예시로 알아보기

자바의 단일 스레드
- 자바에서 이벤트는 이벤트 분배 스레드에 의해 하나씩 도착하는 순서대로 처리된다. 하나의 이벤트에 대한 처리가 완전히 종료된 후 다음 이벤트가 처리되는 것이다.
자바스크립트
→ 싱글 스레드로 프로그램이 동작한다.

// 결과: 1 2 3 -> 위에서부터 순서대로 실행되는 방식
console.log('1');
console.log('2');
console.log('3');

비동기 = 멀티태스킹 작업

의미

💡 asynchronous ←→ synchronous

→ 작업 a의 수행이 종료되지 않더라도(응답이 발생하지 않았음에도 불구하고), 작업 a를 수행하는 데 걸리는 시간 동안 대기하지 않고 뒤이어 들어온 작업 b를 수행하는 것이다.

⇒ 즉, 동기의 핵심인 “현재 작업의 응답과 다음 작업의 요청이 동시에 발생하는 것”이 아니다.

필요성

데이터를 서버로부터 받아오는 앱을 만든다고 가정하자. 제일 먼저 서버로부터 데이터를 받아올 것이다. 이때 동기로 처리하게 된다면, 모든 데이터를 서버로부터 가져올 때 걸리는 시간이 아무리 길어도 모든 데이터를 받아온 후에 앱이 실행될 것이고, 데이터의 양이 늘어날수록 앱의 실행속도는 느려질 것이다. 즉, 이렇게 데이터를 받아올 때 앱이 대기하는 상태가 되는 것을 방지하기 위해서 비동기적으로 처리하는 것이다.

장점

자원을 효율적으로 사용할 수 있다.
동일한 작업에 대해 비동기 실행이 동기 실행보다 더 빠른 시간 안에 처리한다.

⇒ 비동기 방식의 장점을 나타내는 대표적인 예 “페이지 리로드”

화면을 구성하는 것들 중 조그마한 하나가 바뀌어 페이지 리로드를 할 때 전체 리소스를 다시 불러온다. 이때 불필요한 리소스 낭비가 발생하므로 비효율적이다. 하지만, AJAX와 같이 비동기 방식을 사용하게 된다면 필요한 부분만 불러와 사용할 수 있다.

단점

병렬적 수행 → 동기 방식보다 복잡하다.

예시로 알아보기

비동기는 특성 상 병렬적으로 태스크를 수행하기 때문에, 멀티 스레드가 필요한 멀티 태스킹 작업이다. 따라서 DOS와 같은 단일 운영체제에서는 불가능하며, windows와 같은 멀티 태스크 환경에서만 가능하다.

자바의 멀티 스레드

public class Asynchronous {
public static void main(String[] args){
    Thread t1 = new Thread(()->{
        method1();
    });
    Thread t2 = new Thread(()->{
        method2();
    });
    Thread t3 = new Thread(()->{
        method3();
    });
    t1.start();
    t2.start();
    t3.start();
}
public static void method1(){
    System.out.println("method1");
}
public static void method2(){
    System.out.println("method2");
}
public static void method3(){
    System.out.println("method3");
}
}

→ 실행 결과는 어떻게 될까?
실행 결과는 매번 변하게 된다!!
⇒ 자바의 멀티 스레드는 Thread 스케쥴러에 의해 제어되는데, 이는 비동기식으로 처리되며, 처리 순서는 보장되지 않는다.

제이쿼리 AJAX
→ 기존 웹 어플리케이션에서는 http 요청이 웹 서버로 전달되고 웹 세버는 이를 처리한 후에 사용자에게 html 페이지를 리턴했지만, ajax 통신을 이용하며 http 전송과는 별도로 사용자가 웹 어플리케이션과 상호작용을 할 수 있게 되었다.
```
function getData(){
let tableData;
$.get('https://domain.com/products/1', function (response) {
    tableData = response;
});
return tableData;
}
console.log(getData()); // 결과: undefined
```

실제 결과가 저렇게 나타난 이유는?
-> $.get() 메서드는 비동기 처리되는 메서드이다. 따라서 실행되다 $.get() 메서드를 만난 순간 비동기로 처리하는 부분에 메서드를 맡기고 이 결과를 기다리지 않고 다시 돌아와 다음 줄에 있는 return tableData를 처리한다. 따라서 아무런 값을 가지지 못한 채 리턴된 tableData가 화면에 undefined로 표시되는 것이다.
이러한 문제를 어떻게 처리할까?

콜백 함수를 사용하자!

콜백 함수란?

💡 특정 함수에 매개변수로 전달된 함수로, 해당 함수를 전달받은 함수 안에서 호출된다.

const callBackFunc = function(callback){
    console.log("inside of callBackFunc");
    callback()
};
callBackFunc(function(){
    console.log("this is callback")
});

function getData(callbackFunc) {
    $.get('https://domain.com/products/1', function (response) {
        callbackFunc(response);
    });
}

getData(function (tableData) {
    console.log(tableData);
});

→ $.get() 메서드 파라미터로 callbackFunc 함수 전달함 → 콜백 함수인 callbackFunc 함수는 $.get() 메서드 안에서 실행되는데, 이때 서버에서 받은 데이터를 콜백함수의 인자로 넘겨주고, 콜백 함수가 실행될 때 response가 매개변수로 전달되므로 화면에 표시된다.
- 콜백 함수는 es7~8이 보편화되기 전에 많이 사용했다. 하지만, 현재는 콜백 함수보다 es7에서는 promise를, es8에서는 async, await를 많이 사용한다. 그 이유는 바로 “가독성" 때문이다. 콜백 함수는 여러 데이터를 가져와야 하는 경우 콜백 안에 콜백 함수를 겹쳐서 구성하는 경우가 많은데, 이렇게 되면 흔히 말하는 콜백 지옥에 빠질 수 있는 가능성이 높아진다.

JS의 setTimeout() 메소드
→ WEB API의 한 종류로, 코드를 바로 실행하지 않고 지정한 시간만큼 기다렸다가 실행한다.
```
console.log('1');
setTimeout(() => { console.log('2'); }, 0) // 첫 번째 매개변수는 콜백 함수!
console.log('3');
```
💡 예상결과 → 1, 2, 3(setTimeout 두 번째 인자가 0이니까!)

💡 실제 결과 → 1, null, 3, 2

실제 결과가 저렇게 나타난 이유는?
→ setTimeout() 메소드는 앞서 말했듯이 WEB API, 즉, 비동기적 API이다. 따라서 1을 먼저 출력하고 setTimeout() 메소드를 만난 컴퓨터는 이를 비동기를 처리하는 다른 장소에 맡긴 후, 동기 방식과 같이 수행될 때까지 기다리지 않고 바로 다시 3을 출력한다. 동기 처리가 모두 종료되었으므로 비동기 처리의 결과 2를 출력하는 것이다.

Q2. HashMap 동작 방식

Hashmap이란?

Hashing된 map
객체를 map에 넣는 것

→ Map은 무엇인가?

MAP : key & value를 가진 자료구조. key와 value를 쌍으로 보관

KEY : map에 유일하게 (중복되지 않게) 존재. 동일한 key가 들어오면 기존의 쌍 대체

VALUE : 중복 가능. key를 통해서 값을 볼 수 있음

→ Hashing은 무엇인가?

key 값을 hash function에 대입해서 계산된 결과를 주소로 사용하여 value에 접근할 수 있게 함

Java에서의 HashMap

//선언 
import java.util.HashMap; 
HashMap<Integer,String> map = new HashMap<>();

✅ 값 추가

// key, value
map.put("A", 100);
map.put("B", 101);

✅ 값 삭제

// key로 map의 값 제거 
map.remove("A")

// 모든 값 제거 
map.clear()

✅ 값 읽기

// key로 value 읽어오기 
map.get("B") 

// 많은 양(전체)를 출력할 때 
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
// entrySet()은 key와 value 모두 가져올 때 사용 

for(Integer i : map.keySet()){ 
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
// keySet()은 key만 가져올 때 사용 
// key를 통해서 value를 찾는데 시간이 오래 걸리기 때문에 많은 양의 데이터 처리할 때는 추천X

✅ 존재 여부

map.containsKey("B")     // true 
map.constainsValue(200)  // false

💥 Collision(충돌) 발생

Collision : 동일하지 않은 두 객체가 같은 위치에 들어가려고 하는 경우

충돌 회피 방법

1️⃣ Open Addressing

충돌이 생기면 다른 hash bucket에 해당 자료를 삽입하는 방식
데이터 개수가 적으면 2️⃣ 보다 성능이 좋다
배열의 크기 커질수록 연속된 공간에 데이터 저장하게 됨
모든 원소가 반드시 자신의 hash value와 일치하는 주소에 저장된다는 보장 ❌

2️⃣ Separate Chaining

해당 bucket 값을 첫 부분으로 하는 linked list로 해결
Hash Table 방식
자바는 separate chaining 방식으로 hash table을 구현

Map에 공간이 없을 때

1️⃣ 리스트로 삽입하기

값(value)는 객체이기 때문에 리스트 자체를 마지막 bucket에 삽입할 수 있다

2️⃣ size 늘리기

load factor 사용해서 map의 capacity 늘리기
load factor : map의 크기 늘리기 위한 기준을 제공하는 수

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

4 → map size
0.75f → load factor
4 * 0.75 = 3 → 3번째 공간이 채워지면 hash map이 2배로 증가한다

HashMap vs. HashTable

HashMap	HashTable
빠름 but 동기화 문제	멀티스레드 환경에서 안전(thread-safe)
→ multi-thread 환경에서 성능 👍	→ multi-thread 아니면 성능 떨어짐
key에 null값 허용	key에 null 허용 ❌
보조 hash 사용 → 충돌 발생 가능성 ⬇ 성능⬆	보조 hash 사용 ❌
JAVA의 HashMap은 계속 개선 중

Q3. Array vs List vs Vector

🔎 Array : 배열

여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 자료구조

📌 특징

메모리 상에 연속된 여러 변수들이 모여서 하나의 배열을 이룬다.
- 배열 선언시 배열 사이즈 만큼의 연속된 메모리를 할당 받는다.
- 연속되어 있기 때문에 관리하기 편하다.
대괄호 [] 내부에 변수 인덱스를 지정하여 각각의 변수에 접근할 수 있다.
- 배열의 기본적인 사용방식
- 배열 인덱스는 값에 대한 유일무이한 식별자
배열의 이름은 배열의 첫 번째 변수, 즉 배열 [0]의 포인터이다.
선언할 때에 배열의 크기를 결정하며, 변경할 수 없다.
같은 종류의 변수만 선언 가능하다.
cache hit의 가능성이 커져서 성능에 큰 도움이 된다.
- cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우

⚠ 한계

배열의 길이를 바꿀 수 없다. 가변 배열과 같이 길이가 변경 가능한 배열의 경우,
- 기존의 배열은 그대로 두고
- 새로운 길이로 지정된 배열을 따로 할당한 후
- 데이터의 복사를 진행하고
- 기존의 배열을 삭제한다.
- 총 3번의 작업 + 메모리 탐색이 필요하기 때문에 리소스 낭비가 크다.
한계 해결: linked list 자료형 활용
→ 탐색, 할당, 복사, 삭제 등의 리소스 낭비가 없다.
인덱스에 따라서 값을 유지하기 때문에, 엘리먼트가 삭제되어도 빈자리(null)가 남게 된다.
→ 불필요한 메모리 차지
삭제한 데이터를 뒤에 위치한 엘리먼트로 메꾸면, 데이터가 순서에 따라서 빈틈없이 연속적으로 위치하며, 이를 List(리스트)라고 한다.
인덱스가 중요한 경우는 배열을 사용하고, 그렇지 않은 경우에는 리스트를 사용한다.

🔎 List : 리스트

배열이 가지고 있는 인덱스라는 장점을 버리는 대신 빈틈없는 데이터의 적재라는 장점을 취한 자료구조

📌 특징

핵심: 엘리먼트들 간의 순서(sequence) → 순서가 있는 데이터의 모임
- 여러 자료가 일직선으로 서로 연결된 선형 구조
비연속적인 메모리
- 메모리 선할당을 하지 않는다.
- 각 요소는 이후와 이전의 요소를 가리키는 포인터를 가지고 있어 추가 공간 필요
인덱스의 의미: 몇 번째 데이터인가 정도의 의미
빈 엘리먼트를 허용하지 않는다.
순차성을 보장하지 못해 spacial locality 보장이 되지 않아서 cache hit가 어렵다.
- spacial locality
- : 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현
오버헤드가 발생하지 않는다.

💜 프로그래밍 언어 별 리스트

C

리스트 지원 X, 대신 배열 지원
리스트를 사용하려면 직접 만들거나 라이브러리를 사용해야 한다.

JavaScript

C 패밀리 랭귀지
자바스크립트에서는 배열에 리스트의 기능이 포함되어 있다.

numbers = [10, 20, 30, 40, 50];

numbers.splice(3, 1); // 인덱스 3에서부터 1개의 값을 삭제한다.

for(i = 0; i < numbers.length; i++){
    console.log(numbers[i]);
    // 10, 20, 30, 50
}

Python

기본적으로 리스트 제공, 배열 제공 X
리스트가 곧 배열
리스트 크기가 가변적이고, 어떤 원소 타입이던 저장할 수 있다.
대신 C의 배열보다 메모리를 더 많이 필요로 한다.

numbers = [10, 20, 30, 40, 50]
numbers.pop(3) # 40 / 3번째 인덱스 값 리턴 후 삭제
for number in numbers:
    print(number) # 10, 20, 30, 50

Java

배열과 리스트를 모두 지원하고, 두 가지가 완전히 분리되어 있다.
LinkedList와 ArrayList 2가지 형태로 제공한다.
- ArrayList: 인덱스를 이용해서 데이터를 가져오는 것이 빈번할 때 사용
- LinkedList: 데이터의 추가/삭제가 빈번할 때 사용

⚠ 한계

배열에 비해 상대적으로 복잡하다.
검색이 비효율적이다
참조를 위한 메모리가 필요하다.

🔎 Vector : 벡터

배열 기반 컨테이너
- 동적 배열구조 클래스 → 배열과 달리 크기 수정 가능

📌 특징

연속적인 메모리에 할당됨.
마지막 위치에 추가/삭제는 쉬움.
구현이 용이하다.
랜덤적으로 직접 접근이 가능하다.
- index를 사용해서 특정 값에 바로 접근할 수 있다. ⇒ 데이터 위치를 알 경우 성능이 좋음.

⚠ 한계

연속적인 메모리에 할당되므로, 중간에 값을 삽입하거나 삭제하기 어려움.
- 주소값을 모두 이동시켜야 한다. ⇒ 삽입/삭제가 빈번할 경우 비효율적임.
다량의 데이터에서 검색이 느리다.
- 무작위로 데이터가 들어있을 경우 순차 검색을 해야 한다.

저작자표시 비영리 변경금지

'Team Project (2021-2022) > CS Study' 카테고리의 다른 글

[7주차]Garbage Collection, 함수형 언어 (0)	2022.03.21
[5주차] P NP 문제, ArrayList와 LinkedList, Java vs Python (0)	2022.03.14
[3주차] 알고리즘: 배열, 유전알고리즘, 행렬뒤집기 (0)	2022.02.21
[2주차] 알고리즘: 배열, map, hashmap, set (0)	2022.02.14
[1주차] 알고리즘: Dynamic Programming, 배열 (0)	2022.02.09

현재글[4주차] 동기/비동기, HashMap 동작 방식, Array vs List vs Vector의 차이점

[4주차] 동기/비동기, HashMap 동작 방식, Array vs List vs Vector의 차이점

Q1. 동기 vs 비동기

동기와 비동기는 프로세스 수행 순서에 대한 메커니즘이다.

동기

의미

장점

단점

예시로 알아보기

비동기 = 멀티태스킹 작업

의미

필요성

장점

단점

예시로 알아보기

Q2. HashMap 동작 방식

Hashmap이란?

→ Map은 무엇인가?

→ Hashing은 무엇인가?

Java에서의 HashMap

💥 Collision(충돌) 발생

충돌 회피 방법

Map에 공간이 없을 때

HashMap vs. HashTable

Q3. Array vs List vs Vector

🔎 Array : 배열

📌 특징

⚠ 한계

🔎 List : 리스트

📌 특징

💜 프로그래밍 언어 별 리스트

C

JavaScript

Python

Java

⚠ 한계

🔎 Vector : 벡터

📌 특징

⚠ 한계

'Team Project (2021-2022) > CS Study' 카테고리의 다른 글

'Team Project (2021-2022)/CS Study'의 다른글

관련글

티스토리툴바