Ищите хороший 64-битный хеш для путей к файлам в UTF16
У меня есть кодированный путь Unicode / UTF-16. ограничителями пути является U+005C '\'. Пути - это корневые относительные пути файловой системы Windows, оканчивающиеся нулем, например "\windows\system32\drivers\myDriver32.sys"
Я хочу хэшировать этот путь в 64-разрядное целое число без знака. Это не должно быть "криптографически обоснованным". Хэши должны быть нечувствительными к регистру, но должны обрабатывать не-ascii буквы. Очевидно, что хеш также должен хорошо разбрасываться.
Есть некоторые идеи, которые у меня были, хотя:
A) Использование идентификатора файла Windows в качестве "хеша". В моем случае я хочу, чтобы хеш изменился, если файл был перемещен, так что это не вариант.
Б) Просто используйте обычный строковый хеш: хэш += простой * хэш + кодовая точка для всей строки.
У меня есть ощущение, что можно использовать тот факт, что путь состоит из "сегментов" (имен папок и конечного имени файла).
Подводя итог потребностей:
1) 64-битный хеш
2) хорошее распределение / несколько коллизий для путей файловой системы.
3) эффективный
4) не должен быть в безопасности
5) без учета регистра
4 ответа
Криптографически безопасные хэши могут быть не очень эффективными с точки зрения скорости, но есть реализации, доступные практически для любого языка программирования.
Возможность их использования для вашего приложения зависит от того, насколько вы зависите от скорости - эталонный тест даст вам соответствующий ответ.
Вы можете использовать подстроку такого хэша, например, MD5 на вашем пути, предварительно преобразованную в нижний регистр, так что хэш эффективно не чувствителен к регистру (требует, чтобы вы использовали метод для нижнего регистра, который знает, как преобразовать все UTF-16 нестандартных символов, которые могут встречаться в файловой системе).
Криптографически безопасные хэши имеют преимущество равномерного распределения независимо от того, какую часть подстроки вы берете, потому что они разработаны так, чтобы быть непредсказуемыми, т.е. каждая часть хеша в идеале зависит от всей хэшированной информации, как и любая другая ее часть.
Я бы просто использовал что-то прямое. Я не знаю, какой язык вы используете, поэтому следующий псевдокод:
ui64 res = 10000019;
for(i = 0; i < len; i += 2)
{
ui64 merge = ucase(path[i]) * 65536 + ucase(path[i + 1]);
res = res * 8191 + merge; // unchecked arithmetic
}
return res;
Я предполагаю что path[i + 1]
безопасно на том основании, что если len
нечетно, тогда в последнем случае он будет безопасно читать U+0000.
Я бы не использовал тот факт, что в UTF-16 есть пробелы, вызванные пробелами, строчными и заглавными буквами и недопустимыми для путей символами, потому что они не распределены таким образом, чтобы их можно было использовать. из этого факта, что может быть использовано быстро. Удаление на 32 (все символы ниже U+0032 недопустимы в именах путей) не будет слишком дорогим, но это также не улучшит хеширование слишком сильно.
Даже если вам не нужен криптографический хэш, вы все равно можете его использовать, и, поскольку ваша проблема не в безопасности, тогда "сломанный" криптографический хеш будет в порядке. Я предлагаю MD4, который довольно быстрый. На моем ПК (система Core2 с частотой 2,4 ГГц, использующая одно ядро) MD4 хэширует более 700 МБ / с, и даже для небольших входов (менее 50 байт) он может обрабатывать около 8 миллионов сообщений в секунду. Вы можете найти более быстрые некриптографические хеши, но для того, чтобы это измеримо изменилось, уже требуется довольно специфическая ситуация.
Для конкретных свойств, которые вы ищете, вам понадобится:
"Нормализовать" символы, чтобы заглавные буквы были преобразованы в строчные (без учета регистра). Обратите внимание, что, вообще говоря, нечувствительность к регистру в мире Unicode - задача не из легких. Из того, что вы объясняете, я понял, что вы используете только тот же тип нечувствительности к регистру, который Windows использует для доступа к файлам (я думаю, что это только для ASCII, поэтому преобразование в верхний регистр -> нижний регистр просто).
Усечь вывод MD4. MD4 выдает 128 бит; просто используйте первые 64 бита. Это будет настолько рассеянно, насколько вы могли бы пожелать.
В некоторых местах доступны реализации MD4, в том числе прямо в RFC 1320, ссылка на которую приведена выше. Вы также можете найти реализации MD4 с открытым исходным кодом в C и Java в sphlib.
Вы можете просто создать общую библиотеку в C# и использовать класс FileInfo, чтобы получить полный путь к каталогу или файлу. Затем используйте.GetHashCode() в пути, например:
Hash = fullPath.GetHashCode();
или же
int getHashCode(string uri)
{
if (uri == null) throw new ArgumentNullException(nameof(uri));
FileInfo fileInfo = new FileInfo(uri);
return fileInfo.FullName.GetHashCode();
}
Хотя это всего лишь 32-битный код, вы дублируете его или добавляете другой HashCode, основываясь на некоторых других характеристиках файла.