[JS] 해시 테이블 - 일반 객체 vs Map과 그 원리

Map(=연관 배열, 딕셔너리)이란?

여기서 말하는 Map은 자바스크립트가 아닌 일반적인 ADT이다.

• 키-값 형태로 저장되는 ADT.
• 같은 키를 가지는 쌍은 최대 한 개만 존재한다. (같은 값은 여러 개 가능)
• 해시 테이블 or 트리 로 구현할 수 있다.

ADT(Abstract Data Type) = 추상 자료형
구현 방법은 명시하지 않고, 특성과 작업들에 대해서만 설명하는 자료구조.
규칙들의 나열.

 

해시 테이블이란?

• 배열과 해시 함수를 사용하여 Map을 구현한 자료 구조이다.
• 평균 O(1)의 시간복잡도를 가진다.

해시 함수

• 임의의 크기를 가지는 타입의 데이터를, 고정된 크기를 가지는 타입의 데이터로 변환하는 함수.
• 해시 테이블의 해시 함수는 임의 데이터를 정수(해시값)로 변환한다.
• 이 hash값을 유한한 해시 테이블에 저장하기 위해, 해시 테이블의 크기로 모듈러 연산을 해서 저장한다.

해시 충돌

해시 충돌은 어떤 값을 넣으려고 할 때, 이미 다른 값이 존재하는 경우 발생한다.

1. 키는 다르지만 hash(해시 함수로 변환한 값)가 같을 때
2. 키도 hash도 다른데 hash % map_capa 결과가 같을 때 (모듈러 연산의 결과가 같을 때)

비둘기집 원리로, 무한한 값을 유한한 해시 테이블에 저장하려다 보면 생기는 일이다.

해시 충돌의 해결방법 1. 체이닝 (Chaining)

같은 주소에 저장되면 연결리스트로 연결

조회 시 연결된 데이터들을 순회해야 함

해시 충돌의 해결방법 2. 개방 주소법 (Open Addressing)

충돌이 일어났을 때, 충돌 주소가 아닌 다른 주소에 저장 (선형, 제곱, 이중해시 등 다른 주소를 지정하는 방법은 다양)

조회 시 정해진 규칙에 따라 다른 버킷들을 순회해야 함

그러면 어떻게 해시 테이블의 탐색을 최적화 할 수 있을까?

버킷의 크기를 키우면 된다. 삽입된 엔트리 수가 임계치를 넘으면 resize해서 버킷 수를 늘리고, 순회를 짧게 유지한다.

 

자바스크립트 객체의 생성원리

자바스크립트 객체는 Indexed Properties를 가진 객체와 Named properties를 가진 객체로 나누어진다.

• Indexed Properties: [1, 2, 3] or {1: "a", 2: "b"}
• Named properties: {"first": 1, "second": 2}

히든 클래스

• 이 중 Named properties를 가진 객체는 히든 클래스를 참조한다. 히든 클래스는 객체의 모양 정보를 저장하고 있다.
• 동일한 구조를 가진 객체는 동일한 히든 클래스를 공유한다.

 

아래 코드의 힙 스냅샷을 찍어보자.

class HiddenClass {
    #name;
    constructor(name) {
        this.#name = name;
    }
}

const ham = new HiddenClass("ham");
const jam = new HiddenClass("jam");

Map @87495 이부분이 히든 클래스 id를 나타내는 것이라고 한다. 같은 히든 클래스를 가리키고 있다.

 

그런데 여기서 ham.a = 1; 딱 요 코드만 추가하면? ham의 Map id가 바뀐 것을 알 수 있다.

 

이것이 바로 히든 클래스 전이이다. 새로운 Named properties를 추가하면 전이된다.

 

이제 다시 jam.a = 2; 를 해줘서 같은 프로퍼티를 추가하면? 다시 두 객체가 같은 히든 클래스를 가리키게 된다.

Named properties

위에서는 Named properties가 히든 클래스 전이를 유발한다고 했다. 그런데 사실 이 Named properties는 세 종류로 나뉘어진다. 히든 클래스 전이를 유발하는 프로퍼티는 Fast properties 뿐이다.

