3

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

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

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

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

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

天真的实现很简单（在 C# 中）：

 Dictionary<String,DateTime>

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

那么，鉴于这些限制，您会使用什么？

编辑，可能会改变提议的实施的一些附加信息：

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

4 回答 4

5

我不相信在不知道完整值集的情况下可以构造“完美哈希”（尤其是在 C# int 的值数量有限的情况下）。所以任何类型的散列也需要比较原始值的能力。

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

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

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

于 2012-04-14T05:03:23.043 回答
2

字符串的唯一散列会很好，前提是没有由于冲突而导致的误报

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

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

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

于 2012-04-14T05:04:28.830 回答
2

如果内存占用是可以容忍的，我建议Hashset<string>为字符串使用 a ，并使用队列来存储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在程序启动时启动 a ，然后使用该ElapsedMilliseconds值。这样可以避免在夏令时更改期间、系统自动更新时钟（使用 NTP）或用户更改日期/时间时发生的潜在问题。

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

在“附加信息”发布后添加：

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

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

于 2012-04-14T05:13:49.927 回答
1

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

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

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

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

于 2012-04-14T05:44:37.713 回答