Мне надо соорудить нечто, что будет напоминать хеш-таблицу с коллизиями. Сначала думал сформировать прототип хеш-мэпа в виде пары <char *, int>. А теперь смотрите какую он использует хеш-функцию:

inline size_t hash_value(const char *_Str)
{
...
		for(_Strsize _Idx = 0; _Idx <= _Size; _Idx += _Stride)
			_Val += (size_t)_Str[_Idx];
}

КРИВОРУКИЕ УРОДЫ! ЭТО Ж КОЛИЧЕСТВО КОЛЛИЗИЙ И ПРИДУМАТЬ ТАКОЕ СЛОЖНО!!!
Тогда возникает вопрос. У меня есть четыре целых и одна строка переменной длины. Как мне на основе этого сформировать хеш?
Два условия: минимизировать коллизии и максимизировать скорость.
У кого-нибудь предложения есть?

P.S. С hash_multimap кто-нибудь работал? Или примерчик на посмотреть даст?

Примерчики уже нашел. Дундук. В MSDN 8-)
Остается лишь вопрос по хеш-функции.

Ну возьми великий и могучий ELF hash

Вот чего надыбал:

#include "GeneralHashFunctions.h"

unsigned int RSHash(string str)
{

   unsigned int b = 378551;
   unsigned int a = 63689;
   unsigned int hash = 0;

   for(unsigned int i = 0; i < str.length(); i++)
   {
      hash = hash*a+str[i];
      a = a*b;
   }

   return (hash & 0x7FFFFFFF);

};
/* End Of RS Hash Function */


unsigned int JSHash(string str)
{

   unsigned int hash = 1315423911;

   for(unsigned int i = 0; i < str.length(); i++)
   {
      hash ^= ((hash << 5) + str[i] + (hash >> 2));
   }

   return (hash & 0x7FFFFFFF);

};
/* End Of JS Hash Function */


unsigned int PJWHash(string str)
{

   unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
   unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
   unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
   unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
   unsigned int hash             = 0;
   unsigned int test             = 0;

   for(unsigned int i = 0; i < str.length(); i++)
   {

      hash = (hash << OneEighth) + str[i];

      if((test = hash & HighBits)  != 0)
      {

         hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));

      }

   }

 return (hash & 0x7FFFFFFF);

};
/* End Of  P. J. Weinberger Hash Function */


unsigned int ELFHash(string str)
{

   unsigned int hash = 0;
   unsigned int x    = 0;

   for(unsigned int i = 0; i < str.length(); i++)
   {
      hash = (hash << 4) + str[i];
      if((x = hash & 0xF0000000L) != 0)
      {
         hash ^= (x >> 24);
         hash &= ~x;
      }
   }

   return (hash & 0x7FFFFFFF);

};
/* End Of ELF Hash Function */


unsigned int BKDRHash(string str)
{

   unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
   unsigned int hash = 0;

   for(unsigned int i = 0; i < str.length(); i++)
   {

      hash = (hash*seed)+str[i];

   }

   return (hash & 0x7FFFFFFF);

};
/* End Of BKDR Hash Function */


unsigned int SDBMHash(string str)
{

   unsigned int hash = 0;

   for(unsigned int i = 0; i < str.length(); i++)
   {

      hash = str[i] + (hash << 6) + (hash << 16) - hash;

   }

   return (hash & 0x7FFFFFFF);

};
/* End Of SDBM Hash Function */


unsigned int DJBHash(string str)
{

   unsigned int hash = 5381;

   for(unsigned int i = 0; i < str.length(); i++)
   {

      hash = ((hash << 5) + hash) + str[i];

   }

   return (hash & 0x7FFFFFFF);


}
/* End Of DJB Hash Function */

Гы, нашел, наконец-то RFC по MD5, а то все никак найти не мог...

ftp://ftp.rfc-editor.org/in-notes/rfc1321.txt

Вдруг пригодиться , не помню откуда сливал там и rfc этот есть

_1137406300__md5.zip

volodya
нуу ваще-то MD5 он немаленький (там толи 128 толи 160 бит), относительно медленный, но дает минимум коллизий (ес-но при такой-то длине)
вопрос сильно зависит от контекста - что за дворды у тебя используются, что за строки...
напр, если твои дворды это VA, то можно использовать даже младший байт - уже получишь хорошую минимизацию коллизий. старший байт (word) использовать не стоит вообще, т.к. коллизий будет очень много.

короче, все это очень относительно...

з.ы. я проверял как-то CRC32 на именах функций из всех dll, найденных у меня на машине (а установленно у меня оочень много), так вот, была (кажется) пара функций, дающих коллизию.
Так что MD5, это, имхо, лишнее...

Да я уже не о своем случае, здесь я и ELFHash с лихвой обойдусь. От добра добра не ищут. Я не настолько помешанный на алгоритмах, чтобы где надо и где не надо их использовать :)

можно попробовать md4 - вроде как побыстрей md5 будет