散列算法+二叉排序树?

In computing, a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

维基百科对于散列表的定义如上。下面的说明中我们总是认为$key$为整数。

一个最简单的散列函数大概就是这样(其中$n$为数组长度)$$f(x)=xmod n$$显然我们无法保证对于所有的$x$，$f(x)$是唯一的，所以需要处理冲突。

如果检测到冲突，就把$x$安排到目前的位置的下一个，这种方法听起来非常粗暴，而且会对其他的$key$造成影响，所以并不推荐这么使用。

检测到冲突后，应用一个新的散列函数来计算新的散列值，我也没用过。

在上面两种情况下，我们的array真的只是一个array，但是如果把它换成二维的，对于每一个散列值，后面都跟着一个链表，冲突后直接把新的$key$加入到链表中，则是一个很好的解决方案。可以证明，在随机分布的参数值中，我们几乎不会遇到一个各个散列值分布极其不均匀的情况。

二叉搜索树(Binary Search Tree, BST)是一棵有序的二叉树，理想情况下它是平衡的，对于增删改查的操作都可以以$O(lg n)$的时间复杂度解决。但是在实际应用时，平衡的二叉树几乎不会遇到，很多时候二叉树甚至会退化成一个链表，大大降低效率。所以出现了一批自平衡二叉树，通过附加的信息来保持树的平衡。

红黑树是资格最老，应用最广的平衡二叉树之一，经典的SGI STL就是用它实现了map和set

用高度的附加信息来保持严格平衡的二叉树，据说在M$ Windows的内核中扮演的重要地位。

基于随机思想的二叉树，从附加信息来看是一个堆，从$key$的角度看是BST

基于$size$的严格平衡的二叉树，因为$size$并不是无用的附加信息，所以被认为是一个很有潜力的结构。

开个玩笑，相关信息参见维基

在散列表中我们提到过，为了处理冲突，我们可以在数组中挂上一个链表。但是链表的长度是一个很大的问题，过长的链表将会降低散列表的效率。如果我们用二叉树来代替链表，甚至用另一个散列表来代替链表，也许能提高很多效率。
据说java源码里有这么做的

待续代码