자바스크립트의 배열 인덱스 접근은 왜 O(1)인지

자바나 c언어에서는 변수를 선언할 때 타입까지 한 번에 지정해줘야한다.

특히 단일 타입만을 지정해야한다. 그런데 자바스크립트는 타입 지정을 안하고 변수 선언을 하다보니 하나의 배열에 원시 타입이나 객체 타입을 뒤죽박죽으로 넣을 수 있다. 

자바 , c에서는 인덱스 접근 시 변수에 담긴 배열의 첫 주소(포인터)+ index*typeSize  로 한번에 메모리에 접근하여 이 O(1)로 맞춰진다. 

하지만 타입 사이즈를 보장하지 않는 자바스크립트는 어떻게 O(1)이 될까?

답은 v8과 같은 자바스크립트 엔진에 있었다. 우선 빌드 시까진 낙관적으로 접근을 하고 컴파일 시 해당 배열이 단일 타입으로 이루어진 빠른 배열이라면 자바처럼 포인터+index*typeSize로 인덱스에 접근한다. 하지만 여러 타입이 섞인 느린 배열은 해시로 변환 되어 아래처럼 변환 됨.

const arr = [1, "hello", {name: "zerojin"}];
// 실제로는 이런 구조:
// {
//   0: 1,
//   1: "hello", 
//   2: {name: "zerojin"},
//   length: 3
// }

해시맵에서의 요소 접근은 O(1) 이기에 자바스크립트 배열의 인덱스 접근 또한 O(1)을 보장함