我正在阅读一个算法问题，其中一个是:
对于一个包含数百万行数据的文件，有2行都是相同的。这些行太长了，可能不适合内存。找到这两行是一样的
建议的解决方案是分部分读取行，并为每行创建散列。
例如，您通过构建第1行第1部分的哈希(可以在内存中读取)来构建第1行的哈希，然后构建第1行的第2部分的哈希直到第1行的第n部分。
将哈希存储在文件或哈希表中。对于任何相同的哈希值，比较行。如果直线相等，我们就解出来了。
虽然我在高层次上理解这个解决方案，但我不知道如何实现。如何将散列与文件中的特定行关联?这是语言实现的细节吗?
例如，在Java中我们如何解决这个问题?
真正的答案是购买更多内存。Java中最长的字符串是2gb，现在的机器都能适应。你可以用不到200美元买到32 GB。
但是为了解决这个问题，我建议你
- 查找每行的偏移量
- 查找相同长度的行(使用偏移量的差异)
- 计算相同长度的行的64位或更长哈希值。
- 对于具有相同哈希值的行，逐字节比较。
注意:如果你没有足够的内存来缓存整个文件，这将花费很长时间。如果您有一台32 GB的机器，它有一个64 GB的文件，每次传递将花费大约20分钟，并且这有多个传递。
1)用哪个API查找偏移量?
计算已读取的字节数，这就是偏移量。
2)真正的答案是购买更多的内存项目经理不同意这对真正的产品。你有不同的经历吗?
我向他们指出，如果他们认为这是对资源的良好利用，我可以花一天时间节省100美元的可重用内存，这可能会花费他们1000美元(即使这不是我得到的报酬)。我让他们决定;)
我8岁的儿子有一台他自己造的8gb电脑，内存花了我24英镑。然而你是对的，有些项目经理认为8 GB对于专业人员来说太大了，每小时要花那么多钱!我的电脑有16gb的空间，我不会用它来运行任何严肃的事情，因为我的工作是在256gb的电脑上进行的。现在你可以买到2tb的机器，这对大多数应用来说都是多余的。div;)
虽然我同意解决方案是利用现代技术，并利用这些天廉价的内存，但这个问题是一个旨在锻炼大脑并理解如何在给定的约束下解决问题的问题。
你所说的散列相当简单。java解决方案可以利用一些底层的东西，这些东西可能会模糊实际发生的事情，所以我将首先解释解决方案，然后解释java实现。
通解:
哈希，如SHA1、MD5等，通过压缩输入生成一个整数。假设您只能在每行中存储前MB的字符。
- 你将遍历每一行，获得第一个MB字符，并将其传递给哈希算法(例如MD5)。
- 然后将哈希映射为键，将行号列表/数组映射为值。
- 在第一次传递之后，任何具有匹配的第一个MB字符的行将以相同的散列结束，因此在映射中的相同列表中。
- 为第二次传递做准备，您搜索地图并剔除仅包含一个行号的任何列表。
- 然后通过编译地图中剩余条目的行号来创建行号列表，这些行将是第二次检查的唯一行号。
- 第二遍，你从你的行列表中的每一行拉出第二MB的字符，散列它们，并将它们以与第一次相同的方式放在地图中。
- 遍历map中的条目，剔除只有一行号的哈希条目。
- 重复第二步，但增加字符块(MB)以与通过号一致。
- 当你到达一个只有多个行号的哈希，并且该哈希只有两个元素的通道时，这两个行是相同的。
这实际上是一个树状搜索。
Java方法:Java有一个名为HashMap的类，它会自动对键进行散列。通过使用
HashMap<String,ArrayList<Integer>>
- map.get (mbBlock)阀门(lineNumber);当然，你应该检查这是否是第一次使用这个键，这样你就不会得到一个空指针异常。
- 每次通过后，剔除只包含一行的条目。
- 在剩下的行上重复，直到只剩下两个行号
-
获取每行的前k个字符，其中k可以配置。执行散列查找可能具有相同行的几组行
-
基于第一步的结果，你大大缩小了搜索范围，在接下来的k个字符的每个小组上运行你的算法。
-
即使不是最坏的情况，搜索范围也会在每轮之后急剧缩小。
算法的诀窍是把大问题分解成小问题，并充分利用前面步骤的结果。