����� �� �����.


������ ���������.

C�������� ������. �������� ����������.


���-�������

     ��� �� �������� ����������� �������� ���������� ������� - ���-�������. ������� ����� ������ �������� � ��� ���� O(1), ����� ��� ���������� ������ - O(n). ���������� ��������� ����������� ����� ����� � ������� �������[1990] � �����[1998].

     ���� ������ ������ �� ��� ����, ��� ����������� ������� ��������������� �������������. ����� ������ �����, ��������� ��� ���������� ��� �������� �����������. ������ �����, ��������� ��� ��������� ����������� ��� �������� ���������, ����������� ����.
 

������. �������� �����������

��-������� - ��� ������� ������ � ��������� ����������, ���������� ���-��������.

�������, �� hashTable ���. 3.1 - ��� ������ �� 8 ���������. ������ ������� ������������ ����� ��������� �� �������� ������, �������� �����. ���-������� � ���� ������� ������ ����� ���� �� 8 � ���������� ������� ��� ������ � �������. ��� ���� ��� ����� �� 0 �� 7 ��������� ��� ��������� � hashTable ��� � ����� ����� �� 0 �� 7, �������� ����������� ���������� �������� ��������.

���������� �������, ����� ������� �������� ��������� �������� ������ ���� �������� � ����� ������ ������, � ����� ������ ��������, ����������� ������������� �������. ���-������� ����� ����������� � ����� ������, �, ��������, � �������� ����������� ���� ������������ � �����������, ��� ��� ������ ����������� ������� ���������������. � ����� �����������, ������� - ��������� ��������� ������.

�� ��� ������ ������ � ������� ������ ���� ���������� ����� ���-�������, ������� ������ ������������� ���� �����������: ��� ������ ���� �������, � ��� ������ ��������� ������� ����� ��� ������������� ��������� �� �������. ��������� ���������� ������������ �������� (������, ����� ��� ������ �������� ����� ���������� �������� ���-�������) � ������������ ������, ����� �������� ������ � �������� ���������� �������� ������ � ���� ����� �������.


���. 3.1: ���-�������

����� �������� � ������� ����� �������, �� �������� ����, ����� ���������� ������, � ������� ��� ����� ��������, ����� ��������� ������� � ������ ����� ������. ��������, ����� �������� 11, �� ����� 11 �� 8 � �������� ������� 3. ����� �������, 11 ������� ���������� � ������, �� ������ �������� ��������� hashTable[3]. ����� ����� �����, �� ��� �������� � �������� �� ���������������� ������. ����� ������� �����, �� ������� ��� � ������� ������� ������, ��� ����������.

��� ���������� ��������� � ���-������� ���������� ����� ������������ ������, ������� ������������ � ���� ��������� �������, ������ �� ������� ������������� ����� ���-�������. ���� ����� ���������� �����������.

