2JINISHAPPY 2JINISHAPPY

자료구조와 알고리즘을 공부한 사람이라면 레드블랙트리에 대해 한번쯤은 들어봤을 것 이다 포인터가 중간보스라면 레드블랙트리가 최종보스라고 생각하는데 .. 3부작 정도로 나눠서 레드블랙트리를 정리하려고 한다 레드블랙트리가 무엇인지에 대해 알기 전에, 레드블랙트리가 어디에서 사용되는지에 대해 두 가지를 소개하자면 Java Collection API의 Map Interface 구현체인 HashMap의 Seperate Chaining 구현에서 사용한다. 👉 Key값의 Collision이 발생할 경우 같은 Hash값을 가지는 원소들을 Collection으로 관리하는데, 이 때 원소의 개수가 많아지면 Red-Black 트리를 이용해서 관리하여 연산 시간을 O(log)으로 관리한다 Linux의 기본 스케줄러인 CFS 스..

➕ Hash Table은 java에서의 HashTable API가 아닌 Hash function을 통해 mapping된 value를 저장하는 Table을 뜻함 👇 이전 글 보기 https://2jinishappy.tistory.com/230 빠른 데이터 검색을 위한 Hashing과 Hash Table select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 2jinishappy.tistory.com 서로 다른 key에 대해 hash function으로 변환된 h(x)가 같을 경우, 같은 index에 값을 저장해야 하는 coll..

select * from ~ where key="name" 우리는 종종 위와 같은 쿼리문으로 데이터베이스에 있는 튜플을 조회한다 데이터베이스에 있는 attribute의 key값이 unique하다고 할 때, 테이블의 튜플을 어떻게 조회하는 것이 효과적인지 고민하는 과정에서 해싱의 원리를 찾을 수 있다. 특정 key가 주어졌을 때, 해당 key 값을 가진 record를 찾기 위한 방법으로는 1️⃣ Key를 index로 가진 array로 table 구현 2️⃣ BST 이용 1번은 조회하는 데 O(1)이 소모되는 대신 |max(key)|만큼의 메모리를 요구하기 때문에 실제로 사용하기에는 어렵다. 2번 또한 1번에 비해서는 get, insert의 평균적인 시간이 짧긴 하지만 O(log n)도 수천, 수만개의 re..