Хеш-таблицы из 20 слов или меньше:
– Структура данных, состоящая из неупорядоченных, неиндексированных пар "ключ-значение"
– Сверхбыстрый поиск, операции вставки и удаления.
Если вы обнаружили, что задаетесь вопросом, «что за хэш-таблицы непонятны», вот краткий ответ.
Что такое хеш-таблица?
Хеш-таблицы — это структуры данных, включенные в большинство языков программирования. Итак, что такое структура данных? Структуры данных — это такие вещи в языках программирования, как наборы, кортежи, списки или массивы. Данные в любой заданной структуре данных организованы определенным заранее определенным образом.
Различные языки кодирования могут иметь разные структуры данных или могут иметь схожие структуры данных, но давать им разные имена. Например, хеш-таблица в Python называется словарем, а в JavaScript — объектом.
Так что же такое хеш-таблица? Это неупорядоченный список пар ключ-значение. В отличие от многих других структур данных, таких как массивы, он не индексируется. Другими словами, вы не можете искать ключ в какой-либо конкретной позиции, например, в индексе 3. Поэтому вам действительно нужно использовать ключ для поиска значения. Как в старомодном печатном словаре (помните те..?), где вы будете искать ключевое слово, а не 5-е слово на данной странице.
Почему «хэш»? Что за ерунда по этому поводу?
Теперь будьте готовы к тому, что вас перенесет в декорации шпионского романа, потому что именно здесь начинается самое интересное с хеш-таблицами. Если вы когда-либо создавали секретный код, сценарий или язык со своими школьными друзьями, вы уже знаете основы «хеширования». (Если вы один из тех счастливчиков, которые пропустили такие игры в детстве, вы можете поискать языковую игру, такую как Pig Latin, чтобы понять, о чем я говорю.)
Для простоты хеширование — это использование набора предопределенных правил, в соответствии с которыми обычное слово, буква или другой символ заменяются словом, группой символов или цифрами, которые не имеют смысла для человека, который не знаю правил конвертации.
Чтобы дать вам пример, вы можете решить переместить каждую букву на один индекс вверх в алфавите. Так что мое имя «Анника» будет затем преобразовано в «Буджльб».
Эти правила преобразования, кстати, называются «хеш-функцией». В программировании эти хеш-функции более сложны и, вероятно, чаще включают в себя какое-то математическое преобразование, а не просто изменение букв. Важно отметить, что хэш-функция всегда будет приводить к одному и тому же результату для одного и того же ввода или ключа. Однако несколько ключей могут быть хешированы в один и тот же вывод хеш-функции. Эти «коллизии» разрешаются способами, которые выходят за рамки этой статьи, но вы можете быть уверены, что в языках программирования есть способы справиться с этим.
Так почему мы занимаемся этим секретным агентом?
Представьте, что у вас есть список из тысячи пар ключ-значение. Например, каталог продуктов, указывающий код продукта в качестве ключа и соответствующую цену в качестве значений, связанных с каждым ключом. Не существует логического способа упорядочить или проиндексировать эти ключи. Как вы гарантируете, что сможете быстро найти цену, не просматривая сначала несколько сотен ключей, прежде чем найдете тот, который ищете?
Представьте себе, что память компьютера, которая используется для сохранения данных в вашей структуре данных, будет состоять из ряда пронумерованных и упорядоченных «ячеек». Например, вы создаете массив, содержащий 5 значений. Компьютер будет искать пространство памяти из 5 последовательных ячеек для хранения массива. Допустим, первой свободной ячейкой памяти является ячейка с номером 1000. Таким образом, он резервирует ячейки с 1000 по 1004 для массива, сохраняя значение с индексом 0 в ячейке 1000, с индексом 1 в ячейке 1001 и т. д.
В этом случае, если бы вы искали значение по заданному индексу, компьютеру просто нужно было бы перейти к конкретной ячейке, посмотреть, что там находится, и вернуть значение. Но если вы собираетесь искать значение без индекса, а заданный массив состоит не из 5, а из 1000 значений, вам придется перерыть много памяти, чтобы найти правильное значение.
Пары ключ-значение, такие как хэш-таблицы или словари, не имеют индекса и поэтому не могут быть найдены по индексу. Чтобы не приходилось перебирать сотни ключей, чтобы найти искомое значение, хэш-таблицы хранятся уникальным образом. В зависимости от размера вашей хэш-таблицы (и некоторых других факторов, таких как коэффициент загрузки, который я не буду здесь подробно объяснять), компьютер будет резервировать определенный объем памяти, который немного превышает количество хранимых пар ключ-значение. .
Помните, что каждая ячейка памяти пронумерована и поэтому может быть однозначно идентифицирована и прочитана за один шаг. Теперь, если вы введете пару ключ-значение, компьютер возьмет ключ и преобразует этот ключ с помощью хеш-функции в числовое значение. В примере с каталогом товаров допустим, что ключом является номер продукта «485-xs-gr» для конкретной футболки размера xs и зеленого цвета. Номер продукта — это ключ, который компьютер преобразует в числовое значение. Допустим, хеш-функция вычисляет значение 687 для нашего ключа «485-xs-gr». Затем компьютер сохранит значение, связанное с этим ключом, в ячейке памяти номер 687 зарезервированной памяти. Таким образом, в нашем примере это может быть цена 12,99 евро, которая будет храниться в ячейке памяти 687.
Так к чему тогда все это?
Итак, если вы теперь попросите компьютер дать вам цену продукта «485-xs-gr», ему больше не придется искать среди сотен продуктов, а просто будет использовать хеш-функцию для вычисления места хранения значения, которое вы ищете и, таким образом, может за один шаг предоставить вам цену, которую вы ищете. Это значительно ускорит поисковые операции. На самом деле, не только поиск, но и вставка или удаление элементов таким образом намного быстрее.
Что нужно знать о хеш-таблицах?
То, что вам нужно знать о хеш-таблицах, зависит от того, что вы делаете с языками программирования или хеш-таблицами. Для большинства программистов должно быть достаточно понимания (временной) эффективности хеш-таблиц и того, какая структура данных работает как хеш-таблица в используемом ими языке программирования.
Если вы хотите создать или поддерживать язык программирования, возможно, вы захотите более подробно изучить эффективное хеширование под капотом этих структур данных. Но большинству из нас это действительно не нужно.
Дальнейшее чтение
Наконец, если вы нашли такое объяснение полезным, я могу горячо порекомендовать книгу Джея Венгроу «Руководство здравого смысла по структурам данных и алгоритмам». Многое из того, что я знаю, я узнал из его книги. И у него есть уникальный способ объяснить вещи таким образом, что сложные вещи кажутся очень простыми.