当给定一组静态对象（从某种意义上说是静态的，一旦加载它就很少改变），需要以最佳性能重复并发查找，哪个更好，HashMap或者使用一些自定义比较器进行二进制搜索的数组？
答案是对象还是结构类型的函数？散列和/或相等的函数性能？哈希唯一性？列表大小？ Hashset尺寸/设置尺寸？
我正在查看的集合的大小可以从 500k 到 10m 不等——以防该信息有用。
虽然我正在寻找 C# 答案，但我认为真正的数学答案不在于语言，所以我不包括那个标签。但是，如果需要注意 C# 特定的事情，则需要该信息。
对于非常小的集合，差异将可以忽略不计。在您的范围的低端（500k 项），如果您进行大量查找，您将开始看到差异。二进制搜索将是 O(log n)，而哈希查找将是 O(1)，摊销。这与真正的常数不同，但您仍然必须拥有一个非常糟糕的哈希函数才能获得比二分搜索更差的性能。
（当我说“可怕的哈希”时，我的意思是：
hashCode()
{
return 0;
}
是的，它本身非常快，但会导致您的哈希映射成为链表。）
ialashkevich使用数组和字典编写了一些 C# 代码来比较这两种方法，但它使用 Long 值作为键。我想测试在查找过程中实际执行哈希函数的东西，所以我修改了那个代码。我将其更改为使用字符串值，并将填充和查找部分重构为它们自己的方法，以便在分析器中更容易看到。我还保留了使用 Long 值的代码，作为比较点。最后，我摆脱了自定义的二进制搜索功能，并使用了Array课堂上的那个。
这是代码：
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
以下是几种不同大小的集合的结果。（时间以毫秒为单位。）
500000 长值...
填充长字典：26
填充长数组：2
搜索长字典：9
搜索长数组：80500000 个字符串值...
填充字符串数组：1237
填充字符串字典：46
排序字符串数组：1755
搜索字符串字典：27
搜索字符串数组：15691000000 长值...
填充长字典：58
填充长数组：5
搜索长字典：23
搜索长数组：1361000000 个字符串值...
填充字符串数组：2070
填充字符串字典：121
排序字符串数组：3579
搜索字符串字典：58
搜索字符串数组：32673000000 长值...
填充长字典：207
填充长数组：14
搜索长字典：75
搜索长数组：4353000000 字符串值...
填充字符串数组：5553
填充字符串字典：449
排序字符串数组：11695
搜索字符串字典：194
搜索字符串数组：1059410000000 长值...
填充长字典：521
填充长数组：47
搜索长字典：202
搜索长数组：118110000000 字符串值...
填充字符串数组：18119
填充字符串字典：1088
排序字符串数组：28174
搜索字符串字典：747
搜索字符串数组：26503
为了比较，这是程序最后一次运行的分析器输出（1000 万条记录和查找）。我强调了相关的功能。他们非常同意上面的秒表计时指标。
您可以看到字典查找比二分查找快得多，并且（正如预期的那样）集合越大，差异越明显。所以，如果你有一个合理的散列函数（相当快，几乎没有冲突），散列查找应该胜过二进制搜索在这个范围内的集合。
Bobby、Bill 和 Corbin 的答案是错误的。对于固定/有界 n，O(1) 不比 O(log n) 慢：
log(n) 是常数，所以它取决于常数时间。
对于慢速散列函数，听说过 md5 吗？
默认的字符串散列算法可能涉及所有字符，并且很容易比长字符串键的平均比较慢 100 倍。去过也做过。
您可能能够（部分）使用基数。如果您可以分成 256 个大致相同大小的块，那么您正在查看 2k 到 40k 的二进制搜索。这可能会提供更好的性能。
[编辑] 太多人投票否决他们不理解的内容。
用于二进制搜索排序集的字符串比较有一个非常有趣的特性：它们越接近目标越慢。首先他们会在第一个字符上中断，最后只在最后一个字符上中断。假设他们的时间恒定是不正确的。
这个问题唯一合理的答案是：视情况而定。这取决于数据的大小、数据的形状、哈希实现、二进制搜索实现以及数据所在的位置（即使问题中没有提到）。其他几个答案也说了这么多，所以我可以删除它。但是，将我从反馈中学到的内容分享给我的原始答案可能会很好。
鉴于评论，您可能会认为使用哈希表的人精神错乱。哈希表是鲁莽和危险的吗？这些人疯了吗？
事实证明他们不是。正如二叉树擅长某些事情（按顺序数据遍历、存储效率）一样，哈希表也有其大放异彩的时刻。特别是，它们可以非常擅长减少获取数据所需的读取次数。哈希算法可以生成一个位置并直接在内存或磁盘上跳转到该位置，而二进制搜索在每次比较期间读取数据以确定接下来要读取的内容。每次读取都有可能导致缓存未命中，这比 CPU 指令慢一个数量级（或更多）。
这并不是说哈希表比二分查找更好。他们不是。这也不意味着所有哈希和二进制搜索实现都是相同的。他们不是。如果我有一个观点，那就是：这两种方法的存在都是有原因的。由您决定哪个最适合您的需求。
原答案：
哈希算法是 O(1)，而二进制搜索是 O(log n)。因此，当 n 接近无穷大时，哈希性能相对于二分查找有所提高。您的里程将根据 n、您的哈希实现和您的二进制搜索实现而有所不同。
关于 O(1) 的有趣讨论。释义：
O(1) 并不意味着瞬时。这意味着性能不会随着 n 大小的增长而改变。你可以设计一个非常慢的散列算法，没有人会使用它，它仍然是 O(1)。但是，我相当确定 .NET/C# 不会受到成本过高的散列的影响；）
好的，我会尽量简短。
C# 简短回答：
测试两种不同的方法。
.NET 为您提供了通过一行代码改变方法的工具。否则，请使用 System.Collections.Generic.Dictionary 并确保使用大量初始化它作为初始容量，否则由于 GC 必须执行收集旧存储桶数组的工作，您将在余生中插入项目。
更长的答案：
哈希表具有几乎恒定的查找时间，并且在现实世界中获取哈希表中的项目不仅需要计算哈希。
要获取某个项目，您的哈希表将执行以下操作：
查找时间取决于您的哈希函数有多“好”（输出有多稀疏）和快，您使用的桶数以及键比较器的速度有多快，这并不总是最好的解决方案。
哈希通常更快，尽管二进制搜索具有更好的最坏情况特征。哈希访问通常是通过计算获得哈希值以确定记录将在哪个“桶”中，因此性能通常取决于记录分布的均匀程度以及用于搜索桶的方法。对桶进行线性搜索的不良哈希函数（留下一些包含大量记录的桶）将导致搜索缓慢。（另一方面，如果您读取的是磁盘而不是内存，则哈希桶可能是连续的，而二叉树几乎可以保证非本地访问。）
如果您希望通常快速，请使用哈希。如果你真的想要保证有界的性能，你可以选择二叉树。
令人惊讶的是，没有人提到 Cuckoo 散列，它提供了保证 O(1)，并且与完美散列不同，它能够使用它分配的所有内存，而完美散列最终可以保证 O(1)，但浪费了它的大部分分配。警告？插入时间可能非常慢，尤其是当元素数量增加时，因为所有优化都是在插入阶段执行的。
我相信其中的某些版本在路由器硬件中用于 ip 查找。
见链接文字
与数组相比，字典/哈希表使用更多内存并且需要更多时间来填充。但是通过字典而不是数组内的二进制搜索来完成搜索更快。
这是要搜索和填充的1000万个Int64项目的数字。加上您可以自己运行的示例代码。
字典内存： 462,836
阵列内存： 88,376
填充字典：402
填充阵列： 23
搜索词典： 176
搜索数组： 680
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace BinaryVsDictionary
{
internal class Program
{
private const long Capacity = 10000000;
private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue);
private static readonly long[] Arr = new long[Capacity];
private static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Dict.Add(i, i);
}
stopwatch.Stop();
Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Arr[i] = i;
}
stopwatch.Stop();
Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = Dict[i];
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = BinarySearch(Arr, 0, Capacity, i);
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds);
Console.ReadLine();
}
private static long BinarySearch(long[] arr, long low, long hi, long value)
{
while (low <= hi)
{
long median = low + ((hi - low) >> 1);
if (arr[median] == value)
{
return median;
}
if (arr[median] < value)
{
low = median + 1;
}
else
{
hi = median - 1;
}
}
return ~low;
}
}
}
我强烈怀疑在大小约为 1M 的问题集中，散列会更快。
只是为了数字：
二分查找需要~ 20 次比较（2^20 == 1M）
哈希查找需要对搜索键进行 1 次哈希计算，之后可能需要进行少量比较以解决可能的冲突
编辑：数字：
for (int i = 0; i < 1000 * 1000; i++) {
c.GetHashCode();
}
for (int i = 0; i < 1000 * 1000; i++) {
for (int j = 0; j < 20; j++)
c.CompareTo(d);
}
时间：c = "abcde"，d = "rwerij" 哈希码：0.0012 秒。比较：2.4 秒。
免责声明：实际上对哈希查找与二进制查找进行基准测试可能比这个不完全相关的测试更好。我什至不确定 GetHashCode 是否在后台被记忆
我想说这主要取决于哈希和比较方法的性能。例如，当使用非常长但随机的字符串键时，比较总是会产生非常快的结果，但默认哈希函数将处理整个字符串。
但在大多数情况下，哈希映射应该更快。
我想知道为什么没有人提到完美散列。
仅当您的数据集长期固定时才有意义，但它会分析数据并构造一个完美的哈希函数以确保没有冲突。
非常简洁，如果您的数据集是恒定的并且与应用程序运行时间相比计算函数的时间很短。
这取决于您如何处理哈希表的重复项（如果有的话）。如果您确实希望允许哈希键重复（没有完美的哈希函数），主键查找仍然是 O(1)，但在后面搜索“正确”值可能代价高昂。答案是，理论上大多数时候，散列更快。YMMV 取决于你放在那里的数据......
这里描述了哈希是如何构建的，并且因为键的宇宙相当大，并且哈希函数被构建为“非常内射”，因此很少发生冲突，哈希表的访问时间实际上不是 O(1) ......基于某些概率的东西。但是，可以合理地说，哈希的访问时间几乎总是小于时间 O(log_2(n))
这个问题比纯算法性能的范围更复杂。如果我们去掉二分查找算法对缓存更友好的因素，散列查找在一般意义上更快。最好的解决方法是构建一个程序并禁用编译器优化选项，我们可以发现哈希查找更快，因为它的算法时间效率在一般意义上是 O(1)。
但是，当您启用编译器优化并尝试使用较少的样本（例如少于 10,000 个）进行相同的测试时，通过利用其缓存友好的数据结构，二分查找优于哈希查找。
当然，对于这么大的数据集，哈希是最快的。
由于数据很少更改，因此加快速度的一种方法是以编程方式生成临时代码以将第一层搜索作为一个巨大的 switch 语句（如果您的编译器可以处理它），然后分支到搜索结果桶。
答案取决于。让我们认为元素“n”的数量非常大。如果您擅长编写更好的散列函数以减少冲突，那么散列是最好的。
请注意，
哈希函数仅在搜索时执行一次，并指向相应的存储桶。所以如果 n 很高，这不是一个很大的开销。
哈希表中的问题：
但是哈希表中的问题是，如果哈希函数不好（发生更多冲突），那么搜索就不是 O(1)。它趋向于 O(n)，因为在桶中搜索是线性搜索。可能比二叉树更糟糕。
二叉树中的问题：
在二叉树中，如果树不平衡，它也趋向于 O(n)。例如，如果您将 1,2,3,4,5 插入到更可能是列表的二叉树中。
所以，
如果你能看到一个好的散列方法，使用散列表如果没有，你最好使用二叉树。
这更像是对比尔答案的评论，因为他的答案有很多赞成票，即使它是错误的。所以我不得不发布这个。
我看到很多关于在哈希表中查找的最坏情况复杂性是什么的讨论，以及什么被认为是摊销分析/什么不是。请检查下面的链接
与比尔所说的相反，最坏情况的复杂性是 O(n) 而不是 O(1)。因此他的 O(1) 复杂度没有被摊销，因为这种分析只能用于最坏的情况（他自己的维基百科链接也是这样说的）