Если вы новичок в структуре данных или только что закончили первый квартал в качестве студента факультета CS, вы все еще можете не знать, как работает хеш-таблица. В этой статье я хочу рассказать о том, как работает хеш-таблица без единого кода, чтобы дать вам базовую аналогию с ней.
По сути, хеш-таблица - это словарь пар ключ-значение. Что отличает его от обычного словаря, так это процесс «хеширования». Прежде чем ключ окажется в сегменте / слоте, необходимо выполнить «хеширование», чтобы найти индекс сегментов, поскольку этот конкретный сегмент будет содержать пару ключ-значение в будущем. Это одна из причин, по которой хеш-таблица имеет высокие средние показатели по корпусу.
Хорошо, вы можете понять суть хеш-таблицы, а можете и нет. Не волнуйтесь, я знаю, что это случится. Давайте просто воспользуемся повседневным примером в этом случае. Здесь я провожу аналогию для каждого ключевого слова, которое мы будем использовать.
Аналогия:
- Ключ = Корзина
- Ценность = что угодно
- Индекс = тип этого конкретного мусора; это может быть компост, переработка или свалка
- Ведра = массив мусорного ведра
Хэш
«Хеширование» - это процесс сортировки этих ключей / мусора, чтобы определить тип этого конкретного мусора или «индекса». Как только индекс известен, мы можем выбросить мусор в нужную корзину или «ведро».
Это последовательность вставки элемента в хеш-таблицу:
- У вас должен быть ключ и ценность. Давайте представим, что ключ - это бумаги, а его ценность - это количество этих бумаг, то есть 2. Теперь у вас есть мусор, и ваша задача - выбросить этот мусор в правильную корзину.
2. Давайте «хэшируем» !. Найдите тип мусора.
3. Выбросьте в нужное «ведро» или в хлам !!!
Столкновение:
Что ж, очевидно, у вас теперь есть бумаги в вашей корзине, но вы также хотите выбросить еще одну бумагу, которая вам не понадобится. Да, очевидно, повторить нашу последовательность вставки и бросить в то же ведро. Но, к сожалению, хеш-таблица работает не так.
Если вы хотите узнать, как бороться с коллизиями, вы можете посмотреть это руководство на языке Python или прокомментировать ниже, если вы хотите увидеть часть 2 этой статьи😁.