JH-Labs

이진탐색트리(Binary Search Tree) - 최대 자식노드를 2개 갖는 이진트리 - 정렬된 상태로 유지되기 때문에 탐색 효율이 좋음 (중위순회시 정렬된 상태로 출력됨) - Balanced Tree가 아니기 때문에 극단적으로 모든 노드가 자식노드를 1개씩만 갖게 되면 O(n) 성능을 보임 Red-Black Tree - 이진탐색트리의 일종이지만 Balanced Tree이기 때문에 성능을 O(logN)으로 보장함 - 이진탐색트리의 일종이므로 왼쪽 서브트리의 모든 값은 오른쪽 서브트리의 모든 값보다 작아야 함(정렬됨) - Red-Black Tree는 이진탐색트리 중에서 성능이 가장 좋다. - 따라서 리눅스 커널의 프로세스 관리, Java 8이상 HashMap에서 해쉬 블록의 value, 함수형 프로그래밍..

HashMap - HashTable과 다르게 쓰레드 동기화를 하지 않음(single-thread에서 유용) - 기본적으로 해쉬값을 반환하는 해쉬함스로써 hashCode()를 사용함 - hashCode()의 반환형은 int임 - int는 32비트(4Byte)이고 2^32개로 완벽한 해쉬값을 만들 수 없음(표현해야 할 key가 2^32개 보다 많을 경우) - HashMap은 O(1)을 보장하기 위해 random access가 가능하게 하려면 HashMap의 크기는 2^32개 여야 함 - 그래서 보통 2^32보다 작은 숫자 M을 이용해 해쉬값을 다음과 같이 다시 정의함 (int index = X.hashCode() % M) - 여기서 M은 2의 지수승 형태임. 즉, M이 2^a 형태라면 hashCode()의 ..

Type Of Index single level index composite index multilevel index 1. Single Level Index - 인덱싱하는 컬럼이 1개인 경우에 해당함 - primary key에 걸면 Primary Index(기본 인덱스), 다른 컬럼에 걸면 Secondary Index(보조 인덱스) - SQL문에서 where = {key1} = {value1} 가 하나인 경우 equality search가 빠르다. - 메모리에 index table의 데이터 크기가 table보다 작음 - 카디널리티가 매우 낮은 컬럼이라면 인덱스를 지정하지 않는 것이 더 나을 수도 있음 [인덱스 정렬 타입] 1) Dense Index(밀집 인덱스) - 한 인덱스에 원하는 데이터가 바로 매칭..

영속성 전이와 고아 객체는 다른 개념이다. CascadeType과 orphanRemoval은 각각 영속성 전이와 고아 객체 개념에 해당한다. 1. CascadeType.REMOVE - 부모 엔티티가 삭제될 때, 자식 엔티티도 함께 삭제되도록 한다. - 부모 엔티티에 설정한다. 따라서 양방향 연관관계일 경우에만 해당한다. - 부모를 삭제하는 것이 아닌 단순히 부모와 자식의 연관관계를 제거하는 연산에 대해서는 자식 엔티티를 삭제하지 않는다. 예를 들어 부모 엔티티에서 one-to-many로 Collection 형태의 자식 엔티티들을 가지고 있을 때, 해당 Collection에서 특정 자식 엔티티를 삭제하는 연산에 대해서는 delete 쿼리가 발생하지 않는다. 부모 엔티티가 삭제된 것이 아니기 때문이다. cf..

코드 /** * https://www.acmicpc.net/problem/12919 */ import java.io.*; public class Main { private static String S, T; private static final char A = 'A'; private static final char B = 'B'; public static void main(String[] args) throws IOException { init(); var result = solve(T); var bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write(result ? "1" : "0"); bw.flush(); bw.close(); } ..

양방향 연관관계 - 일반적으로 RDB는 방향이 존재하지 않음. 즉, 양방향이라는 개념 자체가 없음 - OneToMany를 사용하더라도 실질적으로 One 쪽의 DB에 컬럼이 생기지 않음 - 객체 단에서 편리함을 제공하기 위해 양방향 연관관계를 제공하는 것 - 따라서 JPA에서 양방향 연관관계를 사용할 경우 연관관계 주인을 정의해 줘야 함 - 연관관계의 주인인 Entity만 외래키의 값을 변경할 수 있고 상대방 Entity는 조회만 가능한 제약이 있음 - 양방향 연관관계를 설정하면 양쪽 모두에 참조 변수를 설정해 줘야 함(동기화 필요). - 이러한 불편함을 해결하고자 연관관계 편의메소드를 활용 - 일반적으로 연관관계 편의 메소드는 주인 엔티티에 정의함(주인이 아닌 쪽에 정의해도 됨) - 추후 유지보수나 확장..

Entity가 기본생성자를 필요로 하는 이유 - JPA는 DB 값을 자바 객체로 직렬화할 때 Reflection을 이용함 - Reflection이란 구체적인 클래스 타입을 알지 못해도 그 클래스의 메소드, 타입, 변수들에 접근할 수 있도록 해주는 Java API - JPA에서는 자바 객체로 직렬화할 때 기본생성자를 통해 먼저 객체를 만들고나서, Reflection을 통해 필드 값을 주입함 - 따라서 Entity에는 기본생성자가 필요하고 기본생성자가 없다면 예외가 발생함(InstantiationException) Proxy - '상속'을 이용해 특정 객체를 한 번 감싸 이전, 이후에 특정 로직을 추가하도록 하는 개념 - JPA의 fetch 타입을 LAZY(지연로딩)으로 할 경우, Proxy로 해당 객체를 ..

Balanced Tree - 한쪽으로 노드가 몰리는 Binary Search Tree의 단점을 보완하고자 등장 - DBMS에서 가장 범용적으로 사용되는 자료구조 - Binary Search Tree와 유사하지만 depth를 자동으로 잡아주기 때문에 탐색 시간복잡도가 O(logN)을 보장함 - 하지만 depth에 영향을 줄 수 있는 insert, delete 경우에 대해서는 성능이 좋지 않을 수 있음 - 결론적으로, 데이터를 얼마나 자주 삽입, 삭제할 것인가에 따라서 B-Tree Index를 활용할지 말지를 결정 - 즉, 갱신 빈도가 높은 테이블에 인덱스를 지정할 경우, 인덱스 재구성 발생 빈도가 높아진다는 점을 고려해야 함 B-Tree - 하나의 노드에 여러개의 값이 배치되는 구조의 트리 - 차수 M의 ..