Когда дело доходит до хеширования, оно обычно соответствует хеш-таблице (хеш-таблице) и хеш-функции. Сегодня мы не будем говорить о хеш-таблицах, а только о хеш-функциях.
определение
Цитирование абзаца определения хеш-функции в энциклопедии Baidu.
Хэш, обычно переводимый как «хеш», также напрямую транслитерируется как «хэш», то есть ввод любой длины преобразуется в вывод фиксированной длины с помощью алгоритма хеширования, а вывод представляет собой хеш-значение.
Это преобразование является картой сжатия, то есть пространство хеш-значения обычно намного меньше, чем пространство ввода, и разные входы могут хэшироваться в один и тот же вывод, поэтому невозможно определить уникальное входное значение из хеша. ценность.
Проще говоря, это функция, которая сжимает сообщение любой длины в дайджест сообщения фиксированной длины.
Существует много выражений об определении хэш-функции, которые похожи друг на друга, и этого достаточно, чтобы понять ее понятие и коннотацию.
природа
ПроверятьВикипедияиЭнциклопедия Байду, оба упоминают несколько моментов о природе хеширования:
1. Уверенность
Если два хеш-значения не совпадают, то исходные входные данные двух хеш-значений также различны;
2. Конфликт (столкновение)
Вход и выход хеш-функции не уникальны.Если два хеш-значения одинаковы, два входных значения, скорее всего, будут одинаковыми, но они также могут быть разными;
3. Необратимость
Последнее касается того, является ли оно обратимым, и эти два выражения различны:
В Википедии четко сказано, что «хэш-функция должна быть необратимой», а утверждение Baidu Baike двусмысленно, а последнее, напротив, слишком неточное. Автор больше склоняется к упомянутой в Википедии необратимости.
4. Путаница
В разделе «Свойства хеш-функций» Википедия также упоминает, что:
Введите некоторые данные для вычисления хеш-значения, а затем частично измените входное значение, хэш-функция с сильными свойствами обфускации даст совершенно другое хэш-значение.
В этом выражении два слова: "Сильное запутывание", "полностью отличается". Что это означает?
Давайте сначала разберемся с концепцией:Лавинный эффект
Суть его в том, что "Строгие правила схода лавин": Когда любой из входных битов инвертируется, каждый бит на выходе имеет 50% шанс измениться.
Изучите еще одно понятие:Hamming distance.
Некоторые переводятся как «расстояние Хэмминга», а другие - как «расстояние Хэмминга». Имя не важно, важна коннотация.
Количество битов, в котором соответствующие биты двух кодовых слов имеют разные значения, называется расстоянием Хэмминга двух кодовых слов. Пример следующий: 10101 и 00110 имеют первую, четвертую и пятую позиции, отличные от первой, тогда расстояние Хэмминга равно 3.
В соответствии с хэшем, если «частично изменяет входное значение», расстояние Хэмминга двух хэшей до и после составляет половину длины хэша (то есть половина битов различны), то это «50% вероятность изменения .". Такая хеш-функция является «хэш-функцией с сильными свойствами запутывания».
Пример хэш-функции
Общие хэш-функцииMD5иСемья ШАи другие криптографические хэш-функции,CRCЭто также следует рассматривать как хэш.
Оба используются для проверки данных, а первый также используется для цифровых подписей, аутентификации доступа и других полей безопасности.
Однако сегодня мы не будем много говорить о криптографических хэшах, а в основном поговорим о следующих двух хешах:
BKDRHash
Вы должны были видеть эту хэш-функцию, и некоторые читатели могут не знать ее названия. hashCode() для String в JDK реализован с помощью этой хеш-функции:
public int hashCode() {
int h = hash;
final int len = length();
if (h == 0 && len > 0) {
for (int i = 0; i < len; i++) {
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
Определите класс, и если вы позволите IDE автоматически сгенерировать функцию hashCode(), ее реализация будет аналогичной:
public static class Foo{
int a;
double b;
String c;
@Override
public int hashCode() {
int result;
long temp;
result = a;
temp = Double.doubleToLongBits(b);
result = 31 * result + (int) (temp ^ (temp >>> 32));
result = 31 * result + (c != null ? c.hashCode() : 0);
return result;
}
}
Почему у тебя всегда проблемы с "31"? Зачем итеративно умножать и суммировать вот так?
В этой статье рассматриваются некоторые из этих принципов:Анализ и расширение алгоритма bkdrhash хеш-таблицы
И на Чжиху есть много великих богов, которые сделали анализ:Каков математический принцип алгоритма хеширования и как обеспечить как можно меньше коллизий
Из сравнения баллов, приведенного во второй ссылке, видно, что, хотя BKDRHash прост в реализации, он очень эффективен (низкая частота конфликтов).
Низкая коллизия, так что BKDRHash используется не только для хеш-таблиц, но и для индексации объектов.
Чаще всего используется MD5.Некоторые веб-сайты могут использовать MD5 файла в качестве ключа для извлечения файла.
рисунокDiskLruCacheВ качестве ключа также используется MD5, но обычно MD5 вычисляется не для самого файла, а MD5 для URL-адреса (например, OkHttp, Glide).
Дайджест сообщения, сгенерированный MD5, имеет биты 128. Если идентифицируемых объектов немного, частота конфликтов будет очень низкой;
Когда частота коллизий намного ниже вероятности повреждения оборудования, можно считать надежным использование MD5 в качестве ключа.
Для веб-сайтов, если вы хотите хранить массивные файлы, не рекомендуется использовать MD5 в качестве ключа.
Кстати, UUID на самом деле имеет 128-битную точность, но добавляет еще несколько разделительных линий для удобства чтения.
Это слишком далеко, вернемся к теме~
Причина, по которой я вижу, что BKDRHash используется для индексации объектов, в основном состоит в том, чтобы увидеть эту статью (я не изучал исходный код Volley):
Анализ исходного кода Android Volley (2), изучение механизма кэширования
В нем упоминается дизайн кэшированных ключей Volley:
private String getFilenameForKey(String key) {
int firstHalfLength = key.length() / 2;
String localFilename = String.valueOf(key.substring(0, firstHalfLength).hashCode());
localFilename += String.valueOf(key.substring(firstHalfLength).hashCode());
return localFilename;
}
Поскольку возвращаемое значение JDK hashCode() имеет тип int, можно сказать, что эта функция имеет 64-битную точность.
Нельзя сказать, что это хэш-функция, потому что длина возвращаемого значения не фиксирована, хэш-функцией ее назвать нельзя по определению, хотя идея очень близка.
Его эквивалент записывается следующим образом:
public static String getFilenameForKey(String key) {
byte[] bytes = key.getBytes();
int h1 = 0, h2 = 0;
int len = bytes.length;
int firstHalfLength = len / 2;
for (int i = 0; i < firstHalfLength; i++) {
byte ch = bytes[i];
h1 = 31 * h1 + ch;
}
for (int i = firstHalfLength; i < len; i++) {
byte ch = bytes[i];
h2 = 31 * h2 + ch;
}
long hash = (((long) h1 << 32) & 0xFFFFFFFF00000000L) | ((long) h2 & 0xFFFFFFFFL);
return Long.toHexString(hash);
}
Эффект примерно эквивалентен 64-битной точности BKDRHash. 64-битный BKDRHash выглядит следующим образом:
public static long BKDRHash(byte[] bytes) {
long seed = 1313; // 31 131 1313 13131 131313 etc..
long hash = 0;
int len = bytes.length;
for (int i = 0; i < len; i++) {
hash = (hash * seed) + bytes[i];
}
return hash;
}
Автор составил программу для сравнения степени конфликтности двух, и первая выше, чем вторая (ограниченное пространство, тестовый код не публикуется, и заинтересованные читатели могут проверить его самостоятельно).
32-битный хэш, независимо от того, какой из них, пока набор данных (случайные данные) равен 10 ^ 6, в основном каждый запуск будет иметь коллизию. 64-битный хеш, пока производительность не так уж плоха, если длина данных относительно велика (например, 20-байтовый случайный массив), трудно конфликтовать даже с набором данных в десятки миллионов (у меня есть не перепробовал сотни миллионов да машина не выдержит).
Автор также был поклонником BKDRHash и какое-то время использовал его в проекте (в качестве ключа кэша). Я знаю, что видел ответ на обсуждение в вышеупомянутой Жиху:
Прочитав Zhihu, я был удивлен, и я вернулся и модифицировал тестовый пример.При построении случайных данных я использовал данные неопределенной длины, например, 1-30 случайных байт.
Протестировано на написанном выше 64bitBKDRHash, результат такой:
Конфликты можно увидеть на наборе данных из 50 000.
Я и раньше знал, что путаница BKDRHash недостаточна (например, значение последнего байта увеличивается на 1, а значение хеша увеличивается только на 1, если оно не переполняется);
Однако из-за его простой реализации и необоснованных результатов тестирования выше, он используется в качестве ключа кэша, ведь Volley сделал то же самое.
На самом деле большой проблемы нет, т.к. ввод обычно длинный, а файлов для кеширования не много (сотни-тысячи уровней), так что конфликтов быть не должно.
Но сердце мое все еще не в покое (см.:закон Мерфи) и быстро переключился на другую хеш-функцию.
MurmurHash
Когда я впервые увидел эту хэш-функцию, меня тоже поразило ее название.
Однако есть и люди, которые считают это имя очень «милым»:
Однако есть поговорка, что «люди не могут смотреть на свою внешность», и нельзя судить об алгоритме по имени, но он зависит от его эффекта.
Как показано на скриншоте, многие известные компоненты с открытым исходным кодом используют этот хеш, так где же он священный? Давайте разберемся.
Сначала посмотрите исходный код:сайты.Google.com/site/murmur…
Исходный код написан на C++:
uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed )
{
const uint64_t m = 0xc6a4a7935bd1e995;
const int r = 47;
uint64_t h = seed ^ (len * m);
const uint64_t * data = (const uint64_t *)key;
const uint64_t * end = data + (len/8);
while(data != end)
{
uint64_t k = *data++;
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
const unsigned char * data2 = (const unsigned char*)data;
switch(len & 7)
{
case 7: h ^= uint64_t(data2[6]) << 48;
case 6: h ^= uint64_t(data2[5]) << 40;
case 5: h ^= uint64_t(data2[4]) << 32;
case 4: h ^= uint64_t(data2[3]) << 24;
case 3: h ^= uint64_t(data2[2]) << 16;
case 2: h ^= uint64_t(data2[1]) << 8;
case 1: h ^= uint64_t(data2[0]);
h *= m;
};
h ^= h >> r;
h *= m;
h ^= h >> r;
return h;
}
В целом не очень сложно, по сравнению с BKDHHash это все цикл.
Кроме того, C++ может указывать указатель int64 на массив char, который может вычислять 8 байт за раз, а для массивов большей длины операция выполняется быстрее.
Для java это относительно проблематично:
public static long hash64(final byte[] data) {
if (data == null || data.length == 0) {
return 0L;
}
final int len = data.length;
final long m = 0xc6a4a7935bd1e995L;
final long seed = 0xe17a1465;
final int r = 47;
long h = seed ^ (len * m);
int remain = len & 7;
int size = len - remain;
for (int i = 0; i < size; i += 8) {
long k = ((long) data[i] << 56) +
((long) (data[i + 1] & 0xFF) << 48) +
((long) (data[i + 2] & 0xFF) << 40) +
((long) (data[i + 3] & 0xFF) << 32) +
((long) (data[i + 4] & 0xFF) << 24) +
((data[i + 5] & 0xFF) << 16) +
((data[i + 6] & 0xFF) << 8) +
((data[i + 7] & 0xFF));
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
switch (remain) {
case 7: h ^= (long)(data[size + 6] & 0xFF) << 48;
case 6: h ^= (long)(data[size + 5] & 0xFF) << 40;
case 5: h ^= (long)(data[size + 4] & 0xFF) << 32;
case 4: h ^= (long)(data[size + 3] & 0xFF) << 24;
case 3: h ^= (data[size + 2] & 0xFF) << 16;
case 2: h ^= (data[size + 1] & 0xFF) << 8;
case 1: h ^= (data[size] & 0xFF);
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
return h;
}
Приведенная выше ссылка на реализацию:
GitHub.com/tanema/murmur и…
GitHub.com/themthem180/м…
Сделайте тест, случайный массив, число 10 ^ 7, длина 1-30, результаты следующие:
| хэш-функция | количество конфликтов | Время работы (мс) |
|---|---|---|
| BKDRHash | 1673 | 1121 |
| CRC64 | 1673 | 1331 |
| MurmurHash | 0 | 1119 |
Этот тест включает в себя еще один 64-битный хеш, CRC64.
Удивительно, что частота коллизий CRC64 и BKDRHash одинакова (проверено много раз, она одинакова), что может быть причиной проблемы переполнения.
Что касается времени расчета, то особой разницы нет.
Если длина случайного массива настроена на 1-50, частота коллизий первого (BKDRHash & CRC64) будет относительно снижена, а эффективность работы последнего будет немного лучше, чем у первого.
Я думаю, что MurmurHash широко используется не только из-за его низкой конфликтности, но и из-за очень важной особенности:
Упомянутая ранее «сильная путаница».
Напишите функцию для вычисления кодового расстояния следующим образом:
private static int getHammingDistance(long a, long b) {
int count = 0;
long mask = 1L;
while (mask != 0) {
if ((a & mask) != (b & mask)) {
count += 1;
}
mask <<= 1;
}
return count;
}
Создайте случайный массив, изменяйте по одному биту за раз, вычисляйте MurmurHash, и кодовое расстояние находится между 31-32.
Для 64-битного хэша это ровно около 50%, что указывает на лавинный эффект хэш-функции.
Или, с другой точки зрения, значение хеш-функции, рассчитанное MurmurHash, является относительно «однородным», что очень важно.
Например, при использовании в хеш-таблицеФильтр БлумаЖдать,
Элементы распределены равномерно.
Последняя вещь:атака на день рождения
Для хеш-функций с лавинным эффектом распределение коллизий выглядит следующим образом:
Возвращаясь к упомянутому ранее ключу кеша, 64-битному MurmurHash, когда количество кешей находится на уровне 10^4,
Вероятность столкновения двух кэшированных ключей составляет порядка 10^-12 (одна часть на триллион), что должно быть относительно надежным.
Если вы считаете, что этого недостаточно, вы можете использовать 128-битный MurmurHash, который должен быть более подходящим, чем MD5, только для индексации (быстрая работа, низкий уровень коллизий, высокий уровень путаницы).
Эпилог
Хеширование широко используется в различных областях компьютерной техники, и понимание некоторых свойств хеш-функций может быть полезно для решения инженерных задач.
Поэтому этим «разговором» я надеюсь вдохновить читателей.
Если есть какое-либо неправильное понимание, пожалуйста, поправьте меня.