CS 10일차

TreeMap이란?

TreeMap은 이진트리를 기반으로 한 Map 컬렉션입니다. 같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면 TreeMap은 키와 값이 저장된 Map, Etnry를 저장한다는 점입니다. TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다. 정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Etnry 객체를 저장합니다. TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어집니다. TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸립니다. 하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋습니다.

레드-블랙 트리(Red-Black Tree)

TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있습니다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요합니다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 냅니다. 이 문제를 보완하기 위해 레드 블랙 트리가 등장하였습니다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍니다.

자바에서의 Hash (출처 ㅣ ecsimsw.tistory.com/entry/Hash-Table-원리와-구현 )

자바8의 HashMap은 충돌을 어떤 방식으로 처리할까.

1. Seperate Chaining

자바7까지 HashMap에 Separate Chaining을 사용한 것은 같지만, 자바8부터는 버킷 당 8개 이상의 데이터가 쌓이면 링크드 리스트에서 트리로 변경한다. (이때 트리 탐색 대소 판단 기준은 해시 함수 값이다.)

그리고 데이터가 삭제되어 6개에 이르면 트리에서 다시 링크드 리스트로 변경한다.

이는 노드가 많을 경우 탐색 성능을 위해서는 트리가 우수하지만, 노드가 적을 경우에 트리는 리스트보다 메모리 사용량이 많고, 탐색 성능에서도 크게 차이가 없기 때문이다.

또, 리스트->트리, 트리->리스트를 8/6으로 차이를 둔 것은 만약 차이가 1이라면 한 쌍이 추가, 삭제가 반복될 경우 자료 구조를 매번 변경해야하는 오버헤드를 낳을 수 있어 2개의 차이를 뒀다고 한다.

2. 해시 버킷 동적 확장

해시 버킷의 개수가 적으면 메모리를 아낄 수 있고, 버킷이 많으면 해시 충돌을 줄여 성능을 높일 수 있을 것이다.

자바의 HashMap에서는 데이터의 개수가 일정 개수 이상이 되면 버킷의 개수를 2배로 늘려 성능 손실 문제를 해결한다고 한다.

이때 어느정도 예측 가능한 상황의 경우 버킷의 최초 개수와 임계점을 직접 지정할 수 있다.

최초 버킷의 수는 말그대로 최초 Entry 개수를 말하고, 임계점(load Factor)는 현재 Entry 개수의 몇 배수가 되면 버킷 확장을 실행할까를 결정한다.

예를 들어, 버킷이 100개이고, load factor가 0.87이면, 데이터의 개수가 87개 이상일 때, 버킷의 개수를 200으로 확장하는 것이다.

구현

자바로 간단하게 Seperate Chaining을 구현해봤다.

class HashTable {

    class Node {
        String key;
        String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private LinkedList<Node>[] table;

    public HashTable(int size) {
        table = new LinkedList[size];
    }

    Long getHashCode(String key) {
        Long hashCode = 0L;

        for (char c : key.toCharArray()) { hashCode += (long) c; }

        return hashCode;
    }

    public int getIndex(Long hashCode) {
        return (int) (hashCode % table.length);
    }

    Node searchNode(int index, String key) {
        LinkedList<Node> indexedList = table[index];

        for (Node n : indexedList) {
            if (n.key == key) { return n; }
        }

        return null;
    }

    public void put(String key, String value) {
        Long hashCode = getHashCode(key);
        int index = getIndex(hashCode);

        if (table[index] == null) {
            table[index] = new LinkedList<Node>();
            table[index].add(new Node(key, value));
        }
        else {
            Node searched = searchNode(index, key);

            if (searched != null) { searched.value = value; }
            else { table[index].add(new Node(key, value)); }
        }
    }

