Специализация
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 в телеграм
Как работает Dictionary<TKey, TValue>: как вычисляется bucket и как влияет коллизия на производительность?
Dictionary хранит элементы в массивах bucket’ов. Для ключа вычисляют хэш-код key.GetHashCode(), берут bucketIndex = hash % buckets.Length, и если в этом бакете уже есть запись, сравнивают ключи на равенство, переходя по связному списку (или дереву в новых версиях). При небольшой нагрузке lookup — O(1), но при многих коллизиях (одинаковых хэших) может деградировать до O(n) в худшем случае.
Для чего переопределяют методы GetHashCode и Equals и как они используются в Dictionary<TKey, TValue>?
Equals определяет, считаются ли два объекта равными по содержанию, а GetHashCode возвращает целочисленный хеш-код, используемый для распределения в бакеты Dictionary. При вставке Dictionary вычисляет hash = key.GetHashCode(), находит бакет по hash % buckets.Length, а затем в цепочке вызывает Equals для обнаружения точного совпадения ключа. Некорректная реализация может привести к потере или дублированию элементов.
В чем разница между Array, Set и Dictionary?
Array — упорядоченный список, допускает дубли; доступ по индексу за O(1).Set — неупорядоченное множество уникальных элементов, поиск за O(1) в среднем.Dictionary — неупорядоченное отображение «ключ→значение», доступ по ключу за O(1) в среднем.
Какие коллекции в .NET существуют и зачем использовать несколько типов (массив, List, Dictionary)?
Основные коллекции:
Массив - фиксированный размер, быстрый доступ
List - динамический размер, удобные методы
Dictionary - быстрый поиск по ключу
HashSet - уникальные элементы
Queue/Stack - FIFO/LIFO
Как работает хеш-таблица (Dictionary) и почему она быстрее для поиска?
Dictionary использует:
Хеш-функцию для преобразования ключа в индекс
Массив "ведёрок" (buckets)
Разрешение коллизий через цепочки
Поиск за O(1) в среднем случае.
Как работает Dictionary внутри?
Что такое entry, buckets в Dictionary?
Как Dictionary решает проблему прямых и косвенных коллизий?
Какие требования предъявляются к ключам в Dictionary?
Что означает уникальность ключа в Dictionary?
Рейтинг:
4
Сложность:
7
Dictionary в C# работает по принципу хеш-таблицы. Когда вы добавляете пару "ключ-значение", он вычисляет числовой хеш-код для ключа. Этот хеш используется для определения "корзины" (bucket), в которую будет помещено значение. При поиске значения по ключу словарь снова вычисляет хеш, находит нужную корзину и возвращает значение. Это позволяет производить поиск, вставку и удаление очень быстро, в идеале за постоянное время O(1).
Рейтинг:
4
Сложность:
6
Entry - это элемент словаря, который хранит ключ, значение и дополнительную информацию. Buckets (ведра) - это индексы в массиве, которые помогают быстро находить элементы. Каждое ведро содержит ссылку на первую запись в цепочке элементов. Когда вы добавляете элемент, вычисляется хеш-код ключа, который определяет ведро для размещения элемента.
Рейтинг:
4
Сложность:
7
Dictionary использует метод цепочек (chaining) для разрешения коллизий. Каждый bucket содержит индекс первой entry в цепочке элементов. При коллизии новые элементы добавляются в цепочку через ссылки next. Когда количество элементов превышает определенный порог, Dictionary увеличивает размер buckets и перераспределяет все элементы. Это уменьшает длину цепочек и поддерживает производительность.
Рейтинг:
5
Сложность:
6
Ключи в Dictionary должны соответствовать протоколу Hashable. Это означает, что для них определены корректные hash и сравнение на равенство. Одинаковые ключи должны иметь одинаковый хэш. Без выполнения этих условий словарь не сможет корректно работать.
Рейтинг:
4
Сложность:
5
Уникальность ключа означает, что в Dictionary не может существовать два элемента с одинаковым ключом. При добавлении значения с уже существующим ключом старое значение будет заменено. Словарь всегда оперирует парами «ключ–значение» с уникальным ключом.
Рейтинг:
2
Сложность:
5
Рейтинг:
2
Сложность:
7
Рейтинг:
2
Сложность:
6
Рейтинг:
2
Сложность:
7
Рейтинг:
1
Сложность:
5
