algorithm - 存储大量唯一字符串的最快方法是什么？

Question

我想知道存储大量字符串和检查重复的最佳方法是什么。

我们必须考虑我们的优先事项:

• 复查速度
• 插入新的字符串时间
• 硬盘存储空间
• 随机访问时间

当我们的目标是快速重复检查和插入新字符串时(随机访问或存储空间无关紧要)，最佳解决方案是什么？ 我考虑 SQL 数据库，但哪个数据库最适合这个解决方案？ 如果我们使用 SQL DB，比如 MySQL，哪个存储引擎最好？ (当然，由于数据量大，我们不得不排除内存)

Answer 1

对输入字符串使用哈希函数。输出散列将是记录的主键/ID。

然后你可以检查数据库是否有这个散列/id/主键:

• 如果不是:这是一个新字符串；您添加一条新记录，包括字符串和散列作为 id。
• 如果是:检查加载记录中的字符串是否与输入字符串相同。
  • 如果字符串相同:重复
  • 如果字符串不同:这是一个冲突。使用 collision resolution方案来解决。 (下面的几个例子)

您必须根据速度和预期的字符串数量以及哈希冲突要求/保证来考虑使用哪种哈希函数/方案/强度。

解决冲突的几种方法:

• 使用第二个哈希函数在同一个表中得出一个新的哈希值。
• 标记记录(例如使用 NULL)并在辅助“冲突”表上使用更强的第二哈希函数(具有更宽的域)重复。在查询中，如果字符串被标记为冲突(例如 NULL)，则在冲突表中再次进行查找。您可能还想使用 dynamic perfect hashing以确保第二张表不会再发生冲突。

当然，根据这需要多持久化以及您期望占用多少内存/字符串数量，您实际上可以在没有数据库的情况下直接在内存中执行此操作，这样会快得多。