Бьерн Страуструп - Язык программирования С++. Главы 2-4
Страница 34. Таблица имен

3.1.3  Таблица имен

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

       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:

          #include <string.h>

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

            for (name* n=table[ii]; n; n=n->next)    // поиск
                if (strcmp(p,n->string) == 0) return n;

            if (ins == 0) error("имя не найдено");

            name* nn = new name;                     // занесение
            nn->string = new char[strlen(p)+1];
            strcpy(nn->string,p);
            nn->value = 1;
            nn->next = table[ii];
            table[ii] = nn;
            return nn;
          }

 После вычисления хэш-кода ii идет простой поиск имени по членам
 next. Имена сравниваются с помощью стандартной функции
 сравнения строк strcmp(). Если имя найдено, то возвращается указатель
 на содержащую его запись, а в противном случае заводится новая запись
 с этим именем.
     Добавление нового имени означает создание нового объекта name
 в свободной памяти с помощью операции new (см. $$3.2.6), его
 инициализацию и включение в список имен. Последнее выполняется как
 занесение нового имени в начало списка, поскольку это можно сделать даже
 без проверки того, есть ли список вообще. Символьная строка имени
 также размещается в свободной памяти. Функция strlen() указывает,
 сколько памяти нужно для строки, операция new отводит нужную память,
 а функция strcpy() копирует в нее строку. Все строковые функции
 описаны в <string.h>:

         extern int strlen(const char*);
         extern int strcmp(const char*, const char*);
         extern char* strcpy(char*, const char*);