Техпрогон
ВойтиНачать бесплатно
По порядку Middle Коллекции и строки обновлено

Как Dictionary находит значение по ключу

Вопрос

Расставьте шаги поиска dict[key] в хеш-таблице Swift по порядку.

Попробуйте сами

Расставьте шаги по порядку стрелками.

  1. 1
    При совпадении ключа возвращается значение, при пустой корзине nil
  2. 2
    Если корзина занята, ключ в ней сравнивается с искомым через ==
  3. 3
    Вызывается hash(into:) у ключа, получается хеш с сидом процесса
  4. 4
    По хешу вычисляется номер корзины в таблице
  5. 5
    При несовпадении проверяется следующая корзина (линейное пробирование)
Показать ответ и разбор

Коротко

Swift использует открытую адресацию с линейным пробированием. Поэтому оба требования Hashable важны: хеш выбирает место, а == подтверждает ключ.

Правильный порядок

  1. 1
    Вызывается hash(into:) у ключа, получается хеш с сидом процесса
  2. 2
    По хешу вычисляется номер корзины в таблице
  3. 3
    Если корзина занята, ключ в ней сравнивается с искомым через ==
  4. 4
    При несовпадении проверяется следующая корзина (линейное пробирование)
  5. 5
    При совпадении ключа возвращается значение, при пустой корзине nil

Разбор

Swift использует открытую адресацию с линейным пробированием. Поэтому оба требования Hashable важны: хеш выбирает место, а == подтверждает ключ. Сид хеширования случаен на каждый запуск.

Ответьте сами, а не прочитайте

В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.

Потренироваться бесплатно

Предыдущий вопрос

Изменение ключа после вставки в Set

Следующий вопрос

Что выведет Swift: группировка через reduce(into:)

Урок по теме

Коллекции и строки в Swift

Ещё по теме «Коллекции и строки»

Все вопросы модуля