In-object properties

• 객체에 직접적으로 저장되어 가장 빨리 접근 가능
• 프로퍼티 수가 객체의 크기에 따라 미리 제한된다.
• 객체 크기보다 더 많은 프로퍼티가 추가되면 객체 내부가 아니라 프로퍼티 저장소(히든 클래스가 참조하는)에 저장된다.

Fast properties

• 프로퍼티 저장소가 참조하고 있는 배열에서 인덱스로 접근 가능
• 같은 히든 클래스끼리는 인라인 캐시 사용해서 빠르다

"현재 히든 클래스에서 'a' 프로퍼티는 인덱스 0번에 있구나!"
→ 이 정보를 인라인 캐시에 저장
→ 이후 같은 히든 클래스를 가진 다른 객체에서 'a' 프로퍼티를 참조하면 인라인 캐시를 통해 바로 0번 인덱스임을 알 수 있어 빠르다.

Slow(Dictionary) properties

프로퍼티 추가와 삭제가 많이 일어나면, 위에서 알아봤듯 히든 클래스 전이가 계속해서 일어나게 된다. 이 히든 클래스들을 저장하기 위해 많은 시간과 메모리 오버헤드가 들기 때문에 Slow properties가 등장하였다.

• 프로퍼티 저장소에 키와 값이 바로 저장, 해시 테이블 구조로 관리
• 이 때문에 새로운 히든 클래스를 생성하지 않음
• 그러나 인라인 캐시를 사용할 수 없고, 해시 계산과 충돌 해결 과정 때문에 더 느리다

 

직접 실험하기

사실 여러 글에서 이에 대해 다루고 있지만, 정량적으로 어떨 때 어떻다라는 것은 잘 보지 못해 직접 실험해보았다.

Map

N과 상관 없이 모든 프로퍼티가 OrderedHashMap이라는 해시 테이블에 저장된다.

N=10

정적 객체 리터럴

10개 프로퍼티 모두 In-object로 추가된다.

동적 객체 리터럴 - for문으로 추가

4개까지만 In-object로 추가, 나머지는 PropertyArray에 추가된다(Fast Property).

N=100

정적 객체 리터럴

100개 모두 In-object로 추가된다.

동적 객체 리터럴 - for문으로 추가

100개 모두 NameDictionary에 Slow properties로 추가된다.

N이 더 커지면...

정적인 객체 리터럴은 어디까지 되나 보자 하고 실험했는데, 128개까지 In-object 프로퍼티로 추가되었다. 그 이후는 Fast properties로 추가된다.

 

자바스크립트에서 객체 vs Map with GPT

위 실험에서 알아낸 실제 프로퍼티들이 저장되는 자료구조 NameDictionary와 OrderedHashMap을, V8 깃허브 소스코드를 까서 알아봐달라고 GPT에게 부탁했다. 결과는 아래와 같다.

	객체 (Slow properties) NameDictionary	Map OrderedHashMap
해시 충돌 해결	Open Addressing 기반 / Linear probing	Separate Chaining + 삽입 순서 유지 / 체인 리스트 (bucket + linked)
순서 보존	❌ 없음	✅ 있음 (삽입 순서 유지)
코드 위치 in V8	dictionary.h / name-dictionary.h	ordered-hash-table.h

즉, 해시 충돌을 해결하는 방법에 있어서 Map이 더 최적화되어 있어 삽입/삭제에 유리하다.

 

그래서 뭘 언제 써야한다고?

정적 객체 리터럴일 때는 In-object, 128개를 넘어가더라도 Fast Property로 처리되기 때문에 Map보다 더 빠르다.

그러나 이 객체 리터럴을 동적으로 활용하려고 하면 4개까지만 In-object로 처리되며, 더 많아지면 그냥 전체 프로퍼티가 Slow Property로 저장되어 굉장히 느려지기 때문에 Map을 사용하는 것이 좋다.

 

참고자료

쉬운코드 - 해시 테이블

https://v8.dev/blog/fast-properties

https://engineering.linecorp.com/ko/blog/v8-hidden-class