Недавно я работал над курсом Coursera Data Structures. На этой неделе моей задачей было узнать о хешировании.
Хеширование широко используется в программировании. Некоторые примеры:
- Языки программирования — необходимо хранить специальные слова, такие как
for, if, while, int, String, etc - Файловые системы — отображаются через хеш-таблицу
- Пароли — шифрование и проверка
- Оптимизация хранилища для поставщиков облачных хранилищ, таких как Dropbox/Google Drive и т. д.
Хорошим примером хеширования является веб-служба, которая отслеживает IP-адреса людей, посетивших их сайт. Это обычное дело для метрик. Гипотетически нам нужна таблица, которая отслеживает IP-адрес и время посещения сайта, со счетчиком, который увеличивается при посещении сайта с того же IP-адреса. В этой ситуации мы отслеживаем только один час за раз, поэтому счетчик должен уменьшиться на количество сайтов, посетивших ровно час назад.
Потенциальным способом сделать это была прямая адресация, при которой каждый возможный IP-адрес кодируется, а затем создается массив размером с этот список IP-адресов. Мы могли бы сохранять запись в массиве каждый раз при доступе к сайту. Огромным недостатком является огромный объем памяти, необходимый для создания такого массива; расточительно резервировать память для IP-адресов, которые потенциально никогда не получат доступ к сайту.
Следующий вариант, сопоставление на основе списка, предполагает сохранение IP-адресов в связанном списке и добавление записи только при доступе к сайту. Преимущество этого заключается в том, что он использует память только для активных записей и легко удаляет IP-адреса, когда мы перестаем их отслеживать. Проблема в том, что когда вы хотите проверить, сколько раз IP-адрес заходил на сайт, вам нужно будет просмотреть весь список, чтобы подсчитать дубликаты для каждого IP-адреса.
Лучшим решением для нашего веб-сервиса может быть цепочка. Для этого мы создадим двумерный массив (массив массивов). Когда IP-адрес обращается к сайту, адрес может быть преобразован в короткое число, чтобы соответствовать индексу первого измерения массива. Затем мы могли бы проверить каждый элемент во втором измерении массива, чтобы увидеть, указан ли IP-адрес. Если его нет в массиве, мы можем добавить его, если есть, мы можем увеличить счетчик.
Набор — это структура данных с тремя методами — добавить, удалить или найти. Хеш-таблица — это любая реализация набора или карты, использующая хеширование. В Java набор уже реализован как HashSet.
Мой следующий пост будет посвящен Хеш-функциям.
