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

Question

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

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

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

Answer 1

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

然后你可以检查数据库是否有这个哈希/id/主键：

如果不是：这是一个新字符串；您添加一个新记录，包括字符串和哈希作为 id。
如果是：检查加载记录中的字符串是否与输入字符串相同。
- 如果字符串相同：它是重复的
- 如果字符串不同：这是一次碰撞。使用冲突解决方案来解决。（下面举几个例子）

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

解决冲突的几种方法：

使用第二个散列函数在同一个表中提出一个新的散列。
标记记录（例如，使用 NULL）并在辅助“碰撞”表上使用更强的第二个散列函数（具有更宽的域）重复。查询时，如果字符串被标记为冲突（例如 NULL），则在冲突表中再次查找。您可能还想使用动态完美散列来确保第二个表没有进一步的冲突。

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