자바스크립트 배열은 우리가 아는 배열이 아니다

 

🤔 우린 한 번이라도 고민해본 적이 있지 않은가?

 

우리가 흔히 아는 배열은 다음과 같다

 

만약 c언어의 배열인 int sample[5] = [11,22,33,44,55]; 라는 배열이 있다고 생각해보자

https://arer.tistory.com/101

그럼 첫번째부터 마지막까지 순서대로 나열되어 메모리에 할당된다는 것은 다 알고 있을 것이다.

여기서 중요한건 메모리에 들어가는 데이터 타입이 한 가지(정수를 나타내는 int는 4byte)로 통일되어있으니 모든 배열의 요소는 4바이트씩 할당되어 빈틈없이 연속적으로 나열된다.

 

즉 자료구조에서 말하는 배열은 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열되는 자료구조이다.

 

우리는 이러한 배열을 밀집 배열(dense array)라 부른다.

 

하지만 자바스크립트의 배열은 다르다.

 

const array = [
  'string',
  10,
  true,
  null,
  undefined,
  NaN,
  Infinity,
  [],
  {},
  function () {},
];

 

이렇게 서로 다른 타입의 데이터들도 모두 들어갈 수 있다.

 

❓ 정확히 타입마다 할당되는 메모리 바이트 수도 다를 텐데 얘네들은 왜 멋대로 들어갈 수 있는 거지?라는 생각을 해보았을 거다. 

 

이 글에서는 그 궁금점을 해결하도록 하겠다.

 

 

📝 자바스크립트의 배열은 일반적인 배열의 동작을 흉내 낸 특수한 객체이다.

 

결론부터 이야기를 하겠다.

아래의 사진처럼 자바스크립트의 배열은 내부적으로 해쉬 테이블로 되어있다.

 

해쉬 테이블로 구현이 되어있기에 메모리 주소가 연속적으로 나열되지 않는다.

그래서 여러가지의 타입을 하나의 배열에 넣을 수 있는 것이다.

 

이렇게 각각의 배열의 요소가 동일한 메모리 크기를 갖지 않아도 되고, 연속적으로 이어져 있지 않을 수도 있는 배열을 희소 배열(sparse array)이라 부른다.

 

🤔 그러면 왜 자바스크립트는 일반적인 자료구조에서 말하는 배열(밀집 배열)이 아닌 해쉬 테이블(희소 배열)을 택했을까?

 

 

📝 일반적인 배열과 자바스크립트 배열의 차이

 

 

 

먼저 앞서 나온 일반적인 배열의 특성을 알아보자.

https://arer.tistory.com/101

이처럼 배열의 요소들이 순서를 가지며 각각의 요소들의 크기가 같으니

다음과 같이 어떤 특정한 인덱스에 접근을 할려면 단 한 번의 연산으로 접근이 가능하다.

 

접근 대상 요소의 메모리 주소 = 배열의 시작 메모리 주소 + 인덱스 * 요소의 바이트 수

 

인덱스가 0인 요소의 메모리 주소 : 1000 + 0 * 4 = 1000

인덱스가 1인 요소의 메모리 주소 : 1000 + 1 * 4 = 1004

인덱스가 2인 요소의 메모리 주소 : 1000 + 2 * 4 = 1008

 

이렇게 단 한 번의 연산을 하면 되니 데이터 접근에 대한 시간 복잡도는 O(1)이며, 매우 효율적이고 빠르다.

 

 

반면의 배열에서 특정한 데이터를 검색하려면 처음부터 끝까지 모두 검색해야 하니데이터 검색에 대한 시간 복잡도는 O(n)이 걸린다.

 

function lineerSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}

console.log(linearSearch[(3, 2, 1, 5, 4, 6)], 3); // 0
console.log(linearSearch[(3, 2, 1, 5, 4, 6)], 0); // -1

 

배열 요소 추가와 삭제 또한 마찬가지이다.

추가와 삭제되는 위치 뒤에 있는 요소들을 이동해야 하니

추가 및 삭제의 대한 시간 복잡도 최악의 경우는 O(n)이다.

https://poiemaweb.com/js-array-is-not-arrray

 

 

하지만 자바스크립트 배열은 해쉬 테이블이므로 시간 복잡도는 다음과 같다.

 

	시간복잡도(평균적인 경우)	시간복잡도(최악의 경우)
인덱스로 요소 접근	O(n)	O(n)
요소 탐색	O(1)	O(n)
요소 추가	O(1)	O(n)
요소 삭제	O(1)	O(n)

 

(이 글은 해쉬 테이블을 다루지 않으므로 이 부분은 표로 통해 간단히 넘어가겠다. 해쉬에 대해 자세히 알고 싶은 분은 여기를 보도록 하자.)

 

이렇게 요소 탐색, 추가, 삭제에 의해서 일반적인 배열보다 더 빠른 시간 복잡도를 가진다.

대신 인덱스로 요소에 접근하는 경우는 일반적인 배열보다 더 느린 시간복잡도를 가진다. 

왜냐하면 인덱스로 주어진다면 해당 인덱스와 같은 키값을 찾으려면 순차 검색(O(n))을 해야 하기 때문이다.

 

이런 식으로 자바스크립트의 배열은 인덱스로 통한 데이터 접근의 단점보다는 탐색, 추가, 삭제에 의한 장점이 더 크다고 판단해 희소 배열인 해쉬 테이블로 배열을 구현한 것이다. 

 

✔️ 모던자바스크립트의 보완

 

 

모던 자바스크립트 엔진은 인덱스로 배열 요소에 접근할 때 일반적인 배열보다 느릴 수밖에 없는 구조적인 단점을 보완하기 위해 배열을 일반 객체와 구별하여 좀 더 배열처럼 동작하도록 최적화하여 구현했다.

 

다음과 같이 배열과 일반 객체의 성능을 테스트해 보면 배열이 일반 객체보다 약 2배 정도 빠르다는 것을 알 수 있다.

 

const array = [];

console.time('Array Performance Test');

for (let i = 0; i < 10000000; i++) {
  array[i] = i;
}

console.time('Array Performance Test'); // 약 340ms

const obj = {};

console.time('Object Performance Test');

for (let i = 0; i < 10000000; i++) {
  obj[i] = i;
}

console.time('Object Performance Test'); // 약 600ms

 

 

 

이 글은 자바스크립트 deep dive에 나와있는 글을 토대로 공부하여 다시 저만의 글로 각색하여 다시 만든 글입니다.

 

원본 글은 여기를 참고해주세요.