Что такое Хеш-таблица, Хеш-функция, Хеширование - простыми словами, пожалуйста

Question

Что такое Хеш-таблица, Хеш-функция, Хеширование - простыми словами, пожалуйста

Amorrey Ученик (129), закрыт 7 месяцев назад

Answer 1

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

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

Хеширование — это процесс применения хеш-функции к ключу, чтобы получить индекс, по которому будет храниться соответствующее значение в хеш-таблице. Например, если у вас есть хеш-таблица размером 10, ключ "анна" может преобразоваться в индекс 3, а ключ "иван" — в индекс 7.

Answer 2

Хеш-функция/хеширование:

Вводишь что угодно (серьёзно: файл, текст, символ).
Получаешь на выходе фиксированную строку в n символов, допустим 32.
Один и тот же файл будет иметь один и тот же хеш.
Хеш нельзя прогнать обратно (восстановить, то, что было закодировано).
Коллизии (два разных текста дают один и тот же хэш) мало вероятны, поэтому ими можно принебречь.

Примеры: md5 (устаревший), серия SHA

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

Answer 3

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

Answer 4

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

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

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

Answer 5

Идея ускорения поиска в больших массивах, не зависящая от объёма (но зависящая от заполнения). Всё в машине представлено числами, из искомой информации формируют число по одному из многих алгоритмов (например, просто складывают). Так формируется адрес в пространстве поиска. Если там что-то есть и надо найти, то нашли, а если надо поместить, то возникает коллизия. Её разрешают тем, что переходят на "другой слой".

Answer 6

Хеш-таблица это вот такая штука
https://otvet.mail.ru/question/238147690