C#之Dictionary 与 C++之map

最近重学二叉查找树，顺便就好好看了看C#里Dictionary和C++的map的实现原理。

首先简单说明两个基本数据结构：

1. 散列表

　　散列表是一个key-value数据结构，可根据key值直接访问其存储位置。其核心是key与其存储位置的映射关系，即散列函数f(k)。当k1 != k2, f(k1) == f(k2)时，称之为碰撞。当散列表中没有碰撞时，其查找复杂度为O(1)，而最坏复杂度为O(n)，其中n为其存储的数据量。

2. 平衡树

　　平衡树是一种在高度上可以保持平衡(左右子树的高度差不超过1)的二叉查找树。正因如此，其查找复杂度最好最坏时都是O(log n)。另外，相比散列表，平衡树存储的为有序序列。

同样是常用key-value结构，C++ STL中的map是利用平衡树实现的，而C#中的Dictionary则使用散列表实现(MSDN描述为“Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey, TValue> class is implemented as a hash table.”)，只是不知道Dictionary使用了哪种碰撞处理方案...