동적 배열과 연관 배열

배열과 0번 인덱스

Array란 같은 타입의 데이터들을 저장하는 자료 구조로 연속된 메모리 공간에 데이터를 저장한다는 특징이 있다. 필드에 데이터를 저장하는것과 달리 연속된 데이터의 각각엔 이름이 없지만 인덱스를 통해 해당 데이터에 접근할 수 있다.

 

이 때 인덱스 번호는 0부터 시작하게 되는데 이는 배열에서 인덱스가 offset 개념으로 사용 되기 때문이다. C와 같은 프로그래밍 언어에서 특정 영역의 메모리 주소는 기준 주소와 offset으로 계산되는데 기준 주소가 a이고 각 프레임의 크기가 s라고 할 때, i 번째 프레임의 주소값은 다음과 같은 등차수열의 일반항을 통해 계산할 수 있다.

a + s * (i - 1) # 1-based  

a + s * i # 0-based

 

여기서 0-based 방식은 런타임에 계산하기에 좀 더 효율적이라는 이점이 존재하고 묘듈러 연산을 통한 인덱스 매핑을 수행할때도 간결한 표현이 가능해지기 때문에 0-based indexing 방식을 통해 배열에 접근하는것이다.

int[] tries = new int[]{10,9,7,8,8,9,10,6,9,10}; 

 

위와 같이 tries라는 변수가 존재할 때 첫 번째 데이터에 접근 하고싶다면 해당 배열에서 0번째 떨어져있는 데이터에 접근하기 위해 tries[0]과 같이 작성할 수 있다.

 

또 다른 이유로 0-based 방식은 직관적으로 구간을 나타내기 때문이다.

 a. 2 <= i < 13 # best 
 b. 1 < i <= 12 # best 
 c. 2 <= i <= 12 
 d. 1 < i < 13

최단경로 알고리즘으로 유명한 다익스트라는 하나의 메모를 통해 구간을 표현하는 4가지 표현식 중 가장 자연스럽고 직관적인 방법을 도출하는 의견을 제안하였는데

이때 lower bound에서 경계값을 포함하지 않는다면 < 그보다 작은 임의의 실수값을 사용해야하지만, 경계값을 포함하도록 한다면<= 좀 더 의도에 맞는 표현 방법이 될 수 있다는것이다.

 

또 한 upper bound에서는 경계값을 포함할 경우 실수값을 사용하지 않는 이상 공집합을 표현하기가 불가능해지기도한다. 따라서 이러한 이유들 때문에 a와 같은 반닫힌구간을 사용하면 좀 더 의미에 맞고 직관적인 표현이 가능해진다.

2차원 배열과 메모리

앞서 살펴본 1차원 배열과 메모리는 모두 연속적인 구조로 직관적인 이해가 가능했다.
그렇다면 2차원 배열은 어떨까?

 

 

2차원 배열을 시각화 하게 되면 위와 같이 x축과 y축으로 나뉘어 있어 보이지만 메모리 상에서는 결국 1차원으로 구성되어있기 때문에 각 행에 맞춰 할당될 뿐이다.

객체와 메모리

 

자바에서 객체는 연속적인 메모리에 공간에 저장되지않지만 그 객체의 참조는 연속적으로 저장되어있다.

String배열에 위 이미지와 같이 데이터를 저장한다면, 원시 타입과 달리 객체 자체를 저장하지않고 그 객체의 참조를 가져오게된다.

CPU 관점에서 Array 결국 연속된 메모리 공간에 데이터들을 저장하기 때문에 cpu cache를 통해 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있다.

동적 배열 (Dynamic Array)

Dynamic Array란 크기가 변할 수 있는 Array로 데이터를 더하거나 빼는 것이 가능한 자료 구조로 resizable array 혹은 array list 등으로 불린다.

 

동적 배열은 다음과 같이 배열 크기를 넘어선 데이터 추가가 발생하게 된다면 기존 배열보다 두 배 더 크기가 큰 배열을 만들고, 그 곳에 기존 데이터를 복사하는 방식으로 배열의 크기를 조절한다.

 

연관 배열 (Associative Array)

Associative Array를 이해하기 위해 먼저 ADT에 대해 알아야할 필요가 있다.

연관 배열의 맥락에서 "ADT"는 "추상 데이터 유형"을 의미한다. 추상 데이터 유형은 해당 작업이 구현되는 방법에 대한 세부 정보를 지정하지 않고 데이터 구조에서 수행할 수 있는 작업 집합에 대한 상위 수준 설명으로 이는 구현 세부 사항이 아니라 수행할 수 있는 작업 측면에서 데이터 유형의 동작을 정의하게된다.

 

연관 배열은 키-값 쌍의 컬렉션을 나타내는 ADT로 여기서 각 키는 컬렉션 내에서 고유하고 각 키는 값과 연결된다. 키-값 쌍을 사용하면 해당 키를 기반으로 값을 효율적으로 검색할 수 있다.

[!NOTE]
연관 배열의 구체적인 구현은 원하는 동작을 달성하는 데 사용되는 프로그래밍 언어나 기본 데이터 구조에 따라 달라질 수 있다.

 

같은 키를 가지는 Pair는 최대 한 개만 존재하기 때문에 map 혹은 dictionary라고 불린다.

 

 

출처 : 쉬운 코드
출처 : toadzilla.log

배열의 index는 왜 0부터 시작할까?