Data Structures

Stack vs. Queue 스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 널리 사용되는 선형 자료구조로, 데이터의 저장 및 처리 방식에서 차이가 있다. 스택(Stack) 스택은 후입선출(LIFO, Last-In First-Out) 방식의 자료구조로, 가장 마지막에 삽입된 데이터가 가장 먼저 제거된다. 데이터의 삽입과 삭제는 모두 스택의 **탑(top)**에서 이루어진다. 주요 연산: 삽입(Push): 데이터를 스택의 탑에 추가한다. 삭제(Pop): 스택의 탑에 있는 데이터를 제거하고 반환한다. 탑 확인(Peek): 스택의 탑에 있는 데이터를 제거하지 않고 확인한다. 비어있는지 확인(IsEmpty): 스택이 비어 있는지 여부를 확인한다. 큐(Queue) 큐는 선입선출(FIFO, First-In First-Out) 방식의 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거된다. 데이터의 삽입은 **후단(Rear)**에서, 삭제는 **전단(Front)**에서 이루어진다. ...

Hash Map HashMap은 키-값 쌍을 저장하고 관리하는 연관 배열의 구현체로, 효율적인 검색, 삽입, 삭제 연산을 제공한다. HashMap은 해시 함수를 사용하여 키를 배열의 인덱스로 변환하고, 해당 인덱스에 값을 저장하는 데이터 구조이다. 이는 키를 통해 빠르게 값을 검색할 수 있게 해준다. https://www.geeksforgeeks.org/load-factor-in-hashmap-in-java-with-examples/ 특징 키-값 쌍 저장: 각 데이터는 고유한 키와 연관된 값으로 저장된다. 빠른 검색: 평균적으로 O(1) 시간 복잡도로 데이터를 검색할 수 있다. 동적 크기 조정: 데이터 양에 따라 자동으로 크기를 조정한다. 널(null) 허용: 대부분의 구현에서 널 키와 널 값을 허용한다. 장점 빠른 접근 및 수정: 키를 통한 빠른 데이터 접근과 수정이 가능하다. 유연성: 다양한 타입의 키와 값을 저장할 수 있다. 메모리 효율성: 데이터 양에 따라 동적으로 크기를 조절한다. 단점 충돌 가능성: 서로 다른 키가 같은 해시 값을 가질 수 있어 충돌이 발생할 수 있다. 순서 보장 없음: 데이터의 삽입 순서가 보장되지 않는다. 메모리 오버헤드: 해시 테이블 구조로 인한 추가적인 메모리 사용이 있을 수 있다. 응용 데이터베이스 인덱싱 캐시 구현 심볼 테이블 관리 빠른 데이터 검색이 필요한 다양한 애플리케이션 동작 원리 해시 함수: 키를 입력받아 배열의 인덱스로 변환한다. 충돌 해결: 서로 다른 키가 같은 인덱스를 가리킬 때 충돌을 해결하는 방법을 사용한다. 구성 요소 버킷: 실제 데이터를 저장하는 배열의 각 요소. 키(Key): 데이터를 식별하는 고유한 값. 값(Value): 키와 연관된 실제 데이터. 해시 함수: 키를 해시 코드로 변환하는 함수. 구현 방식 일반적으로 배열과 연결 리스트를 조합하여 구현한다. 배열은 버킷을 저장하고, 각 버킷은 연결 리스트로 충돌을 해결한다. ...

Lock-free Stack Lock-free Stack은 락(lock)을 사용하지 않고 동시성을 제공하는 LIFO(Last-In-First-Out) 자료구조. 이 자료구조는 여러 스레드가 동시에 스택에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 스택에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Stack은 주로 다음과 같은 방식으로 구현된다: ...

Concurrent Hash Map ConcurrentHashMap은 여러 스레드가 동시에 안전하게 접근할 수 있도록 설계된 HashMap의 동시성 버전이다. 이 자료구조는 멀티스레드 환경에서 높은 성능과 확장성을 제공하면서도 스레드 안전성을 보장한다. Java의 동시성 컬렉션 중 하나로, 멀티스레드 환경에서 안전하게 사용할 수 있도록 설계된 Map 구현체이다. Java를 제외한 프로그래밍 언어와 라이브러리에서도 동시성을 지원하기 위해 구현되어 있는 자료 구조이다. 특징 Thread-safe: 내부적으로 동기화 처리가 되어 있어 멀티스레드 환경에서 안전하다. 높은 동시성: 여러 스레드가 동시에 맵을 수정할 수 있으며, 읽기 작업은 락 없이 수행된다. 원자적 연산 지원: putIfAbsent(), replace(), remove() 등의 원자적 연산을 제공한다. 일관성 있는 반복자: 반복자가 생성된 시점의 맵 상태를 반영하며, ConcurrentModificationException을 발생시키지 않는다. 락 스트라이핑(Lock Striping): 맵을 여러 부분으로 나누어 각각 독립적으로 잠금을 걸어 동시성을 향상시킨다. Null 불허: 키와 값에 null을 허용하지 않는다. 이는 동시성 환경에서 null의 의미가 모호해질 수 있기 때문이다. 약한 일관성: 순간적으로 맵의 상태가 일관되지 않을 수 있지만, 최종적으로는 일관된 상태로 수렴한다. 구현 방식 ConcurrentHashMap은 다음과 같은 기술을 사용하여 구현된다: ...