���� ���-������� ������������ ������������ ��������� ������ ���������� �� ��������� ��������, �� ����������� ���������� ��������� ��������� ������. ��������� ������ - ����� ��� ����� ���������� � ���� ������. ��� ���� �� �������� � ����� �������� �������, ������� � ��������� ��������������� ����������� ������ ���, ����� ���-������ ������. ������ �����, ��� ����� ������� ���-�������. ����� �� ���������� ���� ��������� �� ��������� ��������. ��� ����������� ������� ��������������, ��� unsigned char ������������� � 8 �����, unsigned short int - � 16, unsigned long int - � 32.

  • ������� (������ ������� hashTableSize - ������� �����). ���� ����� ����������� � ��������� �������. ���������� �������� hashValue, ������������ �� 0 �� (hashTableSize - 1), ����� ������� �� ������� ����� �� ������ ���-�������. ��� ��� ��� ����� ���������:
  • typedef int HashIndexType;
    
    HashIndexType Hash(int Key) {
        return Key % HashTableSize;
    }
    ��� ������ ����� ������ ����� ����� ����� ����������� �������� hashTableSize. ����, ��������, hashTableSize ��������� ����, �� ��� ������ ������ ���-�������� ����� �������, ��� �������� - ���������. ����, ��� ��� ������������ - ���� ���� ��� ����� �������� �������, ��� ������� � ���� ������� �������. ����������, ���� ��� ����� �������� �������, �� hashTableSize, ������ ������� ����, �������� ������� ����� ����� Key � �������� �������. ����� �������� ����� ��������� ������������� ������, � �������� hashTableSize ����� ����� ������� �����, �� ������� ������� � ������� ����.
  • ����������������� ����� (������ ������� hashTableSize ���� ������� 2n). �������� key ���������� �� ���������, ����� �� ���������� ������� ����������� ����� �����. � �������� ����� ��������� ���� ����������� ������� ������� (sqrt(5) - 1)/2 = 0.6180339887499. �����, ��������, �� �������� � �������. ������� ������� ������� �� 28, �������� 158. ���������� 8-������� ���� � 158, �������� 16-������� �����. ��� ������� ������ 25 � �������� ����������� �������� ����� 5 ������� ����� �������� �����, ����������� ����� ������������. ��� ��� ����� ����������� ���� �����:
  • /* 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;
    �����, ��������, ������ ������� hashTableSize ����� 1024 (210). ����� ��� ���������� 16-������ ������ � S ����� ��������� �������� 16 - 10 = 6. � ����� ��������:
    typedef unsigned short int HashIndexType;
      
    HashIndexType Hash(int Key) {
        static const HashIndexType K = 40503;
        static const int S = 6;
        return (HashIndexType)(K * Key) >> S;
    }
  • ���������� ����� ��� ����� ���������� ����� (������ ������� ����� 256). ��� ����� ���������� ����� ������ �������� ���������� ���� �������� �� ������ 256. � ���� ������ ��������� hashValue �������� ����� 0 � 255.
  • typedef unsigned char HashIndexType;
    
    HashIndexType Hash(char *str) {
        HashIndexType h = 0;
        while (*str) h += *str++;
        return h;
    }
  • ����������� ��� ��� ����� ���������� ����� (������ ������� ����� 256). ���� ����� ���������� �����������, �� ������� ��������� ������ ����� � ��������� (���������� ����� ���� ���� �������� ��� XY � YX). �����, ��� ����� ����������, ����������� � ���, ��� � ��������� ������ ��������������� ����������� �������� "����������� ���". � ������������� ��������� ����������� ��������� ����������, ����� ��� �������� ���������.
  • typedef unsigned char HashIndexType;
    unsigned char Rand8[256];
      
    HashIndexType Hash(char *str) {
        unsigned char h = 0;
        while (*str) h = Rand8[h ^ *str++];
        return h;
    }
    ����� Rand8 - ������� �� 256 ������������� ��������� �����. �� ������ ������� �� ��������. ����� ����� ������ ����� � ������������; �� �������� ������ �����������.
  • ����������� ��� ��� ����� ���������� ����� (������ ������� <= 65536). ���� �� �������� ������ ������, �� ������� ���-�������� ��� ������� ����� ����� �� 65536. ����� ������ ���������� �� ������ ���, � ������� ������� ������������ 1. ���������� ��� 8-������� ����� ������������ � ���� 16-�������.
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
}
������ ���-������� ������ ���� ���������� �������, ����� � ��� ���������� ������� ������� ����� ������ ����. ��� ����� �� ������� 3.1, ��� ������ �������, ��� ������ ������� ����� ������ ����� � ���. ���-������� ����� ������������� ��� ������������ ��������� �������. �� ���� ����, ��� ������� ������, ������������� ���������� ������� �, ��������������, ������� ����� ����� � ������ ������ �����������. ����� ���������� ��������� ����� n. ���� ������ ������� ����� 1, �� ������� ����������� � ���� ������ ����� n. ���� ������ ������� ����� 2 � ����������� ��������, �� ��� �������� ����� ���� � ����� �������� �� n/100 ��������� � ������. ��� ������ ��������� ����� ������, � ������� ����� ������. ��� �� ����� � ������� 3.1, ������� ������������ ������� � ������ ����� �������.
������ ����� ������ �����
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

������� 3.1: ����������� �������� ������� ������ (�s) �� hashTableSize. ����������� 4096 ���������.

����������

���������� ��������� �� �� ��������� typedef TcompGT ������� �������� ���, ����� ��� ��������������� ������, �������� � �������. ��� ������ ��������� ������� ����� ���������� hashTableSize � ������� ����� ��� hashTable. � ���-������� hash ����������� ����� �������. ������� insertNode ������� ������ ��� ����� ���� � ��������� ��� � �������. ������� deleteNode ������� ���� � ����������� ������, ��� �� ������������. ������� findNode ���� � ������� �������� ����.


����� �������� ���������.

     ����� ��� ��������������� ����������� �� ��������, �� ���� � ������ �������, ����� ������������ ������ ������������, ����������� ���������� ������, �����.

������ �������� ���-������� �������� ����������, ����� ������������ ������� ��������� ������ ������ ��� ���������. ���� ��������, ���, ����� �������� ������� ����������� ����� ��� �� 50 ���������, �� ������������� ����������� ���������� (��. ��������� ������, � �������������� ������ �� C, �������� ����, ������ �����, � Clovis Tondo, Prentice ����, 1991).

������� ������� ������ ������������ ��� ������������������ ������������� (��� ������ ��� ���������������� � ������) � ���, ��� ������� ������ (��� ��������� �������) �����������, � ������ ����� ��������.

     ���� ��� ���������� ������������ ��������� ��������� ���� T, ������ ����� ��������� �������� ������ n. ������� ��������� ������� h, ������������ �� ��������� ���� T � ����������� �������� 0..(n-1). ���� �� ������, ����� ��� ������� ��������� �� ��������� �������� ��������� �� ����������� ����� ������������� ��������. ������ ������ - ��� ����� �� �������� �� ���� ��������� ��������� ��������� ���������. ��� ������� ����� �������� ���-��������.

     ����� ��� �������
         val:  array [0..n-1] of T;
         used: array [0..n-1] of boolean;
		 
(�� ��������� ���� ������ n-1 � �������� ������� � ����������� ����, ���� � ������� ��� �� �����������). � ���� �������� ����� ��������� �������� ���������: ��� ����� ��������� ���� val [i] ��� ��� i, ��� ������� used [i], ������ ��� ��� val [i] ������ ��. �� ����������� �� ����� ������� ������� t �� ����� h(t), ������ ��� ����� "��������" ��� �������� t. ������ ����� ��� ������ ���, ��� ����� �������, ������� �� ����� ��������, ��� ������� �� ��� ������� ����� (��� �������� used �������). � ���� ������ �� ������ ��������� ������ ��������� ����� � ������� ��� ���� ����. ("������" ������ "� ������� ���������� ��������"; ����� �� ����, �� ������������� � ������.) �� �������������, ����� ��������� ������ ������ n, ��� ��� ������ ����� ��������� ����� �����.

     �������� ������, � ����� ������ ������ ����������� ����� ����������: ��� ������ �������� ��������� ������� ������ �� ��� ��������� ����� �� ��� ������������ ����� ��������� ��������.

     �������� ����� �������� �������������� ��������� �������� t �������������� �����: ����� �� h(t), ��������� �������, ���� �� ������ �� ������� ����� ��� �� �������� t. � ������ ������ ������� t ����������� � ���������, �� ������ ������������. ���� ������� �����������, �� ��� ����� �������� �� ��������� ������ �����. ���� ������������, �� ����� ��� ������� (������� used = false).

     ��� ���� ��������:

     >���� � ���, ��� ��� �������� ��������� �������� '���������� ������' ����� ����������. ������� ����� ������ ���. ������ ����, ����� ��������� �������, ���� �� ����������� �� ��� ���� ������ ����� (����� �� ���� ����� �����������) ��� �� ���- ����, ������� �� �� �������� �����. �� ������ ������ ���������, �� ����� �� ���� ������� ��������� �� ����� ����. ���� ���, �� ���������� �����, ���� ��, �� �������� �� ������ ����. ��� ���� ���������� ����� ����, � ������� ������ ��� �� �� �����.

     ���� ���� ������� �� �������, ����������� �������� ��������������, ���������� � �������� ��������� � ����� ��������.

     �� ��������� ���������������� ����������, ����� ������ �������� �� ����� 80% ���� �������.

������ ������� �����������, ������������ � Unix'��:

/*--- HashPJW	-----------------------------------------------------------*
  (��������� PJW) ����������� ��������� ����������� ������ ����������,     *
  ����������� �� ������ ������ �����. ��������� ��������� ��               *
  ������� ������, ������� ����� ���������������� � ���������� unsigned int *
---------------------------------------------------------------------------*/

#include <limits.h>

#define BITS_IN_int     ( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS  ((int) ((BITS_IN_int * 3) / 4))
#define ONE_EIGHTH      ((int) (BITS_IN_int / 8))
#define HIGH_BITS       ( ~((unsigned int)(~0) >> ONE_EIGHTH ))

unsigned int HashPJW
             ( const char * datum )
{
 unsigned int hash_value, i;

for ( hash_value = 0; *datum; ++datum )
 {
   hash_value = ( hash_value << ONE_EIGHTH ) + *datum;
   if (( i = hash_value & HIGH_BITS ) != 0 )
    hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
 }
 return ( hash_value );
}





����� �� ��������, � ���������� � ���������.

SpyLOG