JavaScript에서 해시 테이블을 구현하는 방법

Question

일부 언어는 문자열이 아닌 키를 키로 사용할 수있는 해시 테이블을 구현합니다. JavaScript에서는 문자열과 숫자로 제한됩니다. 이런 종류의 구현에 대한 조회가 여전히 O (1)입니까? JavaScript로 구현 되었습니까?

Answer 1

분명히이 주제에 대해 많은 오해가 있습니다. JavaScript에서 객체의 키는 실제로 문자열 인 (§8.10 참조) 만 있습니다. 무엇이든 (숫자 포함)을 객체 키로 사용하여 문자열로 변환합니다. 따라서 obj[1] 및 obj["1"]은입니다.

내부적으로 많은 JS 구현은 개체 속성을 빠르게 검색 할 수 있도록 일종의 해시 테이블을 사용합니다. V8 실제로 generates hidden C++ classes 단일 CPU 명령에서 조회를 실행할 수 있습니다. 어느 쪽이든, 객체 속성 액세스가 빠르며 O (1) 근처에 있다고 가정하는 것이 안전합니다.

모든 개체 속성 키가 문자열로 변환 되었기 때문에 문자열로 변환하는 항목 만 키로 사용할 수 있습니다. 숫자가 자연스럽게 문자열로 변환되기 때문에 잘 작동합니다. 불리언들도 마찬가지입니다. Date 인스턴스가 고유 문자열로 변환되기 때문에 날짜도 작동합니다 (알고 있어야하는 가장자리 사례가 있음에도 불구하고).

그러나 개체는 의미있는 문자열로 변환되지 않습니다.예를 들면 다음과 같습니다 때문에 string conversion rules의

o = { '[object Object]': 'some value' } 

:

var o = {}; 
o[{a:1}]='some value'; 

사실을 초래한다. 모든 개체가 으로 변환되므로 많은 개체를 다른 개체의 키로 추가하면 하나의 속성 만있는 개체가됩니다.

물론 개체를 키로 사용할 수 있습니다. 사실상 toString —의 기본 구현을 재정의해야만 자신의 해싱 알고리즘을 만들 수 있습니다.

o = { 
    '1:2': 'x', 
    '3:4': 'y' 
} 

Answer 2

JavaScript에는 "해시 테이블"이 없습니다.

키가 고유해야한다는 제한과 함께 키/값 쌍의 모음 인 Dictionaries이 있습니다. 차이점은 사전 구현이 해시를 의미하지는 않지만 성능상의 이유로 구현시 내부적으로 Hash table이 사용된다는 것입니다.

모두 JavaScript의 개체는 사전 (예 : string 및 number과 같은 제외 된 기본 유형)에서 작동합니다.

var o = {}; 
o[propExpression] = valueExpression; 

그러나 여기에서 중요한 것은 : 일반적으로 빈 객체는 일반적인 "해시 테이블"에 사용되는 모든 재산/키 값이 먼저를 문자열로 변환됩니다.

따라서 다음과 동일하다

을 : ECMA 스크립트는 다소 혼란을

---

o[true] = 1 
o["true"] = 1 

따르는하지만 속성 이름 Property Descriptors 검색된 모든 문자열 "알지"의 핵심

속성 식별자 유형은 속성 이름을 속성 설명자와 연결하는 데 사용됩니다. 속성 식별자 유형의 값은 형식 (이름, 설명자), 쌍이며 name은 문자열이고 설명자는 속성 설명자 값입니다.