Cuckoo Hash Table Cuckoo Hash Table은 해시 충돌 문제를 해결하기 위해 개발된 해시 테이블의 한 종류로, 두 개 이상의 해시 함수를 사용하여 각 키에 대해 여러 개의 가능한 위치를 제공한다. 특징 다중 해시 함수: 일반적으로 두 개 이상의 해시 함수를 사용한다. 결정적 성능: 최악의 경우에도 일정한 시간 복잡도를 보장한다. 동적 재배치: 충돌 발생 시 기존 항목을 다른 위치로 이동시킨다. 장점 빠른 검색 속도: O(1) 시간 복잡도로 검색 연산을 수행한다. 공간 효율성: 높은 로드 팩터를 유지할 수 있다. 삭제 연산 지원: Bloom Filter와 달리 효율적인 삭제가 가능하다. 단점 삽입 연산의 복잡성: 최악의 경우 무한 루프에 빠질 수 있어 재해싱이 필요할 수 있다. 구현의 복잡성: 일반 해시 테이블에 비해 구현이 더 복잡하다. 응용 데이터베이스 인덱싱 네트워크 라우팅 테이블 캐시 시스템 스팸 필터링 동작 원리 삽입: ...

블룸 필터 (Bloom filter) 블룸 필터(Bloom Filter)는 공간 효율적인 확률적 데이터 구조로, 원소가 집합에 속하는지 여부를 빠르게 확인하는 데 사용된다. 1970년 Burton Howard Bloom이 고안한 이 구조는 **거짓 양성(false positive)**은 허용하지만 **거짓 음성(false negative)**은 절대 발생하지 않는다. 블룸 필터는 빠른 검색과 극도의 공간 효율이 필요한 시스템에서 필수적이다. 특히 대용량 데이터 처리, 실시간 애플리케이션, 메모리 제약 환경에서 강력한 성능을 발휘한다. 다만 정확성이 절대적이라면 전통적 해시 테이블이 더 적합하다. 핵심 구성 요소 비트 배열(Bit Array): 모든 비트가 0으로 초기화된 배열 (크기 m) 해시 함수(Hash Functions): 원소를 비트 배열의 인덱스로 매핑하는 k개의 독립적 해시 함수 동작 과정 삽입(Add) 원소를 k개의 해시 함수로 해싱 → 각 결과값을 비트 배열의 인덱스로 사용 → 해당 위치의 비트를 1로 설정. 예시: 원소 “apple"을 3개의 해시 함수로 해싱 → 인덱스 1, 4, 7 → 비트 배열 [0,1,0,1,0,0,1,0,0,0] 갱신. ...

Concurrent Skip List Concurrent Skip List는 Skip List 자료구조를 기반으로 하여 멀티스레드 환경에서 동시에 삽입, 삭제, 검색 작업을 수행할 수 있도록 구현된 동시성 자료구조이다. Skip List는 여러 계층의 연결 리스트로 구성된 정렬된 데이터 구조인데, ConcurrentSkipList는 이를 멀티스레드 환경에서 안전하게 사용할 수 있도록 구현한 것이다. 이 자료구조는 락-프리(lock-free) 또는 세밀한 동기화 메커니즘을 사용하여 높은 동시성을 제공한다. 특징 동시성 지원: 여러 스레드가 동시에 자료구조에 접근하고 수정할 수 있다. 락-프리 구현: 대부분의 연산에서 락을 사용하지 않고 Compare-and-Swap(CAS) 연산을 활용한다. 확장성: 멀티코어 시스템에서 높은 확장성을 제공한다. 로그 시간 복잡도: 평균적으로 O(log n) 시간 복잡도로 검색, 삽입, 삭제 연산을 수행한다. 확률적 균형: 재조정 작업 없이 확률적으로 균형을 유지한다. 구현 방식 레벨별 락-프리 리스트: 각 레벨의 리스트를 락-프리 연결 리스트로 취급한다. CAS 연산 사용: 노드 삽입 시 CAS 연산을 사용하여 동시성을 제어한다. 마킹 기법: 노드 삭제 시 다음 참조를 마킹하여 논리적 삭제를 수행한다. 도움 메커니즘: find() 메서드가 마킹된 노드를 정리하는 역할을 수행한다. 장점 높은 동시성: 여러 스레드가 동시에 작업을 수행할 수 있어 성능이 향상된다. 확장성: 스레드 수가 증가해도 성능 저하가 적다. 간단한 구현: 동시성 트리 구조에 비해 구현이 상대적으로 간단하다. 메모리 효율성: 일부 트리 구조보다 메모리 효율적일 수 있다. 응용 동시성 우선순위 큐: 멀티스레드 환경에서 효율적인 우선순위 큐 구현에 사용된다. 데이터베이스 시스템: 동시성 인덱싱 구조로 활용된다. 분산 시스템: 분산 환경에서의 정렬된 데이터 관리에 사용된다. 캐시 시스템: 동시성 캐시 구현에 활용될 수 있다. 동작 원리 Concurrent Skip List는 여러 레벨의 연결 리스트로 구성되며, 각 레벨은 이전 레벨의 “빠른 경로"로 작용한다. 검색, 삽입, 삭제 작업은 상위 레벨에서 시작하여 하위 레벨로 이동하면서 수행된다. ...

