真是O(1)吗？想清楚了没？
2013-01-18 11:21 by 老赵, 15153 visits当然标题里这个O(1)可以换成任何复杂度。
话说写程序的时候我们会用到各种数据结构，但十有八九不会由我们自己从头写起，都会直接拿来用。于是很多人就会记住，譬如HashMap或Dictionary的存取是O(1)的操作，二分查找什么的则是O(log(N))。不过，我们在实践中直接把这些类拿来用的时候，最好也留个心眼，知道这些类内部到底做了些什么，为什么它们能够达到O(1)之类的时间复杂度。
例如，我们都知道List<T>的Add是O(1)的操作，但之所以它是O(1)，是因为它的“扩容”操作被均摊了（amortized），但每次扩容时其实还是需要复制所有元素，次数越少越好，于是实践中在可行的情况下我们往往应该给它指定一个初始容量——用StringBuilder的时候也是一样。
我这里还可以再举一个更为复杂的例子，例如HashSet和SortedSet，我们要向其中添加N个元素（如字符串），哪个会更快一些？从文档上可以知道，HashSet的Add方法是O(1)的操作，而SortedSet内部是用了红黑树，它的Add方法是O(log(N))的操作（但它能顺序输出元素）。显然，从时间复杂度上来讲，SortedSet的性能要落后于HashSet，不过我们能否设计一个用例，让HashSet慢于SortedSet呢？
当然可以，例如以前那个由哈希碰撞引起的DoS安全漏洞，其实就是设计了一些Hash Code相同，但具体内容不同的字符串，让Dictionary（原理与HashSet相同）Add/Remove操作的时间复杂度从O(1)退化为O(N)，这显然低于O(log(N))。不过如今的BCL中的实现已经对碰撞次数设置了阈值，超过这个阈值则会对哈希函数进行随机化，因此这种做法已经很难生效了。所以这里我们可以设计出另一个案例，且看代码：
static string[] GetRandomStrings(int number, int length) { var random = new Random(DateTime.Now.Millisecond); var array = new string[number]; var buffer = new char[length]; for (var i = 0; i < array.Length; i++) { for (var j = 0; j < buffer.Length; j++) { buffer[j] = (char)(random.Next(Char.MinValue, Char.MaxValue) + 1); } array[i] = new string(buffer); } Console.WriteLine("Generated"); return array; } static void CollectGarbage() { for (var i = 0; i < 10; i++) { GC.Collect(); GC.WaitForPendingFinalizers(); } } static void AddToSetTime(string name, ISet<string> set, string[] array) { CollectGarbage(); var watch = new Stopwatch(); watch.Start(); foreach (var s in array) { set.Add(s); } Console.WriteLine(name + ": " + watch.ElapsedMilliseconds); } static void Main() { var array = GetRandomStrings(5000, 50000); AddToSetTime("HashSet", new HashSet<string>(), array); AddToSetTime("SortedSet", new SortedSet<string>(), array); }
GetRandomStrings方法用于生成一系列的随机字符串，我们会将这些字符串使用AddToSetTime方法放入一个集合类中，并输出耗时。这段程序在我的机器上输出：
Generated HashSet: 165 SortedSet: 17
您可以自己尝试一下，具体数值可能不同，但HashSet显著慢于SortedSet则基本是确定的。为什么会这样？O(1)为什么完败于O(log(N))？难道HashSet的常数就那么大么？其实原因很简单，我们只需想想HashSet和SortedSet分别是怎么实现的就行。
HashSet：调用元素的GetHashCode方法获得Hash Code，算出该元素放在哪个Bucket中，然后顺着链表使用Equals方法依次比较Hash Code的相同元素。由于Hash Code散列程度较高，相同Bucket中重复元素极少，因此时间复杂度近似为O(1)。SortedSet：使用CompareTo方法比较新元素与红黑树里的元素，以此决定元素的树中的“走向”，需要时再进行“平衡”操作。由于一颗平衡二叉树的高度为log(N)，因此添加一个元素要进行大约log(N)次比较（以及最多log(N)次O(1)的平衡操作），其时间复杂度大约为O(log(N))。
看起来很正常嘛，但是其中还隐含一些“假设”，那就是GetHashCode、Equals还有CompareTo方法都是O(1)的操作，但事实真是如此吗？针对以上代码生成的随机字符串来说，Equals和CompareTo方法都可以几乎瞬间返回（比较第一个字符即可）。不过GetHashCode便麻烦一些了，便顺手从BCL的代码里摘抄出来吧：
namespace System { public sealed class String { public override int GetHashCode() { #if FEATURE_RANDOMIZED_STRING_HASHING if (HashHelpers.s_UseRandomizedStringHashing) { return InternalMarvin32HashString(this, this.Length, 0); } #endif // FEATURE_RANDOMIZED_STRING_HASHING unsafe { fixed (char* src = this) { Contract.Assert(src[Length] == '\0', "src[this.Length] == '\\0'"); Contract.Assert(((int)src) % 4 == 0, "Managed string should start at 4 bytes boundary"); #if WIN32 int hash1 = (5381 << 16) + 5381; #else int hash1 = 5381; #endif int hash2 = hash1; #if WIN32 // 32 bit machines. int* pint = (int*)src; int len = Length; while (len > 2) { hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1]; pint += 2; len -= 4; } if (len > 0) { hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; } #else int c; char* s = src; while ((c = s[0]) != 0) { hash1 = ((hash1 << 5) + hash1) ^ c; c = s[1]; if (c == 0) break; hash2 = ((hash2 << 5) + hash2) ^ c; s += 2; } #endif #if DEBUG // We want to ensure we can change our hash function daily. // This is perfectly fine as long as you don't persist the // value from GetHashCode to disk or count on String A // hashing before string B. Those are bugs in your code. hash1 ^= ThisAssembly.DailyBuildNumber; #endif return hash1 + (hash2 * 1566083941); } } } } }
从代码里可以看出，撇开最先的InternalMarvin32HashString这个不谈，其他分支下的哈希算法都是与字符串的长度呈线性关系。至于Marvin32这个神秘的哈希算法，我只知道可用于避免哈希碰撞攻击，但搜索了半天都找不到它的具体信息，只有一个“疑似”的简化实现。目前，我们还是用简单的测试来验证字符串长度与GetHashCode方法耗时的关系：
static void GetHashCodeTime(string name, string str, int iteration) { CollectGarbage(); str.GetHashCode(); // warm up var watch = new Stopwatch(); watch.Start(); for (var i = 0; i < iteration; i++) { str.GetHashCode(); } Console.WriteLine(name + ": " + watch.ElapsedMilliseconds); } static void Main() { var shortStr = new string('a', 100); var longStr = new string('a', 10000); var iteration = 1000000; GetHashCodeTime("Short", shortStr, iteration); GetHashCodeTime("Long", longStr, iteration); }
我们创建了长度相差百倍的字符串，并比较其GetHashCode方法的耗时。我们可以开启随机化的字符串哈希算法（即使用Marvin32哈希算法），例如打开之后在我的机器上执行结果是：
Short: 114 Long: 9142
耗时与长度基本呈线性关系。关闭“随机化哈希”之后执行速度略有提高，但耗时与长度的关系依然不变，其实从代码上也已经能够看出这点。
再回到最早针对HashSet和SortedSet的实验，由于我故意生成了长度高达5w的字符串，因此HashSet时间复杂度为O(1)又如何？单次GetHashCode方法调用的耗时，就已经远远超过许多次CompareTo方法了。从中我们也可以看出，假如我们用字符串作为字典的键，其效率会较int或是普通未重载过GetHashCode和Equals方法的类型为低。话说回来，其实用一个最普通的类作为字典的键效率很高，因为它的GetHashCode可以直接返回它的初始地址，而Equals方法则直接比较两个对象的引用。
在实践中，我遇到各种需要以字符串作为键的场景，我都会思考下有没有简单的替代方法，例如使用int做键，甚至直接使用数组。例如，前段时间@左耳朵耗子提到对一个csv文件里的数据进行排序，我们可以使用一个字典来保存一行数据，其中键为字段名：
List<Dictionary<string, string>> data = ...; var ordered = data .OrderBy(row => row["column0"]) // 先以column0排序 .ThenBy(row => row["column1"]); // 再以column1排序
但更有效率（内存使用也更紧凑）的做法是以一个数组来保存一行数据。我们先找出需要排序的列的下标，然后再从数组中找出排序用的字段值：
string[] columns = ...; var index0 = columns.IndexOf("column0"); var index1 = columns.IndexOf("column1"); List<string[]> data = ...; var ordered = data .OrderBy(row => row[index0]) .ThenBy(row => row[index1]);
从理论上讲，两种做法的时间复杂度一致，但实际上后者比前者会有不少提高。我们在了解“理论”的同时也需要注意实践上的细节，例如，其实在实践中O(log(N))其实也是个不比O(1)大多少的时间复杂度，此时可能也需要考虑下“常数”会对性能造成多大影响。
好文章...
话说最后那个，如果人家列数非常非常多，而且非常非常稀疏，可能Dic会好些(有点像邻接矩阵，邻接表的区别)...
最让我激动的是那个“（内存使用也更紧凑）”，Bjarne有一个演讲专门提到这个。他是讲的非常好，然后我就鸡毛当令箭了，上次在google面试，竟然脑子抽筋拿这个来问面试官...