(java) 기본 배열(Array), 동적 배열(Dynamic Array), 연관 배열(Associative Array)의 개념과 내부 동작 원리를 설명

Java에서는 데이터를 저장할 때 다양한 형태의 배열 구조를 사용할 수 있습니다.

세 가지 대표적인 구조인 기본 배열(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");

📌 동작 원리

1. 내부 배열을 생성 (예: 크기 4)
2. 요소를 추가
3. 크기 초과 발생 시:
   • 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) (평균)

 

배열은 가장 기본적이고 빠른 구조이지만, 유연성이 떨어집니다. 동적 배열은 크기 유동성이 강점이고, 연관 배열은 키 기반의 접근이 핵심입니다. 각각의 특징과 동작 원리를 이해하고, 상황에 맞는 자료구조를 선택하는 것이 중요합니다.