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

Question

Я использую следующую функцию хеширования, представленную в книге 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 со знаком, я получу отрицательные значения хеш-функции.Мне интересно, как это можно исправить.

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

Answer 1

Ваш компилятор обнаруживает и предупреждает вас о том, что вы неявно меняете свою интерпретацию байтов, хранящихся в области, на которую указывает 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. Однако фактическое значение этого параметра может зависеть от используемого вами компилятора. Именно эта возможность непереносимости лежит в основе предупреждения вашего компилятора.

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

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;
}

Надеюсь, это даст вам некоторое представление о том, что происходит.

Answer 2

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

Answer 3

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