Карты хеширования могут решить множество различных проблем
Хеширование - это традиционный подход в информатике, при котором структуры данных, называемые хэш-картами, используются для хранения пар ключ-значение . Помимо хранения пар "ключ-значение", хеш-карты можно использовать для решения широкого круга задач в области информатики. При использовании с очередями приоритета и другими адаптерами контейнеров, такими как стеки и очереди, хэш-карты могут ускорить решение проблем за счет уменьшения сложности времени выполнения.
Давайте углубимся в основную концепцию хэш-карт, их использование в C ++ и приложения для решения некоторых из наиболее важных проблем.
Концепция хэш-карт
Карты хеширования обычно хранят элементы в виде пар ключ-значение. Рассмотрим следующий пример: мы хотим сохранить список продуктовых товаров с их ценами в хэш-картах. Название предмета служит ключом, а его цена - его стоимостью. Эта пара "ключ-значение" сохраняется в хэш-карте, как показано ниже:
Порядок хранения значения ключа не гарантируется в неупорядоченной хэш-карте (также называемой неупорядоченной картой). Когда мы вставляем элемент в неупорядоченную хеш-карту, он может располагаться в любой позиции в объекте Map. Если мы хотим строго упорядочить элементы в порядке возрастания их ключей, мы можем использовать упорядоченную хеш-карту или просто карты. В том же примере, что и выше, элементы хранятся в Картах следующим образом:
Ключи отсортированы в лексикографическом порядке, начиная с наименьшей буквы, c. Когда необходимо добавить в Карты новый элемент, например Juice по цене 12 , он вставляется в позицию 3 после Шоколад для сохранения лексикографического порядка .
Кодирование хэш-карт
Неупорядоченные карты и карты являются частью стандартных библиотек шаблонов (STL) в C ++. Чтобы объявить карты и неупорядоченные карты , выполните следующее:
map<key_type, value_type>mp; unordered_map<key_type, value_type>unmp;
key_type и value_type могут иметь стандартные типы данных, такие как int, float, char, pair и т. Д.
Большинство функций-членов являются общими для unordered_map и map object. Итак, давайте посмотрим на некоторые из этих функций.
1. Вставка элемента в хеш-карту
Чтобы вставить элемент в unordered_map или map, запустите следующее:
mp.insert(pair<key_name, value>);
key_name и value - это имя и значение элемента, которые нужно вставить в map соответственно. В приведенном выше примере у нас есть Carrots как key_name и $2 как value . Мы также можем вставить элемент с помощью оператора присваивания:
mp["Carrots"] = 2;
2. Удалить элемент из хеш-карты.
Чтобы удалить элемент из хеш-карты, мы используем функцию erase :
mp.erase(mp.begin()); //Delete an item at start
mp.erase("Carrots"); //Delete an item with key "Carrots"
mp.erase(mp.begin(), mp.end()); //Delete all items in the map
3. Найдите элемент на хэш-карте.
Чтобы найти элемент на хэш-карте, мы используем функцию find :
const_iterator itr = mp.find("Carrots");
Если Carrots найден на карте, тогда itr содержит итератор для элемента в хэш-карте. Если указанный ключ не найден, itr содержит значение unordered_map::end.
4. Другие функции хэш-карты
Вот некоторые из других распространенных функций, используемых в хэш-картах:
value = mp.at("Carrots"); //Returns the value at key
cnt = mp.count("Carrots"); //Returns the total number of carrot
is_empty = mp.empty(); //Returns if the Hash Map is Empty
total_size = mp.size(); //Returns the total number of items
Приложения хэш-карт
Одним из самых больших преимуществ использования хэш-карт является то, что они обеспечивают постоянное время O (1) для операций поиска, вставки и удаления. Это делает их более подходящими для задач, связанных с поиском дубликатов, определением частоты элементов и поиском отдельных элементов.
1. Проблемы, связанные с периодичностью отправки товаров
Карты хеширования полезны для решения большинства проблем, связанных с частотой элементов. Примером такой проблемы является поиск общих символов в списке строк. Если элемент встречается дважды во всех строках, его необходимо дважды включить в вывод:
Input: ["bella","label","roller"] Output: ["e","l","l"]
Чтобы решить эту проблему, мы можем использовать два цикла for для сравнения одной строки со списком других строк. Но временная сложность такого подхода составляет O (n²). Чтобы минимизировать временную сложность, мы можем использовать хэш-карту для хранения символов в виде ключей с номером строки и частотой в виде пары для значения. Затем мы можем выполнить итерацию хеш-карты, чтобы проверить общие символы, обнаруженные во всех строках, а также их частоту. Это снижает временную сложность до O (n).
2. Словарь
Словарь - еще один распространенный пример, в котором хеш-карты используются чаще. Если бы нам нужно было создать онлайн-портал для поиска значения слова, мы бы создали словарь в задней части , чтобы хранить слово вместе с его значением. Когда пользователь ищет слово, он использует хэш-функцию find для получения его значения.
3. Файловые системы
Карты хеширования используются для связывания имени файла с путем к файлу. Чтобы сохранить соответствие между именем файла и путем и физическим расположением этого файла на диске, система использует карту. Эта карта обычно реализуется в виде хеш-таблицы.
4. Подтверждение пароля
Рассмотрим веб-приложение, которое позволяет пользователю вход в систему и аутентификацию, когда пользователь вводит свое имя пользователя и пароль . В большинстве современных систем имя пользователя и пароль не отправляются в виде обычного текста на внутренний сервер для аутентификации. Вместо этого они кодируются как хеш-значение и отправляются на сервер. Затем сервер проверяет полученное значение хеш-функции с сохраненным значением хеш-функции. Если есть совпадение, пользователю разрешается войти в систему. Для этой цели используются специальные криптографические функции, поэтому пользователь в безопасности.
5. Оптимизация хранилища в облаке
Dropbox использует хеш-таблицы для оптимизации хранения в облаке. Предположим, несколько пользователей загружают одно и то же видео в свои учетные записи Dropbox . Поскольку для хранения нескольких копий одного и того же видео потребуется слишком много места, Dropbox хранит одну копию файла со ссылкой, предоставляемой каждому пользователю для доступа. Когда новый пользователь загружает тот же файл, Dropbox вычисляет хеш-значение для файла. Если оно соответствует значению, хранящемуся в хеш-таблице, пользователю возвращается ссылка на файл.
6. Работа компилятора
Чтобы идентифицировать ключевые слова на языке программирования, компилятор сохраняет их в хэш-таблице. Затем компилятор проверяет программу с помощью хэш-таблицы, чтобы убедиться, что синтаксис программы правильный.
Заключение
Это всего лишь несколько приложений, использующих хэш-карты. Карты хеширования служат одним из важнейших инструментов, которые необходимо знать каждому разработчику. Это ускоряет и упрощает решение проблем, особенно проблем, связанных с частотой появления элементов.
