用于高速和内存高效检测字符串重复的数据结构选择

本文关键字：数据结构 选择 字符串 检测 高速 内存 高效 用于 | 更新日期: 2023-09-27 18:31:10

>我有一个有趣的问题，可以通过多种方式解决：

  • 我有一个接受字符串的函数。
  • 如果此函数以前从未见过此字符串，则需要执行一些处理。
  • 如果函数之前看过字符串，则需要跳过处理。
  • 在指定的时间量后，该函数应接受重复的字符串。
  • 此函数每秒可能调用数千次，字符串数据可能非常大。

这是对实际应用程序的高度抽象的解释，只是为了问题的目的而试图深入到核心概念。

该函数需要存储状态才能检测重复项。它还需要存储关联的时间戳，以便使重复项过期。

它不需要存储字符串，字符串的唯一哈希就可以了，前提是没有由于冲突而导致的误报（使用完美的哈希？），并且哈希函数的性能足够高。

朴素的实现很简单（在 C# 中）：

 Dictionary<String,DateTime>

尽管为了降低内存占用并可能提高性能，但我正在评估自定义数据结构来处理此问题，而不是基本的哈希表。

那么，考虑到这些限制，你会使用什么？

编辑，一些可能更改建议实现的其他信息：

  • 99% 的字符串不会重复。
  • 几乎所有重复项都将背靠背或几乎按顺序到达。
  • 在现实世界中，该函数将从多个工作线程调用，因此需要同步状态管理。

用于高速和内存高效检测字符串重复的数据结构选择

我不相信在没有首先知道完整值集的情况下构建"完美哈希"是不可能的（尤其是在值数量有限的 C# int 的情况下）。因此，任何类型的哈希也需要能够比较原始值。

我认为字典是开箱即用的数据结构所能获得的最好的。由于您可以存储定义自定义比较的对象，因此可以轻松避免将字符串保留在模因中，而只需保存可以获得整个字符串的位置。即具有以下值的对象：

stringLocation.fileName="file13.txt";
stringLocation.fromOffset=100;
stringLocation.toOffset=345;
expiration= "2012-09-09T1100";
hashCode = 123456;

如果需要，cutomom 比较器将返回保存的哈希代码或从文件中检索字符串并执行比较。

字符串的唯一哈希值就可以了，前提是没有假 碰撞引起的阳性

如果您希望哈希代码短于字符串，这是不可能的。

使用哈希代码意味着存在误报，只是它们足够罕见，不会成为性能问题。

我什至会考虑仅从字符串的一部分创建哈希代码，以使其更快。即使这意味着您获得更多误报，它也可以提高整体性能。

如果内存占用是可以容忍的，我建议对字符串进行Hashset<string>，并建立一个队列来存储Tuple<DateTime, String>。像这样：

Hashset<string> Strings = new HashSet<string>();
Queue<Tuple<DateTime, String>> Expirations = new Queue<Tuple<DateTime, String>>();

现在，当一个字符串进来时：

if (Strings.Add(s))
{
    // string is new. process it.
    // and add it to the expiration queue
    Expirations.Enqueue(new Tuple<DateTime, String>(DateTime.Now + ExpireTime, s));
}

而且，您必须在某个地方检查过期时间。也许每次你得到一个新字符串时，你都会这样做：

while (Expirations.Count > 0 && Expirations.Peek().Item1 < DateTime.Now)
{
    var e = Expirations.Dequeue();
    Strings.Remove(e.Item2);
}

在这里很难击败Hashset的表现。当然，您正在存储字符串，但这将是保证没有误报的唯一方法。

您还可以考虑使用 DateTime.Now 以外的时间戳。我通常做的是在程序启动时启动Stopwatch，然后使用 ElapsedMilliseconds 值。这样可以避免在夏令时更改期间、系统自动更新时钟（使用 NTP）或用户更改日期/时间时发生的潜在问题。

上述解决方案是否适合您取决于您是否可以承受存储字符串的内存冲击。

在发布"其他信息"后添加：

如果这将由多个线程访问，我建议使用 ConcurrentDictionary 而不是 Hashset ，并且BlockingCollection而不是Queue。或者，您可以使用lock来同步对非并发数据结构的访问。

如果 99% 的字符串确实不会重复，那么您几乎肯定需要一个可以从字典中删除内容的过期队列。

如果存储整个字符串的内存占用不可接受，则只有两个选择：

1） 仅存储字符串的哈希值，这意味着哈希冲突的可能性（当哈希值比字符串短时）。良好的哈希函数（MD5，SHA1等）使这种碰撞几乎不可能发生，因此它只取决于它是否足够快以满足您的目的。

2）使用某种无损压缩。字符串通常具有良好的压缩比（约 10%），并且某些算法（如 ZIP）允许您在快速（效率较低）和慢速（压缩比高）压缩之间进行选择。压缩字符串的另一种方法是将它们转换为 UTF8，这既快速又容易做到，并且对于非 unicode 字符串具有近 50% 的压缩率。

无论您选择哪种方式，它始终在内存占用和哈希/压缩速度之间进行权衡。您可能需要进行一些基准测试以选择最佳解决方案。

相关文章：