Какова временная сложность доступа к значению по ключу в объекте или Map (хеш-таблице)?

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

Как это работает

• Хеш-функция превращает ключ в число (хеш).
• По модулю размера массива получается индекс корзины (bucket).
• В корзине хранится значение или список коллизий.
• При поиске хеш вычисляется снова, и мы сразу попадаем в нужную корзину.

В идеальном случае каждая корзина содержит один элемент, и доступ занимает O(1). Однако если два разных ключа дают одинаковый хеш (коллизия), элементы складываются в список, и поиск может занять O(k), где k — длина цепочки. В худшем случае все ключи попадают в одну корзину, и сложность становится O(n).

Пример на JavaScript

const obj = { name: 'Alice', age: 30 };
console.log(obj.name); // O(1) в среднем

const map = new Map();
map.set('name', 'Alice');
map.set(42, 'answer');
console.log(map.get(42)); // O(1) в среднем

// Коллизии в объекте (упрощённо)
const collision = {};
collision['a'] = 1;
collision['b'] = 2; // разные ключи, но могут попасть в одну корзину

Object vs Map

• Object: ключи только строки и символы, порядок вставки не гарантирован для числовых ключей.
• Map: ключи любого типа, сохраняет порядок вставки, имеет свойство size, лучше подходит для частых добавлений и удалений.

В среднем обе структуры дают O(1) на доступ, вставку и удаление. Но при плохой хеш-функции или большом количестве коллизий производительность падает.

Итог: используйте объекты или Map для быстрого поиска по ключу, когда важна скорость O(1). Map предпочтительнее, если нужны нестроковые ключи или частые изменения размера.