Ищите хороший 64-битный хеш для путей к файлам в UTF16 - PullRequest
Новая
       35

Ищите хороший 64-битный хеш для путей к файлам в UTF16

7 голосов
/ 16 сентября 2010

У меня есть Unicode / UTF-16 кодированный путь .ограничителями пути является U + 005C '\'.Пути - это корневые относительные пути файловой системы Windows, оканчивающиеся нулем, например, "\ windows \ system32 \ drivers \ myDriver32.sys"

Я хочу хэшировать этот путь в 64-битный без знака целое число. не нужно , чтобы быть "криптографически обоснованным" .Хэши должны быть без учета регистра , но способны обрабатывать не-ascii буквы.Очевидно, хеш также должен хорошо разбрасываться.

Есть некоторые идеи, которые у меня были:

A) Использование идентификатора файла Windows в качестве "хэша".В моем случае я хочу, чтобы хеш изменился, если файл был перемещен, так что это не вариант.

B) Просто используйте обычный строковый хеш: hash + = prime * hash + codepoint для всей строки.

У меня такое ощущение, что путь состоит из "сегментов"(имена папок и окончательное имя файла) могут быть использованы.

Подводя итог:

1) 64-битный хеш
2) хорошее распределение / несколько коллизий для путей файловой системы.
3) эффективное
4) недолжен быть безопасным
5) регистронезависимым

Ответы [ 4 ]

2 голосов
/ 16 сентября 2010

Даже если вам не нужен криптографический хеш, вы все равно можете использовать его, и, поскольку ваша проблема не в безопасности, тогда "сломанный" криптографический хеш будет в порядке.Я предлагаю MD4 , что довольно быстро.На моем ПК (система Core2 с частотой 2,4 ГГц, использующая одно ядро) MD4 хэширует более 700 МБ / с, и даже для небольших входов (менее 50 байтов) он может обрабатывать около 8 миллионов сообщений в секунду.Вы можете найти более быстрые некриптографические хеши, но для того, чтобы измерить разницу, уже требуется довольно специфическая ситуация.

Для определенных свойств, которые вам нужны, вам потребуется:

  1. Чтобы "нормализовать" символы, чтобы заглавные буквы были преобразованы в строчные (для нечувствительности к регистру).Обратите внимание, что, вообще говоря, нечувствительность к регистру в мире Unicode не является легкой задачей.Из того, что вы объясняете, я понимаю, что вы только после того же типа нечувствительности к регистру, который Windows использует для доступа к файлам (я думаю , что это только ASCII, так что преобразование в верхний регистр-> строчный просто.

  2. Для усечения вывода MD4.MD4 выдает 128 бит;просто используйте первые 64 бита.Это будет настолько рассеянно, насколько вы пожелаете.

В некоторых местах доступны реализации MD4, в том числе прямо в RFC 1320, ссылка на которую приведена выше.Вы также можете найти реализации MD4 с открытым исходным кодом в C и Java в sphlib .

2 голосов
/ 22 сентября 2010

Я бы просто использовал что-то прямое. Я не знаю, какой язык вы используете, поэтому следующий псевдокод: 

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 недопустимы в именах путей) не будет слишком дорогим, но и не улучшит хеширование слишком сильно.

2 голосов
/ 16 сентября 2010

Криптографически безопасные хэши могут быть не очень эффективными с точки зрения скорости, но есть реализации, доступные практически для любого языка программирования.
Возможность их использования для вашего приложения зависит от того, насколько вы зависите от скорости & ndash; тест даст вам соответствующий ответ.

Вы можете использовать подстроку такого хэша, например, MD5 на вашем пути, ранее преобразованный в нижний регистр, так что хеш эффективно не чувствителен к регистру (требует, чтобы вы использовали метод для нижнего регистра, который знает, как преобразовать все нестандартные символы UTF-16, которые могут встречаться в файловой системе ).

Криптографически безопасные хэши имеют преимущество равномерного распределения независимо от того, какую часть подстроки вы берете, потому что они разработаны так, чтобы быть непредсказуемыми, т.е. каждая часть хеша в идеале зависит от целых хешированных данных, как и любая другая часть это.

1 голос
/ 01 ноября 2016

Вы можете просто создать общую библиотеку в 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 на основе некоторых других характеристик файла.

...