Есть ли хеш-функция строки, которая поддерживает h (x) + h (y) = h (x + y)

Question

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

У меня есть два набора строковых значений, и значение предоставляется во время выполнения. Мне нужно получить список всех строк из второго набора, который начинается с строки из первого набора и заканчивается значением запроса. Здесь значительно упрощенное представление и описание:

set1: 
my_test_val_1 
my_test_val_2 

set2: 
my_test_val_1_extended_to_another_value 
my_test_val_2_extended_as_well 

Моя цель состоит в том, чтобы сохранить хеш-значения этих множеств, как в:

set1: 
hash(my_test_val_1) 
... 

set2: 
hash(my_test_val_1_extended_to_another_value) 

сэкономить на пространстве, и когда «_extended_to_another_value» прибывает как запрос, использовать хэш-функцию с распределительным свойством более того, чтобы сделать:

hash(my_test_val_1) + hash('_extended_to_another_value') = hash_value_to_search 

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

Answer 1

Вот один:

import java.util.Random; 
public class StringHasher { 
    private static int[] CHAR_HASHES = new int[65536]; 
    static { 
     Random rng = new Random(); 
     for(int k = 0; k < 65536; k++) 
      CHAR_HASHES[k] = rng.nextInt(); 
    } 
    public static int hash(String s) { 
     int result = 0; 
     for(int k = 0; k < s.length(); k++) { 
      result += CHAR_HASHES[s.charAt(k)]; 
     } 
     return result; 
    } 
} 

Оказывается, любой такой хеш должен быть создан путем сложения всех хэшей составляющих символов строки - иначе, например, h("hello") = h("h") + h("e") + h("l") + h("l") + h("o") не удерживался.

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

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

Answer 2

Вы можете использовать некоторые из основных алгоритмов хеширования и попытаться взломать его с помощью онлайн-баз данных. Если x и y являются достаточно короткими, вы можете найти их в базе данных MDH или SHA в режиме онлайн-трещин хэшей, и если вы ее дешифруете, вы можете продолжить свой алгоритм.

Если ваше приложение онлайн, он может использовать этот подход. Недостатком является то, что в некоторых случаях в углах вы можете получить неправильное значение, которое имеет тот же хэш-код, что и правильный, но вероятность этого довольно низкая.

Это, в основном, хак, но вы делаете такие вещи с вашим требованием, так что это может быть приемлемо для вас.

Вот пример онлайновых баз данных хеш:

• http://www.md5online.org/
• http://www.dehashme.com/