hash( «abcd» ) = hash(«abc») + hash(«d»)

я не силен в данном вопросе, но разве такое возможно по определению хеш-функций

Первое что приходит в голову - сложение всех символов строки, но с коллизиями тут не очень.

unsigned int my_strange_hash(char * str) {
        unsigned int result = 0;
        while (*str) {
                hash += *str;
                str++;
        }
        return result;
}

Разумеется, переполнение result должно игнорироваться.

Почему бы нет?

Только беда в том что

 hash('ab') + hash('cd') == hash('abc') + hash('d')

Мой хеш подойдёт, правда, возможно он единственный, который подойдёт, а у него не очень с коллизиями (hash('abcd') == hash('dcba'))

Согласен.

Есть смысл ввести некую полиномиальную зависимость hash( «abcd» ) = P(hash(«abc»)) + Q(hash(«d»))

Вот сложение и возьми в качестве хеша. Если в первом требовании некритично именно сложение, то можно взять любую групповую операцию, например, xor. С коллизиями в среднестатистическом случае будет фигово.

есть некоторое подозрение, что алгоритм может быть «улучшен», примерно так:

unsigned int my_strange_hash(char * str) {
        const unsigned long hashcode[256] = {скажем набор простых чисел с 6-10-ю знаками};
        unsigned long result = 0;
        while (*str) {
                hash += hashcode[*str];
                str++;
        }
        return result;
}

Хотя.. с теми условиями так и получается.

hash('abcd') == hash('a') + hash('b') + hash('c') + hash('d')

А поскольку результат Hash это число, то действует коммутативный закон.

А для чего, если не секрет?

Мне главное чтобы при добавлении символа к строке новый хеш считался за O(1) с приемлемой коллизией (1е-5 вполне). Аддитивность (да и полином тоже) этому требованию удовлетворяет. Вот, мож кто родит более другую идею нежели просто через к.-л. суммирование.

Ситуацию с коллизиями можно улучшить, если взять некоммутативную операцию в качестве «+». f(ab) != f (ba);

Не секрет. Для анализа строк.

А старые добрые N-грамы не котируются уже?

Мне главное чтобы при добавлении символа к строке новый хеш считался за O(1) с приемлемой коллизией (1е-5 вполне). Аддитивность (да и полином тоже) этому требованию удовлетворяет.

Большинство хешей так и работают. Аддитивность тут излишня, нужно... как бы это назвать... итеративность: hash(data + byte) = f(hash(data), byte). CRC, MD5 и SHA точно сойдут.

Угу, я так же подумал. Нечего велосипедить.

Вообще это они и есть.

Предельный размер-то не указал :). В таком случае хышем являются сами строки.

И зачем их хешировать?

В джаве для строк используют полиномиальный: hash(str + c) = hash(str) * 31 + (int) c; Вместо 31 можно поставить какое-нибудь другое простое число

Как это «зачем»?!

От длинных нет профита, короткие и так короче хеша который ты получишь. Могу ошибаться не профессионал и даже не любитель NLP :)

А, в этом смысле... Ну тут свой хеш главным образом для того, чтобы найти все n-граммы всех длин за O(1) проход.

PS короче, взял за основу ряд Фибоначчи.

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

Все-таки, коммутативность и аддитивность - вещи разные. Например, если A(+)B = AB, то очевидно , такое сложение некоммутативно, но в то же время при f(x)=x имеем f(ab)=f(a)+f(b). Случаи частные, но тем не менее.