logo标签列表

短字符串的哈希函数

cstringmathhash
9
我希望将弱嵌入式系统中的函数名发送到主机以进行调试。由于两者通过RS232连接，带宽短缺，因此我不想直接发送函数名称。有一些长度为15个字符的函数名称，我有时候想要以相当高的速率发送这些名称。
我考虑的解决方案是找到一个哈希函数，可以将这些函数名称哈希到单个字节，并仅发送该字节。主机将扫描源中的所有函数，使用相同的函数计算其哈希值，然后将哈希值转换为原始字符串。
哈希函数必须满足以下条件：
1. 对于短字符串无碰撞。 2. 简单（因为我不想在嵌入式系统中编写太多代码）。 3. 适合单个字节。
显然，它不需要特别安全，只需无碰撞即可。因此，我认为使用与加密相关的哈希函数并不值得它们的复杂性。
以下是示例代码：
int myfunc() {
    sendToHost(hash("myfunc"));
}

主机将能够向我呈现myfunc函数执行时间列表。
是否有一些已知的哈希函数符合上述条件？
编辑：
1. 我假设我会使用少于256个函数名。 2. 我可以使用多个字节，两个字节就足够了。 3. 我更喜欢使用哈希函数而不是在客户端和服务器上使用相同的函数到字节映射，因为（1）我在客户端没有映射实现，也不确定是否想要为调试目的添加一个。 （2）它需要我的构建链中的另一个工具将函数名称表注入我的嵌入式系统代码中。在这方面，哈希更好，即使这意味着我偶尔会发生冲突。
2
好的，单字节意味着您最多可以拥有256个不同的函数名称。这对于您的嵌入式系统是否正确？此外，如果所有函数名称都已确定且静态，为什么不使用枚举来映射每个函数？ - KJ Saxena
16
你考虑过使用以下一种或多种通用哈希函数吗：http://www.partow.net/programming/hashfunctions/index.html。 - Matthieu N.
8个回答
8

试试 最小完美哈希：

最小完美哈希保证n个键将映射到0..n-1，没有任何冲突。

包含C代码。

没有获取所有函数名称，这是行不通的。 - Guffa
是的，只有在您预先知道所有字符串的情况下才能进行完美哈希。如果不是这种情况，一种方法是使用哈希表来处理冲突，然后传输哈希表中条目的索引。 - Martin B
您可能还可以劝说gperf或类似的工具在编译时进行内联，从而将计算成本降至0。 - Hasturkun
3

嗯，由于您将解析源代码以了解所有可能的函数，因此仅有256个可能值，也许最好的方法是为每个函数分配一个数字？

一个真正的哈希函数可能不会起作用，因为你只有256个可能的哈希值。但你想映射至少26^15个可能的值（假设只使用字母，大小写不敏感的函数名称）。即使您限制了可能的字符串数量（通过应用一些强制格式），您也很难获得有意义的名称和有效的哈希函数。

3

不，不行。

仅凭八位哈希无法生成无碰撞的哈希码，甚至接近都不可能。如果允许长度超过一个字符的字符串，则可能的字符串数量超过可能的哈希码数量。

为什么不只提取函数名并为每个函数名分配一个ID呢？然后你只需要在通信双方的每一侧使用查找表即可。

（正如其他人所示，如果您已经拥有所有函数名称，则可以生成无冲突的哈希算法，但这时更容易为每个名称分配一个数字以制作查找表...）

1
为什么会有踩票？如果你不说出你不喜欢的是什么，那就毫无意义。 - Guffa
8位哈希根据字符串数量可能是可以的——根据生日悖论，对于20个字符串来说，这应该是相当可行的，如果你足够努力地搜索，你可以找到一个适用于40或50个字符串的无冲突8位哈希。但是，如果你不想花费精力寻找无冲突哈希函数，你是正确的，你可能需要一个2到4字节的哈希。 - Craig McQueen
为什么要点踩？如果你不解释哪里有问题，那么回答就无法得到改进。 - Guffa
3
你可以使用Huffman树根据函数在程序中出现的频率来缩写函数名称。最常用的函数可以缩写为1位，不太常见的函数可以缩写为4-5位，非常罕见的函数可以缩写为10-15位等。Huffman树并不难实现，但你需要处理一些位对齐的问题。

Huffman tree

2
如果您有一种跟踪代码内部功能的方法（例如在运行时生成的文本文件），则可以使用每个函数的内存位置。这不完全是一个字节，但比整个名称更小，并且保证是唯一的。这具有低开销的附加优势。您只需要“解码”地址的文本文件即可将地址映射到实际名称；此文件可以发送到远程位置或存储在本地计算机上。
这是我的做法。你应该能够使用编译后的二进制文件中的调试信息来提取函数名称，而不需要额外的表格。 - Brooks Moses
0
在这种情况下，您可以使用枚举来标识函数。在某个头文件中声明函数ID：
typedef enum
{
    FUNC_ID_main,
    FUNC_ID_myfunc,
    FUNC_ID_setled,
    FUNC_ID_soundbuzzer
} FUNC_ID_t;

然后在函数中：

int myfunc(void)
{
    sendFuncIDToHost(FUNC_ID_myfunc);
    ...
}
0
这里介绍了一种简单的实现方法：http://www.devcodenote.com/2015/04/collision-free-string-hashing.html 以下是文章中的一部分：
它的灵感来自于二进制数如何被解码并转换为十进制数格式的方式。每个二进制字符串表示都唯一地映射到十进制格式中的一个数字。
例如，如果我们有一个由大写英文字母组成的字符集，则字符集的长度为26，其中A可以用数字0表示，B可以用数字1表示，C可以用数字2表示，以此类推，直到Z用数字25表示。现在，每当我们想将该字符集的字符串映射到唯一的数字时，我们执行与二进制格式相同的转换。
该链接指向一个受到攻击的网站，请更新或删除它！ - Balázs Édes
0

如果发送方和接收方共享相同的函数名称集，他们可以从这些函数构建完全相同的哈希表。您可以使用到达哈希元素的路径来进行通信。这可以是{起始位置+跳数}以进行通信，这需要2个字节的带宽。对于固定大小的表（线性探测），只需要最终索引来寻址条目。

注意：在构建两个“同步”的哈希表时，插入顺序非常重要 ;-)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接