Производительность поиска ключа в объекте JavaScript

Question

Я только что прочитал этот вопрос: есть ли в javascript словари, подобные python?

В одном из ответов говорилось, что вы можете использовать объекты JavaScript, такие как словари Python. Это правда? Какова производительность поиска ключа в объекте? Это O (1)? Добавляет ли ключ к объекту также постоянное время (хеширование)?

Answer 1

Документы V8 Design подразумевают, что поиск будет по крайней мере таким быстрым, если не быстрее:

Большинство механизмов JavaScript используют словарную структуру данных в качестве хранилищадля свойств объекта - каждый доступ к свойству требует динамического поиска для определения местоположения свойства в памяти.Этот подход делает доступ к свойствам в JavaScript обычно намного медленнее, чем доступ к переменным экземпляра в языках программирования, таких как Java и Smalltalk.В этих языках переменные экземпляра расположены с фиксированными смещениями, определенными компилятором из-за фиксированной структуры объекта, определенной классом объекта.Доступ - это просто вопрос загрузки или сохранения памяти, для которого часто требуется только одна инструкция.

Чтобы сократить время, необходимое для доступа к свойствам JavaScript, V8 не использует динамический поиск для доступа к свойствам.Вместо этого V8 динамически создает скрытые классы за кулисами.[...] В V8 объект изменяет свой скрытый класс при добавлении нового свойства.

Похоже, что добавление нового ключа может быть немного медленнее,из-за создания скрытого класса.

Answer 2

Да, вы можете предположить, что добавление ключа и последующее использование его для доступа - это эффективно операций с постоянным временем.

Под капотом движок JS может применять некоторые методы для оптимизации последующих поисков, но для целей любого алгоритма можно принять O (1).