В этой статье мы окунемся в увлекательный мир методов ручного хеширования строк, используя только ручку и бумагу. Хотя современные языки программирования предоставляют встроенные функции для расчета хэш-кодов, понимание основных принципов может быть полезным. Мы шаг за шагом рассмотрим несколько методов с примерами кода.
Метод 1: простое сложение
Один из самых простых способов вычислить хеш-код вручную — суммировать значения ASCII каждого символа в строке. В качестве примера возьмем строку «привет»:
-
Присвойте символам значения ASCII:
h: 104
e: 101
l: 108
l: 108
o: 111 -
Вычислите сумму:
HashCode = 104 + 101 + 108 + 108 + 111 = 532
Метод 2: полиномиальный скользящий хеш
В методе полиномиального скользящего хеширования используется полиномиальная функция для вычисления хеш-кода. Вот пошаговое руководство:
-
Назначьте простое число в качестве основы (например, 31) и инициализируйте хэш-значение равным 0.
-
Пройдитесь по каждому символу строки и примените следующую формулу:
хэш = (хэш * база + значение ASCII) % MOD
Давайте рассчитаем хеш-код для строки «world», используя base = 31 и MOD = 1000000007:
-
Инициализировать хэш = 0, базовое значение = 31, MOD = 1000000007.
-
Перебирать символы:
- Для «w»: хеш = (0 * 31 + 119) % 1000000007 = 119
- Для «o»: хэш = (119 * 31 + 111) % 1000000007 = 3910
- Для «r»: хэш = (3910 * 31 + 114) % 1000000007 = 122314
- Для «l»: хеш = (122314 * 31 + 108) % 1000000007 = 3805252
- Для d: хеш = (3805252 * 31 + 100) % 1000000007 = 118259408
Окончательный хеш-код слова «мир» — 118259408.
Метод 3: операция XOR
Хеширование на основе XOR — это еще один метод расчета хэш-кодов вручную. Вот пример:
-
Инициализировать хэш = 0.
-
Перебрать каждый символ в строке и применить операцию XOR:
хэш = хэш-значение XOR ASCII
Давайте посчитаем хэш-код для строки «pen» с помощью XOR:
-
Инициализировать хэш = 0.
-
Перебирать символы:
- Для «p»: хеш = 0 XOR 112 = 112
- Для «e»: хеш = 112 XOR 101 = 29
- Для n: хэш = 29 XOR 110 = 115
Окончательный хэш-код слова «ручка» — 115.
Вычисление хеш-кодов вручную с помощью ручки и бумаги обеспечивает более глубокое понимание основных принципов хэш-функций. Мы исследовали три метода: простое сложение, полиномиальный скользящий хэш и операцию XOR. Каждый метод имеет свои преимущества и варианты использования. Хорошо освоив эти методы, вы сможете получить представление о том, как работают хеш-функции и их практическое применение в различных сценариях программирования.
Помните, что хотя ручное хеширование строк информативно, важно использовать встроенные хэш-функции, предоставляемые языками программирования, для оптимальной производительности и надежности в реальных приложениях.