Хеш-функция для коротких строк

Question

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

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

Хеш-функция должна быть

1. Без столкновений для коротких струн.
2. Простой (поскольку я не хочу, чтобы во встроенной системе было слишком много кода).
3. соответствует одному байту

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

Пример кода:

int myfunc() {
    sendToHost(hash("myfunc"));
}

Хозяин сможет представить мне список случаев, когда выполнялась функция myfunc.

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

Edit:

1. Полагаю, я буду использовать намного меньше 256 имен функций.
2. Я могу использовать больше, чем один байт, два байта обеспечат мне хорошее покрытие.
3. Я предпочитаю использовать хеш-функцию вместо того, чтобы использовать одну и ту же функцию-байтовую карту на клиенте и сервере, потому что (1) у меня нет реализации карты на клиенте, и я не уверен, что хочу поставить один для целей отладки. (2) Требуется другой инструмент в моей цепочке сборки, чтобы внедрить таблицу имен функций в код моей встроенной системы. Хеш лучше в этом отношении, даже если это означает, что я буду иметь столкновение время от времени.

Answer 1

Попробуйте минимальное идеальное хеширование :

Минимальное идеальное хеширование гарантирует, что n ключей будут отображаться в 0..n-1 без коллизий вообще.

С код включен.

Answer 2

Вы можете использовать дерево Хаффмана для сокращения имен ваших функций в соответствии с частотой их использования в вашей программе. Наиболее распространенная функция может быть сокращена до 1 бита, менее распространена до 4-5, очень редко - до 10-15 бит и т. Д. Дерево Хаффмана не очень сложно реализовать, но вам придется что-то делать с выравниванием битов.

Answer 3

Нет, нет.

Вы не можете создать хеш-код без коллизий или даже близко к нему, используя только 8-битный хеш. Если вы разрешите строки длиной более одного символа, у вас будет больше возможных строк, чем возможных хеш-кодов.

Почему бы просто не извлечь имена функций и присвоить каждому имени функции идентификатор? Тогда вам понадобится только справочная таблица на каждой стороне провода.

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

Answer 4

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

Реальная хеш-функция, вероятно, не будет работать, потому что у вас есть только 256 возможных хешей. но вы хотите отобразить как минимум 26 ^ 15 возможных значений (при условии только буквенных, без учета регистра имен функций). Даже если вы ограничите количество возможных строк (применяя некоторое обязательное форматирование), вам будет сложно получить как значимые имена, так и действительную хеш-функцию.

Answer 5

Если у вас есть способ отслеживать функции в вашем коде (то есть текстовый файл, сгенерированный во время выполнения), вы можете просто использовать ячейки памяти каждой функции. Не совсем байт, но меньше целого имени и гарантированно будет уникальным. Это имеет дополнительное преимущество - низкие накладные расходы. Все, что вам нужно для «декодирования» адреса, - это текстовый файл, который сопоставляет адреса с реальными именами; это может быть отправлено в удаленное местоположение или, как я уже говорил, сохранено на локальном компьютере.

Answer 6

Описанный здесь простой способ реализовать его самостоятельно: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Вот фрагмент из поста:

Он черпает вдохновение в том, как двоичные числа декодируются и преобразуются в формат десятичных чисел. Каждое двоичное строковое представление однозначно отображается на число в десятичном формате.

если, скажем, у нас есть набор символов заглавных английских букв, то длина набора символов равна 26, где A может быть представлен числом 0, B - номером 1, C - номером 2 и так далее до Z числом 25. Теперь, когда мы хотим отобразить строку этого набора символов в уникальное число, мы выполняем то же преобразование, что и в случае двоичного формата

Answer 7

Если отправитель и получатель используют один и тот же набор имен функций, они могут создавать из них идентичные хеш-таблицы. Вы можете использовать путь, взятый, чтобы добраться до хеш-элемента, чтобы сообщить об этом. Это может быть {начальная позиция + количество прыжков}, чтобы сообщить об этом. Это займет 2 байта полосы пропускания. Для таблицы фиксированного размера (линейное зондирование) только конечный индекс необходим для адресации записи.

ПРИМЕЧАНИЕ: при построении двух «синхронных» хеш-таблиц важен порядок вставки; -)

Answer 8

В этом случае вы можете просто использовать enum для идентификации функций. Объявите идентификаторы функций в некотором заголовочном файле:

typedef enum
{
    FUNC_ID_main,
    FUNC_ID_myfunc,
    FUNC_ID_setled,
    FUNC_ID_soundbuzzer
} FUNC_ID_t;

Тогда в функциях:

int myfunc(void)
{
    sendFuncIDToHost(FUNC_ID_myfunc);
    ...
}