Блог

Главная - Вопросы по программированию - хеш-функция для четко определенной строки c

хеш-функция для четко определенной строки c

#c #hash #hashtable

#c #хэш #хеш-таблица

Вопрос:

У меня есть строка, которая будет точно состоять из чисел от 1 до 30 и одного из символов ‘R’, ‘T’Or’M’. Позвольте мне проиллюстрировать это несколькими примерами.

 string a="15T","1R","12M","24T","24M" ...  // they are all valid for my string

Теперь мне нужно иметь хэш-функцию, которая дает мне уникальное хэш-значение для каждой входной строки. Поскольку мои входные данные имеют конечный набор, я думаю, что это возможно.

Есть ли кто-нибудь, кто может сказать, какую хэш-функцию я мог бы определить?

Кстати, я создам свою хэш-таблицу с использованием vector, поэтому я думаю, что размер не является важной проблемой, но я определю 10000 как верхнюю границу. Я имею в виду, я предполагаю, что у меня не может быть более 10000 таких строк

Заранее спасибо.

Комментарии:

1. Поскольку у вас есть только 90 различных значений, вы можете представить каждую строку одним 7-разрядным числом…

2. @KerrekSB да, вы так правы. Если вы напишете это как ответ, я приму его. Всем спасибо

3. @eday: что-то вроде number (0 if char == 'R' else 30 if char == 'T' else 60)

4. Если вы можете использовать код GNU, gperf он идеально подходит для вашего варианта использования.

Ответ №1:

Просто укажите достаточно большой целочисленный тип и поместите (максимум) три символа в целое число:

 std::size_t hash(const char* s) {
    std::size_t result = 0;
    while(*s) {
        result <<= 8;
        result |= *s  ;
    }
    return resu<
}

Ответ №2:

Вы могли бы определить алгебраическую функцию: 

 result = string[0] * 0x010000  
         string[1] * 0x000100
         string[2];

По сути, каждый символ помещается в an uint8_t , который имеет диапазон 256. Таким образом, каждый столбец имеет степень 256.

Да, есть большие пробелы, но это гарантирует уникальный хэш.

Вы могли бы сжать пробелы, используя различные «полномочия» для разных столбцов символов.

Задано «15T»:

 result = (string[0] - '0') * 10 // 10 == number of digits in the 2nd column  
         (string[1] - '0') * 3; // 3 == number of choices in 1st column.  
switch (string[2])
{
  case 'T' : result  = 0; break;
  case 'M' : result  = 1; break;
  case 'R' : result  = 2; break;
}

Это система подсчета чисел, в которой каждый столбец имеет разное количество цифр.

Ответ №3:

Что-то вроде:

 unsigned myhash(const char * str)
{
    int n = 0;

    // Parse the number part
    for ( ; *str >= '0' amp;amp; *str <= '9';   str)
        n = n * 10   (*str - '0');

    int c = *str == 'R' ? 0 : 
            *str == 'T' ? 1 :
            *str == 'M' ? 2 :
            3;

    // Check for invalid strings
    if ( c == 3 || n <= 0 || n > 30 || *(  str) != 0 )
    {
        // Some error or anything
        // (Or replace the if condition with an assert)
        throw std::runtime_error("Invalid string");
    }

    // Since 0 <= c < 3 and 0 <= (n-1) < 30
    // There are only 90 possible values
    return c * 30   (n-1);
}

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

Вы можете перестроить исходную строку с помощью:

 int n = hash % 30   1;
int c = hash / 30; // 0 is 'R', 1 is 'T', 2 is 'M'