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

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

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

Аналогия:

  • Ключ = Корзина
  • Ценность = что угодно
  • Индекс = тип этого конкретного мусора; это может быть компост, переработка или свалка
  • Ведра = массив мусорного ведра

Хэш

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

Это последовательность вставки элемента в хеш-таблицу:

  1. У вас должен быть ключ и ценность. Давайте представим, что ключ - это бумаги, а его ценность - это количество этих бумаг, то есть 2. Теперь у вас есть мусор, и ваша задача - выбросить этот мусор в правильную корзину.

2. Давайте «хэшируем» !. Найдите тип мусора.

3. Выбросьте в нужное «ведро» или в хлам !!!

Столкновение:

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

Если вы хотите узнать, как бороться с коллизиями, вы можете посмотреть это руководство на языке Python или прокомментировать ниже, если вы хотите увидеть часть 2 этой статьи😁.