Хэш функции рассмотренные в параграфе 17.6.2.3, не всегда использует полное представление ключа. Когда часть представления игнорируется? Приведите пример, когда бывает разумным игнорировать часть ключа и напишите соответствующую хэш функцию.
Рассмотрим сами эти функции для начала.
|
1 2 3 4 5 6 7 8 9 10 |
template<class T>size_t Hash<T>::operator()(const T& key)const { size_t res=0; sizt_t len=sizeof(T); const char* p=reinterpret_cast<const char*>(&key); while(len--) res=(res<<1)^*p++; return res; } |
Здесь конечно функция будет возвращать полное представление ключа, полную длину, я так понимаю под не полным представлением ключа имеется в веду часть ключа, данная функция не обрезает ключ. Она возвращает просто значение какое есть, а уже в самой функции это значение обрезается на модуль b.size() на модуль размера таблицы хэшей. Вот этой строчкой кода.
|
1 |
size_type i=hash(k)%b.size(); |
Мне кажется эта часть обрезает ключ если ключ будет больше чем b.size(), то он сразу обрежится на не более размера хэш таблицы.
Ну от мы уже привели пример, когда разумно игнорировать часть ключа, это тогда когда ключ превышает хэш размер таблицы.
Пример функции не будем приводить, потому что нам нужно в самой функции будет проверять какой там ключ, превышает ли он размер таблицы или нет, а для этого нам нужно еще в эту функцию передавать сам размер хэш ключа, ну два размера. Да в принципе можно эту функцию написать, только я ее реально тестить не буду. Просто напишу какая она должна быть примерно, но что с двумя параметрами то точно, то что у нас hash наследуется от функционального объекта, то мы его от него наследовать не будем, потому что функция должна принимать один параметр а у нас она будет принимать два, поэтому нам структуру предется всю поменять. Приведу просто пример функции а все сами меняйте.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
template<class T>size_t Hash<T>::operator()(const T& key,int i) { size_t res=0; sizt_t len=sizeof(T); const char* p=reinterpret_cast<const char*>(&key); while(len--) res=(res<<1)^*p++; if(i<=res) res=hash(k)%i; return res; } |
Ну от как то так нужно делать. Что то подобное должно получится.
[youtube]http://www.youtube.com/watch?v=75Nm5rkbzNI[/youtube]