O（1）插入时间和O（log m）查找的数据结构？
Backstory（跳到数据结构部分的倒数第二段）：我正在研究一种压缩算法（LZ77种类）。 该算法归结为查找给定字符串和已经看到的所有字符串之间的最长匹配。
为了快速做到这一点，我按照DEFLATE规范中的建议使用了一个散列表（带有单独的链接）：我为每个散列插入链中的m个插槽，每次插入一个到目前为止（每个输入字节一个）的每个字符串码。 插入速度很快（恒定时间，没有条件逻辑），但搜索速度很慢，因为我必须查看O（m）个字符串才能找到最长匹配。 因为我在一个典型的例子中进行了数十万次插入和成千上万的查找，所以如果我希望我的算法能够快速运行，那么我需要一个高效的数据结构（目前，对于m> 4，它太慢了;我想要一个m更接近128）。
我已经实现了一个特例，其中m是1，运行速度非常快，但只提供了如此的压缩。 现在我正在为那些喜欢改进压缩比超速的人制定一种算法，其中越大，压缩越好（显然，对某个点而言）。 不幸的是，到目前为止，我的尝试过于缓慢，因为压缩比的适度增加随着m的增加而变化。
所以，我正在寻找一种允许非常快速插入的数据结构（因为我做了比搜索更多的插入操作），但仍然是相当快的搜索（优于O（m））。 是否存在O（1）插入和O（log m）搜索数据结构？ 如果没有，那么最好的数据结构是什么？ 我愿意为了速度而牺牲记忆力。 我应该补充说，在我的目标平台上，跳转（ifs，循环和函数调用）非常缓慢，堆分配（为了获得可接受的性能，我必须使用原始字节数组实现所有内容）。
到目前为止，我已经考虑按排序顺序存储m个字符串，这将允许使用二进制搜索进行O（log m）搜索，但是插入也变为O（log m）。
谢谢！
您可能对这种匹配查找结构感兴趣：
http://encode.ru/threads/1393-A-proposed-new-fast-match-searching-structure
这是O（1）插入时间和O（m）查找。 但是，对于相同的匹配查找结果，（m）比标准哈希表低很多倍。 例如，在m = 4的情况下，该结构获得的结果与80探针哈希表等价。
您可能需要考虑使用trie（又名前缀树）而不是哈希表。
对于您的特定应用程序，您可能会另外优化插入。 如果您知道在插入ABC您可能会插入ABCD ，然后保留对为ABC创建的条目的引用，并只需使用D扩展---无需重复查找前缀。
哈希表中的一个常见优化是将刚刚找到的项目移动到列表的头部（想到可能会很快再次使用该存储桶）。 也许你可以使用这个想法的一个变种。
如果在进行查找之前完成所有插入操作，则可以向每个存储桶添加一点，以说明该存储桶的链是否已排序。 在每次查找时，您都可以检查该位以查看存储桶是否已排序。 如果没有，你会对桶进行排序并设置位。 一旦桶被分类，每个查找都是O（lg m）。
如果交织插入和查找，则每个存储桶可以有2个列表：一个是排序的，另一个不是。 插入将始终转到未排序的列表。 查找将首先检查已排序的列表，只有当它不在那里时才会查看未排序的列表。 当它在未排序的列表中找到时，您可以将其删除并将其放入排序列表中。 通过这种方式，您只需付费即可对查找的项目进行排序。
链接地址: http://www.djcxy.com/p/55625.html上一篇: Data structure with O(1) insertion time and O(log m) lookup?