자바에서 자주 쓰는 컬렉션 구조인 List, Set, Map과, 이들 구현체의 자료구조에 대해 알아보자!
여태 컬렉션에 대한 이해가 부족해서 대충 ArrayList나 유명한 것만 사용하였는데
각각 다른 특징과 장단점이 있어서 상황에 맞게 골라서 사용해야 한다. 성능과 용도를 잘 파악해두면 좋을거다.
사실 Map은 자바 컬렉션 프레임워크에 포함되지만, 엄밀히 말하면 Collection 인터페이스를 상속받지 않아서 List, Set처럼 Collection의 하위 타입은 아니다.
컬렉션
List
대표적인 구현체: ArrayList, LinkedList
중복이 허용되어 같은 값을 여러 번 저장할 수 있다.
List의 요소들은 삽입된 순서대로 저장되므로,
DB 쿼리 결과나 API 응답 데이터를 순서대로 처리할 때 유리하다.
"순서"대로 저장되므로, 인덱스 기반으로 접근할 수 있다. ArrayList의 경우 인덱스 접근이 O(1)로 매우 빠르다.
하지만 LinkedList를 사용하면 O(n)이기 때문에 인덱스로 특정 요소에 접근하는 데는 비효율적이다.
단점은 삽입이나 삭제 시 전체 데이터를 이동시켜야 해서 비용이 많이 들 수 있다.
스프링부트에서는 JPA나 MyBatis로 받아온 여러 DB데이터를 리스트에 담아서,
REST API응답으로 순서가 있는 데이터를 보낼 때 DTO리스트로 많이 쓰인다.
데이터의 추가-삭제가 빈번하다면? LinkedList
데이터의 조회가 빈번하다면? ArrayList
Set
대표적인 구현체: HashSet, LinkedHashSet, TreeSet
List와 반대로, 중복이 제거된다. 중복을 제거해야 하는 데이터를 다룰 때 아주 유용하다.
기본적으로는 순서를 유지하지 않지만 LinkedHashSet은 삽입 순서를, TreeSet은 정렬된 순서를 유지한다.
HashSet은 평균 O(1)의 굉장히 빠른 속도로 요소에 접근할 수 있지만 순서를 보장하지 않으므로,
순서가 중요한 경우엔 다른 구현체(Linked, Tree)를 사용해야 하는데 이 경우 약간의 성능 저하가 있을 수 있다.
TreeSet은 정렬된 순서를 유지하기 때문에 삽입이나 삭제 시 O(logn)의 비용이 든다.
스프링부트에서는 Unique한 데이터를 관리할 때 많이 쓰이고, 데이터 처리 과정에서 중복된 값들을 제거할 때 활용할 수 있다.
요소의 정렬이 필요하다면? TreeSet
순서에 상관 없이 빠른 접근이 필요하다면? HashSet
삽입 순서를 유지하면서, 빠른 접근이 필요하다면? LinkedHashSet
Map
대표적인 구현체: HashMap, TreeMap, LinkedHashMap, ConcurrentHashMap
Key-Value 쌍으로 저장된다. 각 데이터가 고유한 키와 그에 대응하는 값을 가지며, 키는 중복될 수 없다.
HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap 등 상황에 맞게 다양한 구현체들 중에서 선택 가능하다.
HashMap은 평균 O(1)로 키를 통한 값 검색이 가능하다. 데이터를 특정 키로 조회하거나 수정할 때 매우 편리하다.
기본 HashMap은 저장 순서를 보장하지 않지만, LinkedHashMap은 삽입 순서를 유지할 수 있다.
TreeMap은 키를 정렬된 상태로 관리하지만, 삽입/삭제가 O(logn)이라 성능 부담이 있을 수 있다.
스프링부트에서는 어플리케이션 설정값(docker.compose 등..)이나 환경변수를 key-value형태로 관리할 때 자주 사용된다.
빠른 조회가 필요한 캐시용 자료구조로도 사용된다.(로컬캐시 hashmap, redis도 key-value 저장소)
HashMap은 내부적으로 배열을 사용하며, 각 배열의 요소를 버킷이라고 부른다.
버킷은 key-value 쌍을 저장하는 노드를 가리키는 포인터를 가진다.
각 버킷 안에는 key-value-next(내부 구조는 상이할 수 있다.)구조를 가진 노드가 저장되고, 여기서 next는 다음 노드를 가리키는 포인터 역할을 한다.
HashMap에서 같은 해시코드를 가진 여러 개의 key-value 쌍이 있을 수 있는데 이를 연결 리스트 방식으로 관리한다.
어떤 키의 해시 값이 동일하면, 같은 인덱스(인덱스-키는 중복될 수 없다.)에 저장되고,
만약 동일한 버킷에 여러 개의 노드가 저장되어야 하면, 연결 리스트 형태로 노드를 추가한다.
| 순서 | null | 동기화 | |
| HashMap | 보장 안됨 | 키, 값 모두 허용 | 비동기 |
| TreeMap | 키의 정렬 순서 | 키는 불가, 값은 허용 | 비동기 |
| LinkedHashMap | 삽입 또는 접근 순서 | 키, 값 모두 허용 | 비동기 |
| ConcurrentHashMap | 보장 안됨 | 키, 값 모두 불가 | 동기화 지원(멀티스레드 굳) |
자료구조
Array
연속된 메모리공간에 데이터를 저장하는 방식이다.
메모리 공간을 효율적으로 사용하고, CPU캐시 히트율이 높아 실제 성능이 좋다.
인덱스로 접근할 때 O(1)의 시간복잡도를 가지고, 한 번 생성하면 크리를 변경할 수 없으므로 동적 크기 조절이 필요하면 ArrayList같은 동적 배열을 사용한다.
단점은 크기가 고정되어 있어 크기를 변경하려면 새로운 배열을 생성하고 데이터를 복사해야 한다.
중간에 요소를 삽입하거나 삭제할 경우, 뒤의 데이터를 이동시켜야 하므로 O(n)의 시간이 걸린다.
Hash
키에 해시 함수를 적용해 배열의 인덱스(버킷)을 결정하고 해당 버킷에 데이터를 저장하는 방식이다.
검색,삽입,삭제 모두 평균 O(1)에 처리가 가능하며, 순서가 보장되진 않는다.
해시 충돌이 발생할 수 있고, 모든 요소가 같은 버킷에 몰리는 최악의 경우에는 O(n)의 시간이 걸린다.
해시 함수를 잘 선택해야 하며 데이터가 많아지면 오버헤드가 발생한다.
Linked
각 노드가 데이터를 저장하고, 다음 노드에 대한 포인터를 가지는 구조다.
메모리 할당이 유연해서 필요할 때마다 노드를 생성해 크기를 자유롭게 변경할 수 있다.
특정 위치에서의 삽입과 삭제가 포인터 조작으로 O(1)시간 안에 처리가 가능하다.
하지만 해당 위치에 임의접근이 불가능해 특정 인덱스에 접근하려면 처음부터 순차적으로 찾아야 하므로 O(n)시간이 걸릴 수 있고,
각 노드마다 추가적인 메모리(포인터)를 사용한다.
Tree
계층적으로 데이터를 저장하며, 각 노드가 자식 노드를 가질 수 있는 구조다.
이진 검색 트리(BST, binary search tree)의 경우 왼쪽 자식이 부모보다 작고, 오른쪽 자식이 부모보다 크다는 특성으로 정렬된 상태를 유지할 수 있다.
정렬된 상태로 유지되므로 범위 검색이나 정렬된 순서로의 순회가 용이하다.
일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸린다.
데이터의 값이 트리에 잘 분산되어 있다면 효율성에 큰 문제가 없으나, 데이터가 들어올 때 값이 편향되게 들어올 경우 한 쪽으로 크게 치우쳐진 트리가 되어 굉장히 비효율적이다.
이 문제를 보완하기 위해 균형 트리가 등장했다.
균형 트리(AVL, Red-Black)의 경우 트리의 높이를 일정 수준 이하로 유지하면서 균형을 맞추어,
항상 예측 가능한 성능으로 O(log n)시간에 삽입,삭제,검색이 가능하다.
각 노드는 빨강 또는 검정 중 하나의 색을 가지고, 루트 노드는 항상 검정색이다.
빨강 노드의 부모와 자식은 검정색이어야 하고, 어떤 노드에서든 루트에서 리프까지의 모든 경로에 있는 검정 노드의 개수는 동일해야 한다.
만약 이 규칙을 위반하면 Rotation 연산을 수행해서 다시 균형을 맞추는데, 이 때 오버헤드가 발생할 수 있다.
'팀 프로젝트 > 최종 프로젝트' 카테고리의 다른 글
| ConfigurationProperties로 민감정보 관리하기 (0) | 2025.02.11 |
|---|
