Быстрая шпаргалка / мини-викторина по HashTables, чтобы освежить в памяти основы.

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

Просматривая блог, попытайтесь ответить на вопросы своими словами, прежде чем смотреть на предоставленный ответ.

Каковы некоторые другие названия для хеш-таблицы?

  • Хэш-карты
  • Карты
  • Неупорядоченные карты
  • Словари
  • Объекты

*в зависимости от языка будут небольшие отличия, но они будут иметь встроенную хеш-таблицу

JS → Объект
Python → Словари
Java → Карты
Ruby → Хэши

Что такое хеш-таблица?

  • Хэш-таблицы — это структура данных, в которой хранятся данные с парами ключ-значение.
  • Ключи используются в качестве индекса для поиска данных в памяти.
  • Данные известны как «значение» → хеш-таблицы создают «пары ключ-значение».

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

Что такое хэш-функция?

Хеш-функция — это просто функция, которая генерирует значение фиксированной длины для каждого полученного ввода.

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

Каковы ключевые аспекты хеш-функций?

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

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

В чем преимущество хеш-функции? Зачем нам использовать его в структуре данных? Как это делается?

  • Мы получаем очень быстрый доступ к нашим данным.
  • Хеш-функция возьмет ключ → преобразует его в хэш → затем преобразует хэш в индексное/адресное пространство, где будут храниться данные для ключа.
  • Когда мы просматриваем данные, нам просто нужно передать ключ → функция генерирует хэш → и мы сразу знаем, где получить наши данные.
  • Поскольку у нас есть адрес хэша/индекса, мы можем очень быстро искать данные.
  • Хеш-функции, встроенные в языки для хеш-таблиц, намеренно очень быстрые, чтобы обеспечить быстрый поиск. Мы можем предположить, что их bigO равно O(1) → постоянное время.

Кратко рассмотрим процедуру добавления/получения данных в хеш-таблицу.

1. Создать ключ — -› передать хеш-функции строку
2. Преобразовать ключ в хеш
3. Использовать хэш для создания/нахождения индекса/адресного пространства в памяти
4а. Сохраните пару ключ-значение (данные) в адресном пространстве (для добавления)
4b. Доступ к адресному пространству в памяти и извлечение значения/данных (для извлечения)

Что такое BigO для операций с хеш-таблицами? Как они работают под капотом?

  • вставка → O(1)
    *хешировать ключ → автоматически помещает его в адресное пространство, которое было получено
    **если нет коллизии → O(n)
  • поиск → O(1)
    *то же самое → передать ключ→ ключ хэшируется → мы используем хэш для поиска точного пространства, чтобы найти наше значение/данные
    ** если нет коллизии → O (н)
  • удалить → O(1)
    *same → использовать ключ → сразу мы знаем, откуда удалить элемент → потому что он не упорядочен, нам не нужно сдвигать индексы, как массивы, поэтому нет O(n)
  • поиск → O(1)
    *просто используйте хэш-функцию, чтобы проверить, есть ли значение

Что вы можете хранить в хеш-таблице?

Разные языки будут по-разному реализовывать хеш-таблицы.

Однако обычно ключ и значение могут относиться к любому типу данных → разрешены все типы данных.

Это сказало. В Javascript ES6.

Хэш-таблицы:
* всегда будут иметь свои ключи в виде строк → будь то целое число или функция, они будут преобразованы в строку. Значения могут быть любого типа данных, включая функции.
** не имеет порядка → данные хранятся случайным образом

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

Наборы хэшей:
* хранит только ключи, но не значения.

Что такое столкновение?

Когда двум отдельным клавишам назначается одно и то же место в памяти.

Примечание: это происходит, когда два разных ввода дают один и тот же результат при хэшировании (при хешировании входные данные X сопоставляются с фиксированным # символом).

* невозможно предсказать коллизии и считается приемлемым риском — поэтому хеширование по-прежнему используется для обеспечения целостности и неотказуемости

Как происходит столкновение?

Столкновения происходят случайно.

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

Как столкновение влияет на время выполнения?

Если возникают коллизии, теоретически это замедляет чтение и запись до → O(n/k) → k равно размеру хеш-таблицы → оно разрешается до → O(n)

Существует несколько распространенных способов разрешения коллизий:

- отдельная цепочка
- открытая адресация
- хэширование в стиле Робин Гуда

(см. страницу вики, чтобы узнать больше)

Зачем использовать хеш-таблицу вместо массива?

Хеш-таблицы отлично подходят для быстрого доступа к определенным значениям.

  • Поиск → O(1)
    *часто используется в базах данных
  • вставка → O(1)
    *в большинстве случаев нам не нужно беспокоиться о столкновении
  • поиск → O(1)
  • удалить → О(1)

По сравнению с массивом:

  • поиск → O(n)
  • вставить → О (п)
  • поиск → O(1)
  • * нажать → О (1)
  • удалить → О (п)

Каковы сильные и слабые стороны хеш-таблиц?

  • Более быстрый поиск (если включено хорошее разрешение коллизий — как в большинстве языков). Более быстрые вставки. Гибкие клавиши (в зависимости от языка)
  • Более медленная итерация ключа → O(n).
    Неупорядоченная/разрозненная память → увеличивает время поиска всех адресов в памяти.

В чем компромисс с хеш-таблицами?

  • Компромисс — улучшенная временная сложность благодаря более быстрому доступу к данным.
  • Стоимость → требует больше памяти → большая космическая сложность O (n).

Как бы вы реализовали свою собственную хеш-таблицу?

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

Вот и все для этой мини-викторины/шпаргалки. Надеюсь, это пощекотало ваш мозг, и вы хорошо провели время!