Рубрики
Без рубрики

Введение в хеширование

Прежде чем читать эту статью, пожалуйста, убедитесь, что у вас есть базовое представление о структурах данных a… С тегами java, программирование, новички, безопасность.

Прежде чем читать эту статью, пожалуйста, убедитесь, что у вас есть базовое представление о структурах данных и алгоритмах. Спасибо!! 😉

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

  1. Массивы – Это наиболее распространенная структура данных, но когда мы пытаемся сохранить в ней эти данные, наиболее распространенный запасной вариант, который возникает при поиске данных. Для поиска требуется O(n) времени. И даже если бы мы использовали отсортированный массив для поиска, это все равно заняло бы O (log (n)) времени, а затем это также повлияло бы на вставку и удаление.

  2. Связанный список – Это также одна из широко используемых структур данных, но она чем-то похожа на массив, поскольку поиск в ней также осуществляется линейным способом. Таким образом, это также не было бы эффективным подходом для хранения наших данных.

  3. Бинарные деревья поиска – Это также отличный инструмент, состоящий из узлов и связанных списков. Поскольку мы будем использовать эту структуру данных для хранения ваших данных, в среднем для выполнения операций вставки, поиска и удаления потребуется O(log(n)) времени. Он обеспечивает умеренно хороший выбор по сравнению с массивами и связанными списками.

  4. Таблица прямого доступа (ДАННЫЕ)

Но DAT имеет практические ограничения, так как, во-первых, для их хранения требуется огромное пространство. Например, если номер телефона состоит из n цифр, нам нужно O (m * 10 ^ n) места для таблицы, где m – размер указателя для записи. Другая проблема заключается в том, что целое число в языке программирования может не храниться рядом с цифрами.

Итак, это когда Хэширование входит в картину. На сегодняшний ДЕНЬ это в основном улучшение. Основная идея, лежащая в его основе, состоит в том, чтобы преобразовать номер телефона в маленький ключ и использовать этот ключ в качестве индекса в Хэш-таблице . Мало того, хеширование выполняется намного лучше, чем перечисленные выше структуры данных, например, мы получаем O (1) как среднюю временную сложность поиска элемента.

Итак, что такое хеширование? Книжное определение – Хеширование – это процесс преобразования заданного ключа в другое меньшее значение за O (1) время поиска. Это делается с помощью функции, называемой хэш-функцией , для сопоставления данных с некоторым зашифрованным или упрощенным репрезентативным значением, которое называется “хэш-код” или “хэш”.

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

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

Пожалуйста, дайте свои предложения и отзывы в комментариях:)

Оригинал: “https://dev.to/sharmakeshav1030/introduction-to-hashing-2o01”