Хеш-функция

Интересует наиболее быстрая "хеш-функция", которая возвращает не совсем хеш, а уже индекс в массиве. размер массива думаю 64Кб.
В stl смотрел. На вход подается строка. То есть только печатные символы. Сейчас просто беру первые 16 бит строки. Но это не устраивает, так как возникают пробелы с непечатаемыми символами. и коллизий много.

 

А почему бы не вычислить стандартный хэш от всей строки и взять его по модулю 65000 или около того? (видимо, желательно брать по модулю простого числа)

 

maxdiver

 

А вот что-то типа такого не катит?

 

Proteus
есть и такой вариант, в stl похожий, только вместо 175 другая константа. я думаю использовать что-нибудь похожее, прчием вместо 175 взять что нибудь более приемлимое, 2^n * 5, чтобы можно было вычислить комбинацией lea + shl.

 

censored
Один проход по строке, используя только умножение и сложение на каждом шаге - куда ж быстрее?

 

maxdiver

"mod" - не самая шустрая операция........ самые быстрые операции: ксор, сложение, сдвиг - вот на них хеш функу и надо делать.

 

UbIvItS
Ну я не говорил, что обязательно использовать деление...
Например, можно быстро взять по модулю 2^n+1, используя только сдвиги и сложения.
65537 как раз является простым

 

Если ещё Адлера функция. То же самое по смыслу и относительно быстрая. В википедии на русском описана.

 

Код (Text):

1. ELF (PJW)
2.  
3. // Dr. Dobb's Journal, April 1996
4.  
5. // HashPJW
6. // An adaptation of Peter Weinberger's (PJW) generic hashing
7. // algorithm based on Allen Holub's version. Accepts a pointer
8. // to a datum to be hashed and returned an unsigned integer
9.  
10. #include <limits.h>
11.  
12. #define BITS_IN_int     (sizeof(int) * CHAR_BIT)
13. define THREE_QUARTERS   ((int)((BITS_IN_int * 3 ) / 4))
14. #define ONE_EIGHT       ((int)(BITS_IN_int / 8)
15. #define HIGH_BITS       (~((unsigned int)(~0) >> ONE_EIGHT))
16.  
17. unsigned int HashPJW (const char* const datum)
18. {
19.     unsigned int    hash_value = 0;
20.     unsigned int    i = 0;
21.  
22.     for (hash_value = 0; *datum; ++datum)
23.     {
24.         hash_value = (hash_value << ONE_EIGHT) + *datum;
25.  
26.         if (i = hash_value & HIGH_BITS) != 0)
27.             hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
28.     }
29.  
30.     return hash_value;
31. }
32.  
33.  
34.  
35. // ElfHash
36. // The published hash algorithm used in the UNIV ELF format
37. // for object files. Accept a pointer to a string to be hashed
38. // and return an unsigned long.
39.  
40. unsigned long ElfHash(const unsigned char* const name)
41. {
42.     unsigned long h = 0;
43.     unsigned long g = 0;
44.  
45.     while (*name)
46.     {
47.         h = (h << 4) + *name++;
48.  
49.         if (g = h & 0xF0000000)
50.             h ^= g >> 24;
51.  
52.         h &= ~g
53.     }
54.  
55.     return h;
56. }

 

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

H = (H >>> 5) xor NextChar

тоже не подходит - при заполнении хеш-таблицы будет наблюдаться огромное число коллизий.

В своей реализации алгоритма сжатия LZW я использовал такую хеш-функцию:

Сначала таблица DWORD dwHashTable[256] заполняется случайными числами. В идеале следует использовать ГПСЧ или зарание подготовленную таблицу. У меня инициализация проходила так:

Код (Text):

1.     // получаем случайное число
2.     __asm {
3.         rdtsc
4.         mov dwHash, eax
5.     }
6.  
7.     // инициализируем хеш-таблицу
8.     // фишка - мы сами не знаем, как будут расбрасываться элементы списка
9.     for(i = 0; i < 256; i++) {
10.         dwHashTable[i] = dwHash*0x94A7F3D9; // взятое наугад нечетное число.
11.         dwHash++; // элементы таблицы будут чередоваться - четные и нечетные, но нас это мало волнует
12.     }

Из-за умножения инициализация проходит не очень быстро, зато потом хеш считается быстро:

Код (Text):

1. dwHash = dwHashTable[*(PBYTE)lpCurrPtr];
2.  
3. while(...) {
4.   dwHash ^= dwHashTable[(dwHash + (BYTE)lpCurrPtr[i++]) & 0xFF];
5.   __asm ror dwHash, 11
6. }

При использовании такого хеша поиск в хеш-таблице происходил в 70% случаев за 1 шаг, в 25% случаев - за 2 шага.


Настоятельно рекомендую в качестве размера массива указать степень двойки.

 

Зависит от заполненности таблицы

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

 

drmist

Это чем-то CRC32 напоминает.

Кстати ассемблерные вставки не очень нужны. В stdlib есть функция циклического вращения dwHash=_rotr(dwHash,11). Есть на любой платформе (проверял). Компиляторы обычно к тому же вставляют это как одну ассемблерную команду.

 

Proteus
Не исключено, что я излишне выпендрился и можно было обойтись банальным crc32. Но там функция инициализации подлиннее помнится, а хранить таблицу не хотелось. К тому же в моем случае невозможно подобрать такие строки, которые вызывали бы много коллизий, тк хеш считается всегда по-разному.

На счет _rotr не знал, спасибо.

 

сделал так:

Код (Text):

1. USHORT htblHash(PSTR s, UCHAR len)
2. {
3.     return (USHORT)(((*(PUCHAR)s) << 8) | len);
4. }

 

n0name
Что же, получается, можно спокойно менять все символы кроме первого и хэш остаётся тем же?
ИМХО неудачная хэш-функция.

 

Покопался в MSDN, набрёл на функцию HashData из shlwapi.dll. Можно подсмотреть алгос у M$ если есть желание.