��� ���������� ��������� � ���-������� ���������� ����� ������������ ������, ������� ������������ � ���� ��������� �������, ������ �� ������� ������������� ����� ���-�������. ���� ����� ���������� �����������. ������ �����, � ������� ��� �������� ������������� � ����� ���-�������, �������� ��� ������ ��� �������� ���������; ��� �������� �� ������� � ���������� ����������.
���� ���-������� ������������ ������������ ��������� ������ ���������� �� ��������� ��������, �� ����������� ���������� ��������� ��������� ������. ��������� ������ - ����� ��� ����� ���������� � ���� ������. ��� ���� �� �������� � ����� �������� �������, ������� � ��������� ��������������� ����������� ������ ���, ����� ���-������ ������. ������ �����, ��� ����� ������� ���-�������. ����� �� ���������� ���� ��������� �� ��������� ��������. ��� ����������� ������� ��������������, ��� unsigned char ������������� � 8 �����, unsigned short int - � 16, unsigned long int - � 32.
��� ������ ����� ������ ����� ����� ����� ����������� �������� hashTableSize. ����, ��������, hashTableSize ��������� ����, �� ��� ������ ������ ���-�������� ����� �������, ��� �������� - ���������. ����, ��� ��� ������������ - ���� ���� ��� ����� �������� �������, ��� ������� � ���� ������� �������. ����������, ���� ��� ����� �������� �������, �� hashTableSize, ������ ������� ����, �������� ������� ����� ����� Key � �������� �������. ����� �������� ����� ��������� ������������� ������, � �������� hashTableSize ����� ����� ������� �����, �� ������� ������� � ������� ����.typedef int HashIndexType; HashIndexType Hash(int Key) { return Key % HashTableSize; }
�����, ��������, ������ ������� hashTableSize ����� 1024 (210). ����� ��� ���������� 16-������ ������ � S ����� ��������� �������� 16 - 10 = 6. � ����� ��������:/* 8-bit index */ typedef unsigned char HashIndexType; static const HashIndexType K = 158; /* 16-bit index */ typedef unsigned short int HashIndexType; static const HashIndexType K = 40503; /* 32-bit index */ typedef unsigned long int HashIndexType; static const HashIndexType K = 2654435769; /* w=bitwidth(HashIndexType), size of table=2**m */ static const int S = w - m; HashIndexType HashValue = (HashIndexType)(K * Key) >> S;
typedef unsigned short int HashIndexType; HashIndexType Hash(int Key) { static const HashIndexType K = 40503; static const int S = 6; return (HashIndexType)(K * Key) >> S; }
typedef unsigned char HashIndexType; HashIndexType Hash(char *str) { HashIndexType h = 0; while (*str) h += *str++; return h; }
����� Rand8 - ������� �� 256 ������������� ��������� �����. �� ������ ������� �� ��������. ����� ����� ������ ����� � ������������; �� �������� ������ ����������� (Pearson [1990]).typedef unsigned char HashIndexType; unsigned char Rand8[256]; HashIndexType Hash(char *str) { unsigned char h = 0; while (*str) h = Rand8[h ^ *str++]; return h; }
������ ���-������� ������ ���� ���������� �������, ����� � ��� ���������� ������� ������� ����� ������ ����. ��� ����� �� ������� 3.1, ��� ������ �������, ��� ������ ������� ����� ������ ����� � ���. ���-������� ����� ������������� ��� ������������ ��������� �������. �� ���� ����, ��� ������� ������, ������������� ���������� ������� �, ��������������, ������� ����� ����� � ������ ������ �����������. ����� ���������� ��������� ����� n. ���� ������ ������� ����� 1, �� ������� ����������� � ���� ������ ����� n. ���� ������ ������� ����� 2 � ����������� ��������, �� ��� �������� ����� ���� � ����� �������� �� n/100 ��������� � ������. ��� ������ ��������� ����� ������, � ������� ����� ������. ��� �� ����� � ������� 3.1, ������� ������������ ������� � ������ ����� �������.typedef unsigned short int HashIndexType; unsigned char Rand8[256]; HashIndexType Hash(char *str) { HashIndexType h; unsigned char h1, h2; if (*str == 0) return 0; h1 = *str; h2 = *str + 1; str++; while (*str) { h1 = Rand8[h1 ^ *str]; h2 = Rand8[h2 ^ *str]; str++; } /* h is in range 0..65535 */ h = ((HashIndexType)h1 << 8)|(HashIndexType)h2; /* use division method to scale */ return h % HashTableSize }
������ | ����� | ������ | ����� | |
---|---|---|---|---|
1 | 869 | 128 | 9 | |
2 | 432 | 256 | 6 | |
4 | 214 | 512 | 4 | |
8 | 106 | 1024 | 4 | |
16 | 54 | 2048 | 3 | |
32 | 28 | 4096 | 3 | |
64 | 15 | 8192 | 3 |