    public String get(String key) {
        Long hashCode = getHashCode(key);
        int index = getIndex(hashCode);

        Node searched = searchNode(index, key);

        if (searched == null) { return ""; }
        else { return searched.value; }
    }
}

대칭키 & 공개키

대칭키(Symmetric Key)

암호화와 복호화에 같은 암호키(대칭키)를 사용하는 알고리즘

동일한 키를 주고받기 때문에, 매우 빠르다는 장점이 있음

but, 대칭키 전달과정에서 해킹 위험에 노출

공개키(Public Key)

암호화와 복호화에 사용하는 암호키를 분리한 알고리즘

자신이 가지고 있는 고유한 암호키(비밀키)로만 복호화할 수 있는 암호키(공개키)를 대중에 공개함

공개키 암호화 방식 진행 과정

A가 웹 상에 공개된 'B의 공개키'를 이용해 평문을 암호화하여 B에게 보냄
B는 자신의 비밀키로 복호화한 평문을 확인, A의 공개키로 응답을 암호화하여 A에개 보냄
A는 자신의 비밀키로 암호화된 응답문을 복호화함

대칭키의 단점을 완벽하게 해결했지만, 암호화 복호화가 매우 복잡함

(암호화하는 키가 복호화하는 키가 서로 다르기 때문)

대칭키와 공개키 암호화 방식을 적절히 혼합해보면?

SSL 탄생의 시초가 됨

1. A가 B의 공개키로 암호화 통신에 사용할 대칭키를 암호화하고 B에게 보냄 2. B는 암호문을 받고, 자신의 비밀키로 복호화함 3. B는 A로부터 얻은 대칭키로 A에게 보낼 평문을 암호화하여 A에게 보냄 4. A는 자신의 대칭키로 암호문을 복호화함 5. 앞으로 이 대칭키로 암호화를 통신함

즉, 대칭키를 주고받을 때만 공개키 암호화 방식을 사용하고 이후에는 계속 대칭키 암호화 방식으로 통신하는 것!

CPU 스케줄링 - mangocode.tistory.com/67?category=994509

SQL과 NOSQL의 차이

웹 앱을 개발할 때, 데이터베이스를 선택할 때 고민하게 된다.

MySQL과 같은 SQL을 사용할까? 아니면 MongoDB와 같은 NoSQL을 사용할까?

보통 Spring에서 개발할 때는 MySQL을, Node.js에서는 MongoDB를 주로 사용했을 것이다.

하지만 그냥 단순히 프레임워크에 따라 결정하는 것이 아니다. 프로젝트를 진행하기에 앞서 적합한 데이터베이스를 택해야 한다. 차이점을 알아보자

SQL (관계형 DB)

SQL을 사용하면 RDBMS에서 데이터를 저장, 수정, 삭제 및 검색 할 수 있음

관계형 데이터베이스에는 핵심적인 두 가지 특징이 있다.

데이터는 정해진 데이터 스키마에 따라 테이블에 저장된다.
데이터는 관계를 통해 여러 테이블에 분산된다.

데이터는 테이블에 레코드로 저장되는데, 각 테이블마다 명확하게 정의된 구조가 있다. 해당 구조는 필드의 이름과 데이터 유형으로 정의된다.

따라서 스키마를 준수하지 않은 레코드는 테이블에 추가할 수 없다. 즉, 스키마를 수정하지 않는 이상은 정해진 구조에 맞는 레코드만 추가가 가능한 것이 관계형 데이터베이스의 특징 중 하나다.

또한, 데이터의 중복을 피하기 위해 '관계'를 이용한다.

하나의 테이블에서 중복 없이 하나의 데이터만을 관리하기 때문에 다른 테이블에서 부정확한 데이터를 다룰 위험이 없어지는 장점이 있다.

NoSQL (비관계형 DB)

말그대로 관계형 DB의 반대다.

스키마도 없고, 관계도 없다!

NoSQL에서는 레코드를 문서(documents)라고 부른다.

여기서 SQL과 핵심적인 차이가 있는데, SQL은 정해진 스키마를 따르지 않으면 데이터 추가가 불가능했다. 하지만 NoSQL에서는 다른 구조의 데이터를 같은 컬렉션에 추가가 가능하다.

문서(documents)는 Json과 비슷한 형태로 가지고 있다. 관계형 데이터베이스처럼 여러 테이블에 나누어담지 않고, 관련 데이터를 동일한 '컬렉션'에 넣는다.

따라서 위 사진에 SQL에서 진행한 Orders, Users, Products 테이블로 나눈 것을 NoSQL에서는 Orders에 한꺼번에 포함해서 저장하게 된다.

따라서 여러 테이블에 조인할 필요없이 이미 필요한 모든 것을 갖춘 문서를 작성하는 것이 NoSQL이다. (NoSQL에는 조인이라는 개념이 존재하지 않음)

그러면 조인하고 싶을 때 NoSQL은 어떻게 할까?

컬렉션을 통해 데이터를 복제하여 각 컬렉션 일부분에 속하는 데이터를 정확하게 산출하도록 한다.

하지만 이러면 데이터가 중복되어 서로 영향을 줄 위험이 있다. 따라서 조인을 잘 사용하지 않고 자주 변경되지 않는 데이터일 때 NoSQL을 쓰면 상당히 효율적이다.

확장 개념

두 데이터베이스를 비교할 때 중요한 Scaling 개념도 존재한다.

데이터베이스 서버의 확장성은 '수직적' 확장과 '수평적' 확장으로 나누어진다.

수직적 확장 : 단순히 데이터베이스 서버의 성능을 향상시키는 것 (ex. CPU 업그레이드)
수평적 확장 : 더 많은 서버가 추가되고 데이터베이스가 전체적으로 분산됨을 의미 (하나의 데이터베이스에서 작동하지만 여러 호스트에서 작동)

데이터 저장 방식으로 인해 SQL 데이터베이스는 일반적으로 수직적 확장만 지원함

수평적 확장은 NoSQL 데이터베이스에서만 가능

그럼 둘 중에 뭘 선택?

정답은 없다. 둘다 훌륭한 솔루션이고 어떤 데이터를 다루느냐에 따라 선택을 고려해야한다.

SQL 장점

명확하게 정의된 스키마, 데이터 무결성 보장
관계는 각 데이터를 중복없이 한번만 저장

SQL 단점

덜 유연함. 데이터 스키마를 사전에 계획하고 알려야 함. (나중에 수정하기 힘듬)
관계를 맺고 있어서 조인문이 많은 복잡한 쿼리가 만들어질 수 있음
대체로 수직적 확장만 가능함

NoSQL 장점

스키마가 없어서 유연함. 언제든지 저장된 데이터를 조정하고 새로운 필드 추가 가능
데이터는 애플리케이션이 필요로 하는 형식으로 저장됨. 데이터 읽어오는 속도 빨라짐
수직 및 수평 확장이 가능해서 애플리케이션이 발생시키는 모든 읽기/쓰기 요청 처리 가능

NoSQL 단점

유연성으로 인해 데이터 구조 결정을 미루게 될 수 있음
데이터 중복을 계속 업데이트 해야 함
데이터가 여러 컬렉션에 중복되어 있기 때문에 수정 시 모든 컬렉션에서 수행해야 함 (SQL에서는 중복 데이터가 없으므로 한번만 수행이 가능)

SQL 데이터베이스 사용이 더 좋을 때

관계를 맺고 있는 데이터가 자주 변경되는 애플리케이션의 경우

NoSQL에서는 여러 컬렉션을 모두 수정해야 하기 때문에 비효율적
변경될 여지가 없고, 명확한 스키마가 사용자와 데이터에게 중요한 경우

NoSQL 데이터베이스 사용이 더 좋을 때

정확한 데이터 구조를 알 수 없거나 변경/확장 될 수 있는 경우
읽기를 자주 하지만, 데이터 변경은 자주 없는 경우
데이터베이스를 수평으로 확장해야 하는 경우 (막대한 양의 데이터를 다뤄야 하는 경우)

하나의 제시 방법이지 완전한 정답이 정해져 있는 것은 아니다.

SQL을 선택해서 복잡한 JOIN문을 만들지 않도록 설계하여 단점을 없앨 수도 있고

NoSQL을 선택해서 중복 데이터를 줄이는 방법으로 설계해서 단점을 없앨 수도 있다.

JAVA - final 키워드

간단한 내용이지만, final 키워드가 클래스, 메소드, 변수 앞에 붙었을 때 각각의 의미에 대해서 정확히 정리하려 한다.

final class
- 다른 클래스가 상속받지 못한다.
final method
- 자식 클래스에서 상위 클래스의 final method를 오버라이드 하지 못한다.
final variable
- 변하지 않는 상수 값이 되어 새롭게 값을 할당할 수 없는 변수가 된다.

non-static 멤버와 static 멤버의 차이

non-static 멤버
- 공간적 특성 : 해당 멤버는 객체마다 별도로 존재한다.
  - 인스턴스 멤버라고 부른다.
- 시간적 특성 : 객체 생성 시에 멤버가 생성된다.
  - 객체가 생성될 때, 멤버가 생성되므로 객체 생성 후에 멤버 사용이 가능.
  - 객체가 사라지면 해당 멤버도 사라진다.
- 공유의 특성 : 공유되지 않는다.
  - 멤버는 객체 내에 각각 독립된 공간을 유지하므로 공유되지 않는다.
static 멤버
- 공간적 특성 : 해당 멤버는 클래스 당 하나만 생성된다.
  - 해당 멤버는 객체 내부가 아닌 별도의 공간에 생성된다.
  - 클래스 멤버라고 부른다.
- 시간적 특성 : 클래스 로딩 시에 멤버가 생성된다.
  - 객체가 생성되기 전에 이미 생성되므로 객체를 생성하지 않고도 사용 가능.
  - 객체가 사라져도 해당 멤버가 사라지지 않는다.
  - 해당 멤버는 프로그램이 종료될 때, 사라진다.
- 공유의 특성 : 동일한 클래스의 모든 객체들에 의해 공유된다. (하나의 클래스로부터 생성된 여러 객체가 공유한다.)

저작자표시

'CS 공부 > CS Study 원본' 카테고리의 다른 글

CS 12일차 (0)	2021.01.29
CS 11일차 (0)	2021.01.25
CS 9일차 (0)	2021.01.18
CS 8일차 (0)	2021.01.15
CS 7일차 (0)	2021.01.13

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

코딩공부