EDIT
Вот проблема, которую я пытаюсь решить:
У меня есть строка, разбитая на несколько частей. Эти части не имеют равной или предсказуемой длины. Каждая часть будет иметь хеш-значение. Когда я объединяю части, я хочу иметь возможность использовать значения хеш-функции для каждой части, чтобы быстро получить значение хеш-функции для частей вместе. Кроме того, хеш, сгенерированный путем объединения частей, должен соответствовать хешу, сгенерированному, если строка была хеширована как целое.
По сути, мне нужен алгоритм хеширования, в котором части хешируемых данных можно хэшировать параллельно, и я не хочу, чтобы порядок или длина кусков имели значение. Я не разрываю строку, а скорее получаю ее непредсказуемыми порциями в непредсказуемом порядке.
Я готов обеспечить повышенную частоту столкновений, если она не слишком повышена. Я также согласен с немного более медленным алгоритмом, так как он едва заметен на маленьких строках, а параллельно с большими строками.
<ч />
Я знаком с несколькими алгоритмами хеширования, однако в настоящее время у меня есть сценарий использования алгоритма хеширования со свойством, что сумма двух хешей равна хеш-сумме двух элементов.
Требования / данности
- Этот алгоритм будет хэшировать байтовые строки длиной не менее 1 байта
- hash ("ab") = hash ('a') + hash ('b')
- Столкновения между строками с одинаковыми символами в разном порядке вполне допустимы
- Сгенерированный хеш должен быть целым числом собственного размера (обычно 32/64 бита)
- Строка может содержать любой символ от 0 до 256 (длина известна, без \ 0 завершена)
- Буквенно-цифровые символы ascii будут наиболее используемыми
- Непропорциональное количество строк будет 1-8 символов ASCII
- Очень маленький процент строк на самом деле будет содержать байты со значениями, равными или превышающими 127
Если это тип алгоритма, с которым связана терминология, я хотел бы знать эту терминологию. Если бы я знал, что такое правильный термин / имя для этого типа алгоритма хэширования, было бы намного проще в Google.
Я думаю, что самый простой способ достичь этого:
- Хеш любого байта должен быть его значением, нормализованным до <128 (если> 128 вычесть 128)
- Чтобы получить хеш строки, вы нормализуете каждый байт до <128 и добавляете его к ключу </li>
- В зависимости от размера ключа мне может понадобиться ограничить количество символов, используемых для хеширования, чтобы избежать переполнения