Специализация
Python Backend Developer
Java Backend Developer
Node.js Backend Developer
Golang Backend Developer
React Frontend Developer
Выберите навыки
React
JavaScript
Git
Redux
Webpack
Сложность
1-3
4-6
7-8
9-10
Рейтинг вопросов
1
2
3
4
5
Подпишись на React Developer в телеграм
Что такое хэш-таблица? Что под капотом у словаря (dict) и множества (set) в Python? (Хэш, коллизии, открытая адресация).
Хэш-таблица — это структура данных, которая хранит пары ключ-значение и позволяет быстро находить значение по ключу с помощью хэш-функции. В Python словари (dict) и множества (set) реализованы как хэш-таблицы. Коллизии (когда разные ключи имеют одинаковый хэш) разрешаются с помощью открытой адресации.
Альтернативы структуры данных dict
Вместо обычного dict можно использовать такие структуры, как collections.defaultdict, collections.OrderedDict, collections.ChainMap, types.MappingProxyType. Каждая из них решает определённую задачу: например, добавляет значения по умолчанию, сохраняет порядок или делает словарь только для чтения.
Как устроен словарь (dict) в Python? Какая структура данных лежит в его основе?
dict в CPython реализован на основе хеш‑таблицы с открытой адресацией. Ключи хешируются, индекс указывает на слот в массиве записей, где хранится пара (хеш, ключ, значение). При росте таблицы происходит расширение и перехеширование.
В чем разница между Array, Set и Dictionary?
Array — упорядоченный список, допускает дубли; доступ по индексу за O(1).Set — неупорядоченное множество уникальных элементов, поиск за O(1) в среднем.Dictionary — неупорядоченное отображение «ключ→значение», доступ по ключу за O(1) в среднем.
Что такое entry, buckets в Dictionary?
Entry - это элемент словаря, который хранит ключ, значение и дополнительную информацию. Buckets (ведра) - это индексы в массиве, которые помогают быстро находить элементы. Каждое ведро содержит ссылку на первую запись в цепочке элементов. Когда вы добавляете элемент, вычисляется хеш-код ключа, который определяет ведро для размещения элемента.
Как работает Dictionary внутри?
Как работает хеш-таблица (Dictionary) и почему она быстрее для поиска?
Для чего переопределяют методы GetHashCode и Equals и как они используются в Dictionary<TKey, TValue>?
Как работает Dictionary<TKey, TValue>: как вычисляется bucket и как влияет коллизия на производительность?
Какие коллекции в .NET существуют и зачем использовать несколько типов (массив, List, Dictionary)?
Рейтинг:
4
Сложность:
7
Dictionary в C# работает по принципу хеш-таблицы. Когда вы добавляете пару "ключ-значение", он вычисляет числовой хеш-код для ключа. Этот хеш используется для определения "корзины" (bucket), в которую будет помещено значение. При поиске значения по ключу словарь снова вычисляет хеш, находит нужную корзину и возвращает значение. Это позволяет производить поиск, вставку и удаление очень быстро, в идеале за постоянное время O(1).
Рейтинг:
1
Сложность:
5
Dictionary использует:
Хеш-функцию для преобразования ключа в индекс
Массив "ведёрок" (buckets)
Разрешение коллизий через цепочки
Поиск за O(1) в среднем случае.
Рейтинг:
2
Сложность:
7
Equals определяет, считаются ли два объекта равными по содержанию, а GetHashCode возвращает целочисленный хеш-код, используемый для распределения в бакеты Dictionary. При вставке Dictionary вычисляет hash = key.GetHashCode(), находит бакет по hash % buckets.Length, а затем в цепочке вызывает Equals для обнаружения точного совпадения ключа. Некорректная реализация может привести к потере или дублированию элементов.
Рейтинг:
2
Сложность:
5
Dictionary хранит элементы в массивах bucket’ов. Для ключа вычисляют хэш-код key.GetHashCode(), берут bucketIndex = hash % buckets.Length, и если в этом бакете уже есть запись, сравнивают ключи на равенство, переходя по связному списку (или дереву в новых версиях). При небольшой нагрузке lookup — O(1), но при многих коллизиях (одинаковых хэших) может деградировать до O(n) в худшем случае.
Рейтинг:
2
Сложность:
7
Основные коллекции:
Массив - фиксированный размер, быстрый доступ
List - динамический размер, удобные методы
Dictionary - быстрый поиск по ключу
HashSet - уникальные элементы
Queue/Stack - FIFO/LIFO
Рейтинг:
2
Сложность:
6
Рейтинг:
2
Сложность:
5
Рейтинг:
2
Сложность:
5
Рейтинг:
2
Сложность:
6
Рейтинг:
4
Сложность:
6
