Предыдущий пост -

Хэш функция.

Рубрика: C++, Дата: 1 July, 2013, Автор:

Напишите хэш функцию, предназначенную для отображения равномерно распределенных целых значений в таблицу хэш-значений размером около 1024. Исходя из такой функции, придумайте набор из 1024 ключей, каждый из которых отображается в одно и то же значение.

Ну что ж начнем. Хэш таблица это просто массив размером 1024 ячейки. Хэш функция должна принимать ключ и возвращать хэш, то есть число в пределах от 0 до 1024. Чуток разобрались.

Теперь давайте подумаем над этой частью задачи: “Исходя из такой функции, придумайте набор из 1024 ключей, каждый из которых отображается в одно и то же значение.” . Тут от чуточку не понятно кажется, но все же можно предположить, что мы например 1024 ключа не сможем придумать, что бы например для них наша хэш функция генерировала например число 1000 или допустим какое нить другое число, поэтому нам проще придумать ключи при котором хэш функция будет генерировать максимальное число и для него мы уже будем как бы генерить максимальные ключи то есть 1024, Нам нужно такие ключи что бы хэш функция генерила больше 1024, ну ладно попробуем сделать хоть что нибудь.

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

#include <iostream>
using std::cout;
using std::endl;
#include <string>
using std::string;

int hash(string s)
{
	size_t res=0;
	typedef string::const_iterator CI;

	CI p=s.begin();
	CI end=s.end();

	while(p!=end)res=(res<<1)^*p++;
//	res%=1024;
	return res;
}

int main()
{
	cout <<"Test hash"<<endl;
	string s="hellow";
	for(int i=0;i<1024;i++)
	{
		char s1=i+'0';
		cout <<hash(s+s1)<<endl;
	}
	return 0;
}

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

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

[youtube]http://www.youtube.com/watch?v=M502EePgmd0[/youtube]

rss