Как реализовать функцию комбинирования слова для создания ключа на вход хешфункции(для хеш таблицы)

Question

Есть задание

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

Я написал вот такую функцию

unsigned short WordCombination(const char* str){
    unsigned short lenght = strlen(str);
    unsigned short modSum = 0;
    for (unsigned short i = 0; i < lenght; i+=2){
        unsigned short word = str[i]; //размещение символа в шестнадцатибитной сетке
        word = (word << BYTE) | str[i + 1]; //объеденение двух симвлов
        word = (word >> STEP) | (word << (WORDSIZE - STEP)); //циклический сдвиг
        modSum += word; //накопление суммы по мо
    }
    return modSum;
}

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

Answer 1

Avp дело говорит. Должно быть что-то, что ограничивает диапазон входных значений, и тем самым позволит сжимать без потерь. Например, должен быть ограничен алфавит входных значений вроде только латиницы в нижнем регистре. Тогда строку из 3 символов получится без потерь запихнуть в 2 байта, т.к в латинице лишь 25 символов, на это надо 5 бит, а в двух байтах 16 бит.

Получается так:

#include <stdio.h>
#include <string.h>

// Ограниченный алфавит
const unsigned VALUE_MIN = 'a';
const unsigned VALUE_MAX = 'z';
// Сколько бит на него надо
const unsigned VALUE_BITS = 5;
// Сколько байт удастся сжать без потерь
// VALUE_BITS / два байта = 5/16
const unsigned MAX_LENGTH = 3;

unsigned short WordCombination(const char* str) {
    unsigned length = strlen(str);
    unsigned short result = 0;
    if (length > MAX_LENGTH) {
        printf("- got too long string of %u", length);
    }
    for (unsigned i = 0; i < length; i++) {
        unsigned char v = str[i];
        // Проверка границ
        if (v < VALUE_MIN) {
            printf("- got too small byte %u", v);
            v = VALUE_MIN;
        }
        if (v > VALUE_MAX) {
            printf("- got too large byte %u", v);
            v = VALUE_MAX;
        }
        // Добавление со смещением
        unsigned short add = (str[i] - VALUE_MIN) << (i * VALUE_BITS);
        result |= add;
        // printf("- add %u\n", add);
    }
    return result;
}

int main() {
    const char* s = "blh";
    unsigned short v = WordCombination(s);
    printf("Source: %s\nResult: %u\n", s, v);
}

БЛОГ НА HUSL

Как реализовать функцию комбинирования слова для создания ключа на вход хешфункции(для хеш таблицы)

Ответы (1 шт):