对于非常小的集合，这种差异是可以忽略不计的。在您的范围低端（500k项）时，如果您需要进行大量查找操作，您将开始看到差异。二分查找的时间复杂度为O(log n)，而哈希表的查找时间复杂度为O(1)，“摊销时间”（amortized）。虽然这并非真正恒定，但您需要使用非常糟糕的哈希函数才能获得比二分查找更差的性能。
（当我说“糟糕的哈希”时，我的意思是类似以下这样的东西：
hashCode()
{
return 0;
}
是的，虽然它本身非常快，但会导致你的哈希映射变成链表。
ialiashkevich编写了一些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://dev59.com/qHM_5IYBdhLWcg3whzjx#1344258
*/
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万条记录和查找）。我已经突出了相关函数。它们与上面的计时指标非常接近。
可以看出，字典查找比二分查找快得多，并且（如预期的那样）差异随着集合大小的增加而更加明显。因此，如果您有一个合理的哈希函数（执行较快，没有太多碰撞），哈希查找应该比二分查找在这个范围内的集合上表现更好。
根据评论，你可能会认为使用哈希表的人是疯子。哈希表是否鲁莽和危险？这些人是疯了吗？
事实证明他们不是。就像二叉树擅长某些事情（按顺序遍历数据，存储效率），哈希表也有它发光的时刻。特别是，在减少读取数据所需的数量方面，哈希表可以非常出色。哈希算法可以生成一个位置并直接跳转到内存或磁盘中的它，而二分查找在每次比较中读取数据以决定下一步要读取什么。每次读取都有可能导致缓存未命中，这比CPU指令慢一个数量级（甚至更多）。
这并不意味着哈希表比二分查找更好。它们不是。这也不意味着所有哈希和二分查找实现都相同。他们不是。如果我有一个观点，那就是：两种方法都有存在的理由。由您决定哪种最适合您的需求。
原始答案：
好的，我会尝试简短明了。
C＃简短回答：
测试两种不同的方法。
.NET提供了让你通过一行代码更改你的方法的工具。 否则使用System.Collections.Generic.Dictionary， 并确保使用一个大数值来初始化它作为初始容量， 否则您将因为GC需要收集旧桶数组而花费余生插入项目。
较长的答案：
一个哈希表几乎具有恒定的查找时间， 而在现实世界中获得哈希表中的项并不仅需要计算哈希。
为了到达一个项，您的哈希表将执行以下操作：
查找时间取决于哈希函数的“好坏”程度（输出有多稀疏和快速）， 您使用的桶数以及键比较器的速度， 它并不总是最佳解决方案。
更好和更深入的解释： http://en.wikipedia.org/wiki/Hash_table
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);
}
times: c = "abcde", d = "rwerij" hashcode: 0.0012 秒。比较: 2.4 秒。
免责声明：实际上，对哈希查找和二进制查找进行基准测试可能比这个不完全相关的测试更好。我甚至不确定 GetHashCode 是否在幕后进行了备忘录。
但在大多数情况下，哈希表应该更快。