java - 高效的大字符串(in)相等函数

Question

我需要比较非常大的基于文件的等长字符串以获得简单相等性，而无需首先计算哈希。

我想使用字符串中的数据进行大的、看似随机的跳跃，这样即使在开始和结束方式相同的字符串中，我也可以快速确定不等式测试。也就是说，我想在整个范围内跳跃，以某种方式大部分或完全避免多次击中同一个角色。

由于字符串是基于文件的并且非常大，我不希望我的跳转太大，因为这会破坏磁盘。

在我的程序中，字符串是一个简单的由文件支持的字符序列，大小小于 2gig，但很少一次完全在内存中。

然后在尝试了一段时间之后我假设它们是相等的并且我只是按顺序迭代。

我的字符串类变体都有一个 int length() 和 char charAt() 函数的基本接口(interface)，假设是 java 字符，通常但不总是 ascii。

任何想法，安迪

Answer 1

构建一些关于您的巨型字符串的元数据。

假设您将它们分成逻辑页面或 block 。您选择一个 block 大小，当您将一个 block 加载到内存中时，您对其进行哈希处理，将此哈希存储在查找表中。

当你去比较两个文件时，你可以先比较已知的子部分的哈希值，然后再去磁盘获取更多。

这应该让您在缓存和消除磁盘访问需求之间取得良好的平衡，而不会给您带来太多开销。