Вся информация, вводимая в компьютер, кодируется в соответствии с одной из систем кодирования (таблиц кодировки). В большинстве таких систем символы (цифры, буквы, служебные знаки) представляются однобайтовыми двоичными числами. В последних версиях Windows (NT, 2000) используется система кодировки Unicode, в которой символы представляются в виде двухбайтовых двоичных величин. Как правило, ключевые поля элементов таблиц — строки символов, Наиболее известные алгоритмы закрытого хэширования основаны на следующих методах [32]:
- деления;
- умножения;
- извлечения битов;
- квадрата;
- сегментации;
- перехода к новому основанию;
- алгебраического кодирования;
- вычислении значения CRC (см. соответствующую главу).
Далее мы рассмотрим только первые четыре метода. Остальные
методы — сегментации, перехода к новому основанию, алгебраического
кодирования — мы рассматривать не будем. Отметим лишь, что их используют
либо в случае значительной длины ключевых слов, либо когда ключ состоит
из нескольких слов. Информацию об этих методах можно получить в
литературе .
Рассмотрение методов хэширования будет произведено на примере одной
задачи. Это позволит лучше понять их особенности, преимущества,
недостатки и возможные ограничения.
Необходимо разработать программу — фрагмент компилятора, которая
собирает информацию об идентификаторах программы. Предположим, что в
программе может встретиться не более М различных имен. Длину возможных
имен ограничим восьмью символами. В качестве ключа используются символы
идентификатора, какие и сколько — будем уточнять для каждого из методов.
Элемент таблицы состоит из 10 байт: 1 байт признаков, 1 байт для
хранения длины идентификатора и 8 байт для хранения символов самого
идентификатора.