Язык программирования C++ для профессионалов




Таблица имен


Есть функция поиска в таблице имен:

name* look(char* p, int ins =0);

Второй ее параметр показывает, была ли символьная строка, обозначающая имя, ранее занесена в таблицу. Инициализатор =0 задает стандартное значение параметра, которое используется, если функция look() вызывается только с одним параметром. Это удобно, так как можно писать look("sqrt2"), что означает look("sqrt2",0), т.е. поиск, а не занесение в таблицу. Чтобы было так же удобно задавать операцию занесения в таблицу, определяется вторая функция:

inline name* insert(const char* s) { return look(s,1); }

Как ранее упоминалось, записи в этой таблице имеют такой тип:

struct name { char* string; name* next; double value; };

Член next используется для связи записей в таблице. Собственно таблица - это просто массив указателей на объекты типа name:

const TBLSZ = 23; name* table[TBLSZ];

Поскольку по умолчанию все статические объекты инициализируются нулем, такое тривиальное описание таблицы table обеспечивает также и нужную инициализацию.

Для поиска имени в таблице функция look() использует простой хэш-код (записи, в которых имена имеют одинаковый хэш-код, связываются вместе):

int ii = 0;// хэш-код const char* pp = p; while (*pp) ii = ii<<1 ^ *pp++; if (ii < 0) ii = -ii; ii %= TBLSZ;

Иными словами, с помощью операции ^ ("исключающее ИЛИ") все символы входной строки p поочередно добавляются к ii. Разряд в результате x^y равен 1 тогда и только тогда, когда эти разряды в операндах x и y различны. До выполнения операции ^ значение ii сдвигается на один разряд влево, чтобы использовался не только один байт ii. Эти действия можно записать таким образом:

ii <<= 1; ii ^= *pp++;

Для хорошего хэш-кода лучше использовать операцию ^, чем +. Операция сдвига важна для получения приемлемого хэш-кода в обоих случаях.

Операторы

if (ii < 0) ii = -ii; ii %= TBLSZ;

гарантируют, что значение ii будет из диапазона 0...TBLSZ-1. Напомним, что % - это операция взятия остатка. Ниже полностью приведена функция look:




Содержание  Назад  Вперед