散列字节字符串

Question

我正在处理个人项目,文件压缩程序,并且我的符号字典出现问题.我需要将以前遇到的字节字符串存储到结构中,以便我可以快速检查它们的存在并检索它们.我一直在假设哈希表最适合这个目的,因此我的问题将与哈希函数有关.但是,如果有人可以建议更好的哈希表替代方案,我会全力以赴.行.所以问题是我无法为这些字节串提供一个好的哈希键.我想到的一切都有非常不均匀的分布,或者需要太长时间.以下列出了我正在使用的情况:

1. 所有字节字符串的长度至少为两个字节.
2. 哈希表的最大大小为3839,很可能会填充.
3. 测试表明,与任何给定字节相比,与较低的7位相比,最高阶位的设置可能性显着降低.
4. 否则,字符串中的字节可以是0到255之间的任何值(我正在使用任何格式的原始字节数据).
5. 我在UNIX环境中使用C语言.我更喜欢坚持使用标准库,但它不需要可移植到其他操作系统.(IE unistd.h很好).
6. 安全无关紧要.
7. 速度是一个高度关注的问题.
8. 尺寸不是很严重,因为它不会被写入文件.但是,考虑到存储的字节字符串的潜在大小,存储空间可能在压缩期间成为问题.

Answer 1

一个线索是更适合这种事情,因为它可以让您存储您的符号为一棵树,并迅速对其进行分析,以匹配值(或拒绝).

作为奖励,你根本不需要哈希.您正在同时存储/检索/比较整个序列,同时仍然只保留最少量的内存.

编辑:作为额外的奖励,只需要第二次解析,你就可以查找与你当前序列"接近"的序列,这样你就可以摆脱一个序列,并使用前一个序列,一些内部保持差异的表示法.这将有助于您更好地压缩文件,因为:

1. 较小的字典意味着较小的文件,您必须将字典写入您的文件
2. 如果您添加人口上限并使用大文件命中,则较少数量的项目可以释放空间以容纳其他更罕见的序列.