我有一堆字符串作为键.就像是...
AAAA ABBA ACEA ALFG
...
...
ZURF [AAA _JFS aKDJ
它们都是任意4个字符的独特组合,并且长度都相同.有成千上万的这些.我想执行查找并检索与每个字符串关联的值.
我目前将它实现为哈希表,但主要关注的是冲突(我已经在Wiki上实现了所有策略).
我正在考虑将其实现为前缀树.鉴于参数虽然(唯一,固定长度),我想知道是否有一个现成的数据结构,我想不到最适合这个......
编辑:此外,所有可能的组合都由数据文件填充一次.然后,查找以线速发生.
在我的环境中，Gperf 的性能始终低于 Judy 数组，我想知道是否有另一个专门为整数键构建的完美哈希库。我事先知道一组键，并且我想利用它来获得性能/尺寸优势。
有大约 1000 个键，并且检索不按顺序排列。密钥对都是整数。密钥是 32 位，检索的值是 8 位。尺寸是最重要的因素。
如果有一种方法可以针对整数键调整 Gperf，或者只是另一种方法，我也会洗耳恭听。:)
（旁注：...在输入这个问题时，我意识到二分搜索可能会更有效，而且我只是过度思考了这个问题。为了学习，我仍然想听听您的任何想法，尽管！）
编辑：键分布不均匀。大多数是在整个可能的范围内随机聚集的。
编辑 2：最坏情况的二进制搜索对我来说太慢了，所以我最终使用了这些键，直到我找到每个键可以使用 8 位来创建 256 个均匀分布的存储桶。我保存了每个桶的最小值和最大值（每个桶条目 24 位），并为密钥对创建了一个大的结构数组。与我在特定情况下测试的其他所有产品相比/更快且更小，所以我想我现在就采用它。:)
如果这是一个非常愚蠢的问题，我预先致歉。
目前，我有一个循环链表。节点数通常保持不变。当我想添加它时，我分配了多个节点（例如100000左右）并将其拼接起来。当我一一分配节点时，这部分工作正常。
我想尝试按块分配：
NODE *temp_node = node->next;
NODE *free_nodes = malloc( size_block * sizeof( NODE ) );
node->next = free_nodes;
for ( i = 0; i < size_block - 1; i++ ) {
free_nodes[i].src = 1;
free_nodes[i].dst = 0;
free_nodes[i].next = &free_nodes[i+1];
}
free_nodes[size_block - 1].next = temp_node;
只要我不尝试释放任何东西（“检测到glibc：双重释放或损坏”错误），该列表就起作用。凭直觉，我认为这是因为释放它不会释放单个节点，并且以正常方式循环是试图多次释放它（加上释放整个块可能会使仍然存在的节点上的所有其他指针变了吗？ ），但：
这样做的目的是因为我要成千上万次调用malloc，如果事情更快，那就太好了。如果有更好的方法可以解决此问题，或者我不能指望它会更快，那么我也很高兴听到这样的消息。:)