Руководство для начинающих по хеш-таблицам
Продолжая свой путь, работая над алгоритмами, готовясь к следующему техническому собеседованию, я столкнулся с проблемой, которая в конечном итоге привела меня в мир хеш-таблиц. Как сделал бы любой хороший разработчик, я глубже изучил, что такое хеш-таблицы и как они могут быть полезны для написания эффективного кода.
Что такое хеш-таблицы?
Хеш-таблицы - это структуры данных для хранения пар ключ / значение. Хеш-таблицы содержат слоты, называемые корзинами, для хранения элементов. Количество этих сегментов или слотов представляет длину нашей хеш-таблицы. Например, если у нас есть хеш-таблица длиной 1000, это означает, что в ней есть 1000 слотов или корзин для хранения 1000 элементов. В хэш-таблицах используется хеш-функция для эффективного сопоставления ключей со значениями, для эффективного поиска элемента, вставки элемента и удаления элемента.
Функции хеширования
Как упоминалось выше, хеш-таблицы используют хеш-функции для хранения значения в нашей хеш-таблице. Число, определяющее индекс, будет получено в результате хеширования нашей метки с помощью функции хеширования. Функция хеширования принимает два входа, любой тип данных и число. Число - это длина нашей хеш-таблицы, так как функция может возвращать числа, равные длине массива. функция хеширования сообщает нам, где найти элемент в массиве, введя ключ. По сути, функция сопоставляет тип данных с числом. В идеале наша функция хеширования будет выводить уникальные номера индексов для каждого ключа.
Хеш-таблицы в действии
Как работает хеш-таблица с использованием поиска по ключу, значению
1. Вы берете ключи ввода, запускаете его через хэш-функцию, где он отображает эти ключи ввода в числа, которые соответствуют количеству индексов в массиве.
2. Выполните эти входные данные с помощью хэш-функции. Есть много разных способов кодирования хэш-функции, но, по сути, хеш-функция должна принимать входные данные, тип данных, а затем преобразовывать их в целое число и, наконец, преобразовывать это целое число в индекс в массиве.
3. Теперь у нас есть ассоциативные ценности. Где теперь мы можем искать, вставлять и удалять наши данные с помощью индекса Array.
Почему хеш-таблицы?
Когда я углубился в хеш-таблицы, я обнаружил, что они используют массив для хранения элементов. Я быстро спросил себя: «Какой смысл использовать хеш-таблицы, если они используют массивы для хранения, почему бы просто не использовать простой массив?» Да, вплоть до сути вещей, но помните также, что структуры данных, такие как хеш-таблицы, - это методы, которые делают ваш код более эффективным! Хеш-таблицы - один из наиболее популярных методов из-за их эффективности.
Хеш-таблицы являются предпочтительной структурой данных, потому что в среднем они обеспечивают временную сложность O (1) для вставки, удаления и поиска, что довольно быстро по сравнению со всеми другими методами структуры данных. Хеш-таблицам не нужно просматривать каждую корзину или слот в поисках значения, потому что оно связано с ключом. Все, что потребуется хеш-таблице, - это ключ, чтобы напрямую найти ее значение.
