удивительная хеш функция

f(x)=kx

f(a)=ka
f(b)=kb
f(a+b)=k(a+b)=ka+kb=f(a)+f(b)

Возникли вопросы: 

1) Что такое А,B,+ ?
2) + слева от равеснства и справа от равенства это обязательно одна и таже операция ?
3) И нафиг тебе такое вообще нужно ? :) 

А так, палцем в небо, вот тебе решение с обычной быстрой хеш-функцией. 
Использовал в трансляторе одного языка программирования.

unsigned int hash(unigned int dwHash, const char * text)
{
	if (text == 0 )
	  return 0;

	while (*text)
		dwHash = (dwHash << 5) + dwHash + *text++;
	return dwHash;
}

Для нее выполняется равенство

hash(hash(0,A),B) = hash(0,concat(A,B))

A,B - строки, concat - конкатенация строк 

> 1) Что такое А,B,+ ? это строки > 2) + слева от равеснства и справа от равенства это обязательно одна и таже операция ? hash(A) + hash(B) - это сложение интов, т.к. hash(?) - это инт A+B - это конкатенация строк > 3) И нафиг тебе такое вообще нужно ? :) это мне надо для анимации. Тоесть у нас например есть несколько анимированых человечков мы берем подставляем "название человечка" + "бежать", а т.к. работа со строками это зло ( в плане скорости ), то мне надо сделать это интами. Конечно могут быть и повторения но это все будет на при экспорте проверяться. > А так, палцем в небо, вот тебе решение с обычной быстрой хеш-функцией. Использовал в трансляторе одного языка программирования. Ну это точно пальцем в небо, слишком много повторений будет, а это плохо.

> 1) Что такое А,B,+ ?

это строки

> 2) + слева от равеснства и справа от равенства это обязательно одна и таже операция ?

hash(A) + hash(B) - это сложение интов, т.к. hash(?) - это инт A+B - это конкатенация строк

> 3) И нафиг тебе такое вообще нужно ? :)

это мне надо для анимации. Тоесть у нас например есть несколько анимированых человечков мы берем подставляем "название человечка" + "бежать", а т.к. работа со строками это зло ( в плане скорости ), то мне надо сделать это интами. Конечно могут быть и повторения но это все будет на при экспорте проверяться.

> А так, палцем в небо, вот тебе решение с обычной быстрой хеш-функцией. Использовал в трансляторе одного языка программирования.

Ну это точно пальцем в небо, слишком много повторений будет, а это плохо.

//tkachilo

Хе-хе :) Ниче не понял :) 

Каких повторений ? Всмысле коллизий что-ли ? Да не очень много.
Точно не понмню, но в моей хеш-таблице на тестовых данных в 50 000
разных строк максимальная цепочка коллизий была что-то около 3-4 элементов. Для современной машины это копейки. 

А так:

hash(hash(0,"человечек"),"бежать") = hash(0,сoncat("человечек","бежать"))

но 

hash(hash(0,"бежать"),"человечек") <> hash(0,concat("человечек","бежать"))

в том виде в каком ты сформулировал, подходит ф-ция единственного вида: hash("abc") = f("a") + f("b") + f("c"), где функция f фиксированная произвольная.

Остаток от деления по модулю :-)

hash(a) = a % c (c - константа)

a % c + b % c = (a + b) % c

На самом деле операция hash(hash(0,A),B) просто расчитывает хеш для А, а потом "досчитывает" туда B. Так можно многие хеш-функции использовать. Возьми например функцию из Дракона.

> hash(A) + hash(B) - это сложение интов

Уверен насчет этого ? У тебя в таком случае

hash(concat("человечек","бежать")) = hash(concat("бежать","человечек")) = hash(concat("чежать","беловечек")) = ...

> мы берем подставляем "название человечка" + "бежать", а т.к. работа со строками это зло ( в плане скорости ), то мне надо сделать это интами.

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

> a % c + b % c = (a + b) % c

не верно. пример:

4 % 10 + 7 % 10 = 11

(4 + 7) % 10 = 1

нужно так: (a % c + b % c) % c

формула такая: (a % c + b % c) %c = (a + b) % c

> 4 % 10 + 7 % 10 = 11

Вам бы курс алгебры для ВУЗов послушать :-) Операция сложения в этом случае по условиям задачи должна быть определена как операция абстрактного сложения в коммутативной группе значений хэша, а вы это правило нарушили :-)

> Операция сложения в этом случае по условиям задачи должна быть определена как

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

ну тогда тоже не верно. вот что у вас выше:

> a % c + b % c = (a + b) % c

исходя из курса алгебры для ВУЗов... вообщем будет : a % c + b % c = a + b

я так понимаю вы в курсе расположения хранилища пирожков.