Hashtable是那么快

s [0] * 31 ^（n-1）+ s [1] * 31 ^（n-2）+ ... + s [n-1]。是java字符串的哈希函数，我假设其余的语言与此实现类似或接近。Hashtable是那么快

如果我们有散列表和50个元素的列表。每个元素是7个字符ABCDEF1，ABCDEF2，ABCDEF3 ..... ABCDEFn

如果每个哈希表存储桶包含5个字符串（我认为这个函数会使它每个桶一个字符串，但让我们假设它是5）。

如果我们调用col.Contains（“ABCDEFn”）; //会进行6次比较，并在7日发现差异。

散列表将需要大约70次操作（乘法和加法）才能获得散列码并与桶中的5个字符串进行比较。并找到它。

对于列表，它将需要大约300比较找到它。

对于仅有10个元素的情况，该列表将需要大约70次操作，但该Hashtable将需要大约50次操作。并注意哈希表操作更耗时（这是乘法）。

我的结论是，.Net中的HybirdDictionary可能是大多数情况下需要使用大小未知的哈希表的最佳选择，因为它会让我使用列表直到列表变得超过10个元素。仍然需要像HashSet而不是字典的键和值，我想知道为什么没有HybirdSet！

那你觉得呢？

谢谢

2010-04-02 Costa

我认为你提出一个好点。对于小数目，列表可能比哈希表更快，这在文献中完美记录。

但是，您可以轻松地创建自己的数据结构，根据其大小count()将使用List或Hash。

2010-04-02 06:19:45

这真的很重要吗？您通常关心大量数据集对性能的影响。如果收集量小，20-30个附加操作不会产生任何影响。

2010-04-02 10:30:37 Poma

我同意只有大多数情况下，我工作的应用程序，其中每mSec，转换为30分钟的吞吐量。为了更好地理解或回顾你所知道的事情，它仍然是重要的思考方式。 – Costa 2010-04-03 04:34:15

@Poma：有时你有小数据集，但有很多*访问。在这种情况下，容器的大小不是决定性的，而是其他一些参数。在这种情况下，即使是小型容器也可能因重度优化而受益。分析器会告诉你。 – 2010-04-05 14:59:30

如果你关心性能并拥有如此高负载的系统，那么使用C而不是C＃ – Poma 2010-05-19 18:00:29

回答