Notice
Recent Posts
Recent Comments
Link
변수의 기록
(java) 기본 배열(Array), 동적 배열(Dynamic Array), 연관 배열(Associative Array)의 개념과 내부 동작 원리를 설명 본문
자바/자바
(java) 기본 배열(Array), 동적 배열(Dynamic Array), 연관 배열(Associative Array)의 개념과 내부 동작 원리를 설명
불광동 물주먹 2025. 4. 22. 23:29Java에서는 데이터를 저장할 때 다양한 형태의 배열 구조를 사용할 수 있습니다.
세 가지 대표적인 구조인 기본 배열(Array), 동적 배열(Dynamic Array), 연관 배열(Associative Array)의 개념과 내부 동작 원리를 설명하겠습니다.
1. 배열 (Array)
배열은 같은 타입의 데이터를 일정한 순서로 나열하여 저장하는 자료구조입니다. Java에서 배열은 다음과 같은 특성을 가집니다:
📌 특징
- 동일한 데이터 타입만 저장 가능
→ 예: int[], String[] 등 - 고정 크기
→ 생성 시 크기를 지정하면 이후 변경 불가 - 연속된 메모리 공간에 저장
→ 메모리의 주소가 연속적으로 할당되어 있음 - 인덱스를 통한 접근
→ 0부터 시작하는 정수 인덱스를 사용하여 요소 접근
int[] nums = new int[4];
nums[0] = 10;
nums[1] = 20;
📌 성능 측면
배열은 **인덱스를 통한 접근이 매우 빠름(O(1))**입니다.
이는 배열이 연속된 메모리 공간에 존재하기 때문입니다. 인덱스를 기준으로 직접 계산하여 메모리 주소를 찾아가기 때문에 CPU 캐시 성능과도 매우 잘 맞습니다.
👉 offset이란?
배열에서 offset은 **기준 주소(base address)**에서 얼마나 떨어져 있는지를 나타내는 값입니다.
예를 들어, base + i * sizeof(type)을 통해 i번째 요소의 위치를 계산합니다.
2. 동적 배열 (Dynamic Array)
Java에서 대표적인 동적 배열 구현체는 ArrayList입니다.
📌 특징
- 크기 자동 조절 가능
→ 내부적으로 크기를 조절하는 배열을 사용하여 유동적인 데이터 추가를 지원 - 초기 배열이 가득 차면, 두 배 크기의 새 배열을 생성하여 복사
List<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
📌 동작 원리
- 내부 배열을 생성 (예: 크기 4)
- 요소를 추가
- 크기 초과 발생 시:
- 2배 크기의 새 배열 생성
- 기존 요소 복사
- 새로운 배열로 대체
이 과정을 reallocation 또는 resize라고 하며, 비용이 크므로 자주 발생하지 않도록 설계됩니다.
📌 시간복잡도
- 평균 삽입 시간: O(1) (amortized)
- 최악의 경우: O(n) (resize 발생 시 전체 복사)
3. 연관 배열 (Associative Array)
Java에서는 연관 배열의 대표적인 구현체로 HashMap, TreeMap 등이 있습니다.
📌 특징
- Key - Value 쌍으로 데이터 저장
- Key를 기준으로 검색 및 저장
- Key는 중복 불가, Value는 중복 가능
Map<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 80);
📌 내부 구조 (HashMap 기준)
- Key를 hash() 함수를 통해 해시값으로 변환
- 해시값을 이용해 인덱스를 계산하여 내부 배열에 저장
- 충돌 처리: 체이닝(LinkedList), Java 8 이후에는 충돌이 심하면 Tree 구조로 전환
📌 시간복잡도
- 삽입/삭제/탐색: 평균 O(1)
- 최악의 경우: O(n) (충돌이 많을 경우)
결론
구분 | 특징 | 예시 | 시간복잡도 (탐색) |
배열 (Array) | 고정 크기, 연속 메모리, 인덱스 접근 | int[], String[] | O(1) |
동적 배열 | 크기 자동 조절, 내부 배열 복사 | ArrayList | O(1) (평균) |
연관 배열 | Key-Value 저장, 해시 구조 사용 | HashMap, TreeMap | O(1) (평균) |
배열은 가장 기본적이고 빠른 구조이지만, 유연성이 떨어집니다. 동적 배열은 크기 유동성이 강점이고, 연관 배열은 키 기반의 접근이 핵심입니다. 각각의 특징과 동작 원리를 이해하고, 상황에 맞는 자료구조를 선택하는 것이 중요합니다.
'자바 > 자바' 카테고리의 다른 글
(Java) Set의 구조와 활용 - ADT 관점으로 이해 (0) | 2025.04.23 |
---|---|
(Java) Map 구조 정리 - ADT 관점에서의 이해 (****별 다섯개****) (0) | 2025.04.23 |
Java Map 컬렉션 정리 – HashMap, LinkedHashMap, TreeMap (0) | 2025.04.21 |
자바 스레드 덤프(Thread Dump) 분석 방법 (0) | 2025.04.13 |
(java) 인터페이스 왜 쓸까? (0) | 2025.03.27 |