Проблема с функцией хеширования - C

Я использую следующую функцию хеширования, представленную в книге K&R.

#define HASHSIZE 101
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

В моем проекте включено больше предупреждений (предупреждения также рассматриваются как ошибки), и приведенный выше код не будет компилироваться.

error: conversion to ‘unsigned int’ from ‘char’ may change the sign of the result

Если я сделаю hashval подписано, я получаю отрицательные значения хеша. Мне интересно, как это можно исправить.

Любая помощь?

Источник

3 ответа

Решение

Ваш компилятор замечает и предупреждает вас о том, что вы неявно меняете свою интерпретацию байтов, хранящихся в области, на которую указывает s, Прототип функции указывает s как указатель на char и по умолчанию в вашей настройке, charКажется, они подписаны. Однако, чтобы получить правильную арифметику, вам нужно использовать только беззнаковые значения. Таким образом, вопрос заключается в следующем: что должен делать компилятор со значениями, указанными через s которые на самом деле имеют отрицательные значения?

Давайте быстро отвлечемся, чтобы убедиться, что мы понимаем, какие ценности мы можем рассматривать. Возможные значения для signed char являются CHAR_MIN в CHAR_MAX включительно. (Эти значения можно найти в limits.h.) Возможные значения для unsigned char являются 0 в UCHAR_MAX включительно. Таким образом, возникает вопрос: как мы представляем возможный диапазон значений из CHAR_MIN в CHAR_MAX в пределах диапазона 0 в UCHAR_MAX?

Один простой подход состоит в том, чтобы просто позволить компилятору выполнить это преобразование для вас: он просто использует арифметику с циклическим изменением, чтобы гарантировать, что значение находится в пределах: он автоматически добавляет UCHAR_MAX + 1 достаточно раз, чтобы получить значение, которое находится в пределах диапазона 0 в UCHAR_MAX, Тем не менее, фактическое значение этого будет потенциально зависеть от компилятора, который вы используете. Именно эта возможность непереносимости лежит в основе предупреждения вашего компилятора.

ОК, так откуда это у нас? Что ж, если вы готовы взять на себя ответственность за гипотетические проблемы переносимости, которые вызовет этот подход, вы можете сказать компилятору, что вы рады, что он выполнил преобразование, используя стандартные правила. Вы делаете это с помощью приведения:

hashval = ((unsigned char) *s) + 31 * hashval;

Этот подход подавит предупреждение и гарантирует, что ваша арифметика будет выполнена как беззнаковая, что вы и хотите для такого рода функций. Однако вы должны знать, что один и тот же код в других системах может давать разные результаты хеширования.

Альтернативный подход состоит в том, чтобы использовать тот факт, что стандарт ANSI C указывает, что указатели можно корректно приводить к типу. unsigned char * для доступа к базовой структуре байтов данных, на которые указывают. (У меня нет моей копии стандарта на данный момент, или я бы дал вам ссылку.) Это позволит вам обобщить этот подход для создания функции, которая дает вам хэш-значение любого значения данных. тип. (Однако, чтобы сделать это, вы должны подумать о том, как вы знаете размер передаваемых данных.) Это может выглядеть примерно так:

unsigned hash(void *s, size_t n) {
  unsigned char *t = (unsigned char *) s;

  while (n--)
    hashval = (*(t++) + 31 * hashval) % HASHSIZE;

  return hashval;
}

Я надеюсь, что это даст вам немного понимания того, что происходит.

Источник

+ Изменить s быть unsigned char * в сигнатуре функции, или просто приведение при использовании (т.е. (unsigned char *)s).

Источник

Я думаю, что вы можете безопасно типизировать свой символ без знака: (без знака)*s

Источник
Другие вопросы по тегам