Read-Copy-Update (RCU) List RCU List는 동시성을 지원하는 연결 리스트 구조로, 여러 스레드가 동시에 안전하게 접근하고 수정할 수 있도록 설계되었다. RCU List는 Read-Copy-Update 메커니즘을 사용하여 구현된 동시성 연결 리스트로 읽기 작업에 대해 락을 사용하지 않으면서도 동시에 업데이트를 수행할 수 있게 해준다. 특징 락 없는 읽기: 읽기 작업은 동기화 없이 수행된다. 동시성 지원: 여러 스레드가 동시에 리스트에 접근할 수 있다. 읽기 성능 최적화: 읽기 작업의 성능이 매우 뛰어나다. 공간-시간 트레이드오프: 더 많은 공간을 사용하여 빠른 연산을 가능하게 한다. 구현 방식 삽입: 새 노드를 생성하고 원자적으로 리스트에 연결한다. 삭제: 노드를 리스트에서 제거한 후, 일정 시간이 지난 뒤 메모리를 해제한다. 읽기: 동기화 없이 리스트를 순회한다. 장점 높은 읽기 성능: 읽기 작업이 매우 빠르다. 확장성: 다중 코어 시스템에서 좋은 성능을 보인다. 데드락 방지: 읽기 작업에서 락을 사용하지 않아 데드락 위험이 줄어든다. 응용 운영체제 커널 데이터베이스 시스템 네트워크 스택 고성능 멀티스레드 애플리케이션 동작 원리 읽기 작업: 동기화 없이 리스트를 순회한다. 쓰기 작업: 새로운 버전의 데이터를 생성하고, 원자적으로 포인터를 업데이트한다. 삭제: 노드를 리스트에서 제거한 후, 모든 읽기 작업이 완료될 때까지 기다렸다가 메모리를 해제한다. 구성 요소 노드: 데이터와 다음 노드를 가리키는 포인터를 포함한다. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다. RCU 동기화 프리미티브: rcu_read_lock(), rcu_read_unlock(), synchronize_rcu() 등 예시 코드 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.util.concurrent.atomic.AtomicReference; public class LockFreeStack<T> { private static class Node<T> { final T value; Node<T> next; Node(T value) { this.value = value; } } private AtomicReference<Node<T>> head = new AtomicReference<>(null); public void push(T value) { Node<T> newNode = new Node<T>(value); while (true) { Node<T> currentHead = head.get(); newNode.next = currentHead; // CAS로 head를 새 노드로 업데이트 시도 if (head.compareAndSet(currentHead, newNode)) { return; } // 실패하면 다시 시도 } } public T pop() { while (true) { Node<T> currentHead = head.get(); if (currentHead == null) { return null; } // CAS로 head를 다음 노드로 업데이트 시도 if (head.compareAndSet( currentHead, currentHead.next)) { return currentHead.value; } // 실패하면 다시 시도 } } } 참고 및 출처

Lock-free Queue Lock-free Queue는 락(lock)을 사용하지 않고 동시성을 제공하는 FIFO(First-In-First-Out) 자료구조이다. 이 자료구조는 여러 생산자(producer)와 소비자(consumer)가 동시에 큐에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 큐에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Queue는 주로 다음과 같은 방식으로 구현된다: ...

Circular Linked List 이는 Linked List의 한 변형으로, 데이터를 저장하고 조직하는 특정한 방식을 제공한다. Circular Linked List(원형 연결 리스트)는 마지막 노드가 첫 번째 노드를 가리키는 연결 리스트의 변형이다. 이 구조에서는 리스트의 끝이 존재하지 않으며, 모든 노드가 연결되어 원을 형성한다. https://www.geeksforgeeks.org/circular-linked-list/ 특징 마지막 노드의 next 포인터가 NULL이 아닌 첫 번째 노드를 가리킨다. 리스트의 어느 노드에서 시작하더라도 모든 노드를 순회할 수 있다. 리스트의 끝과 시작이 연결되어 있어 순환 구조를 가진다. 장점 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리하다. 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 순환적인 데이터 구조를 표현하기에 적합하다. 메모리를 효율적으로 사용할 수 있다. 단점 구현이 단순 연결 리스트보다 복잡하다. 무한 루프에 빠질 가능성이 있어 순회 중단이 어려울 수 있다. 노드 삭제 시 이전 노드를 찾기 위해 전체 리스트를 순회해야 할 수 있다. 응용 Circular Linked List는 다음과 같은 상황에서 유용하게 사용된다: ...