在java中为字符串构造唯一的数字

Question

我们要求在文件中读/写超过1000万个字符串.此外,我们不希望文件中有重复项.由于字符串在读取后会立即刷新到文件中,因此我们不会将其保留在内存中.

我们不能使用哈希码,因为哈希码中的冲突导致我们可能会错过字符串作为重复.我在谷歌搜索中找到的另外两种方法:

1.使用消息摘要算法,如MD5 - 但计算和存储可能成本太高.

2.使用校验和算法.[我不确定这是否会产生一个字符串的唯一键 - 有人可以确认]

是否有任何其他方法可用.谢谢.

Answer 1

如果您对显微镜冲突的风险感到满意,可以按照建议使用一些哈希函数,例如MD5,并依赖哈希值.

另一种可能具有更大内存占用的替代方案是将已经遇到的字符串存储在trie(特殊类型的树)中.

更新:另一种替代方案是使用Bloom过滤器.然而,这仍然依赖于散列,但可以调整为具有任意小的碰撞概率.

Answer 2

在内存中存储1000万个字符串确实很多,所以我理解将其立即写入文件而不是存储在TreeSet<String>第一个文件中的原因,但是你想在哪里存储你要比较的1000万个唯一数字键？如果你想保持它的唯一性和数字(它比字母更小的基数/基数),你不能使密钥短于字符串本身,所以你不会保存任何内存.或者像GZIP那样最高的数据压缩,但这只会增加很多开销.MD5也不合适,因为两个不同的字符串可以产生相同的哈希值.

我真的没有看到比使用体面的RDBMS(SQL数据库)更好的解决方案,其中您将列设置为UNIQUE并相应地处理约束违规.RDBMS针对此类任务进行了高度优化.

如果你真的不能考虑数据库,那么你需要在写/刷新之前重新读取任何现有条目的文件.也许不是很快,但肯定是内存效率高.