【C数据结构】查找（四）红黑树与哈希表

最近在学习C++ STL中的集合与映射，二者底层是由红黑树或哈希表构成，因此有必要深入了解一下其原理。

一、红黑树
红黑树（Red-Black Tree），是一种特殊的二叉查找树，其每个结点上都有一个标志位来存储结点的颜色，Red or Black。
⑴红黑树的一些特性：

①根结点必定是黑色；
②每个叶子结点必定是黑色；（此处的叶子是指空的叶子结点）
③若一个结点是红色，它的子结点必须是黑色；
④从一个结点到该结点的子结点的所有路径上，包含相同数目的黑色结点。（即没有一条路径会比其他路径长出两倍，使得红黑树是相对接*衡的二叉树）

红黑树的应用比较广泛，主要用来存储有序的数据，其时间复杂度为O(log n)，C++中的 set 和 map 就是以此为基础的。有关红黑树的结点增删引起树的调整过于复杂在此不做介绍，需要了解的可以翻看 查找（二）——动态查找表 该部分详细介绍了平衡二叉树的树形结构调整策略，这里仅简单描述一下其基本旋转方法和目的。
⑵红黑树的左旋和右旋
红黑树的基本操作是添加和删除，在对红黑树进行添加或删除之后都会用到旋转方法。因为每次对树的结点进行增删都会使得其可能不再满足红黑树的某些特性，这时候就需要通过旋转调整树的结构，使其重新成为红黑树。
①左旋
对一个结点左旋，简单来说就是将这个结点变成一个左结点，这里给出一个简单事例说明。

对结点A左旋，意味着将 A的右孩子C 转到 A的父结点 位置，即A经过旋转变成了C的左结点。

②右旋
同样地，对一个结点右旋，就是将这个结点变成一个右结点。

有关红黑树的树形结构调整涉及到平衡二叉树的操作，在此不做重复扩展。

二、哈希表
哈希表也叫散列表，是根据键值(key - value)直接进行访问的数据结构。

①它通过哈希函数把 k-v 值映射到表中一个位置来访问记录，从而加快查找速度。
②记录k的存储位置为 f(k), 这里的对应关系 f 称为散列函数，也称哈希函数。
③采用散列技术将记录存储在一块连续的存储空间中，即为散列表或哈希表。
哈希表的查询速度非常快，几乎是O(1)的时间复杂度，但不同的关键字可能得到同一哈希地址，这种现象称为冲突，而具有相同函数值的关键字对该哈希函数来说称作同义词。

那么根据以上特性，可以进一步准确描述哈希表：根据设定的哈希函数 f(key) 和处理冲突的方法将一组关键字映像到一个有限的连续的地址区间上，并以关键字在地址区间中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

下面分别就哈希函数和处理冲突的方法进行讨论。

1. 哈希函数的构造方法
   ⑴直接定址法
   实现方法：取关键字或关键字的某个线性函数值为哈希地址。即 f(key) = a * key + b，其中a和b为常熟，这种哈希函数叫做自身函数。

   ⑵数字分析法（不常用）

   ⑶平方取中法
   实现方法：取关键字平方后的中间几位为哈希地址，取的位数由表长决定。因为通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。
   这里给出一个在BASIC源程序中建立哈希表的例子。假设计算机内可用两位八进制数表示字母和数字，如图所示。
   取标识符在计算机中的八进制数为它的关键字，假设表长为512 = 2 9 2^9 29，则可取关键字平方后的中间 9 位二进制数为哈希地址。
   

⑷折叠法（不常用）

⑸除留余数法
实现方法：取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数为哈希地址。
即 f(key) = key MOD p ,p<=m。它不仅可以对关键字直接取模，也可在直接定址、平方取中运算后取模。
值得注意的是，在使用该方法时，对 p 的选择很重要，选不好容易产生同义词。一般情况下，可以选 p 为质数 或 不包含小于20的质因数的合数。

⑹随机数法
实现方法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 f(key) = random(key)，其中random为随机函数。通常当关键字长度不等时采用此法构造哈希函数。

选择构造方法时，通常需要考虑的因素：
①计算哈希函数所需要的的时间；
②关键字的长度；
③哈希表的大小；
④关键字的分布情况；
⑤记录的查找频率。

2. 处理哈希表冲突的方法
⑴开放定址法

f i    =    (    f ( k e y )    +    d i    )    M O D    m          i    =    1 ,    2 ,    . . .    ,    k ( k ≤ m − 1 ) f_i\;=\;(\;f(key)\;+\;d_i\;)\;MOD\;m\;\;\;\;i\;=\;1,\;2,\;...\;,\;k(k\leq m-1) fi​=(f(key)+di​)MODmi=1,2,...,k(k≤m−1) 其中 f ( k e y ) f(key) f(key)为哈希函数，m 为哈希表表长， d i d_i di​为增量序列，有以下三种取法：
① d i = 1 , 2 , 3 , . . . , m − 1 d_i =1, 2, 3, ... , m-1 di​=1,2,3,...,m−1，称线性探测再散列；
② d i    =    1 2 ,    − 1 2 ,    2 2 ,    − 2 2 ,    . . .    ,    ± k 2    ( k ≤ m 2 ) d_i\;=\;1^2,\;-1^2,\;2^2,\;-2^2,\;...\;,\;\pm k^2\;(k\leq\frac m2) di​=12,−12,22,−22,...,±k2(k≤2m​)，称二次探测再散列；
③ d i d_i di​为伪随机数序列，称伪随机探测再散列。

简析：
使用线性探测再散列时，可能会发生“二次聚集”，即处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继地址的现象，这使得在处理同义词的冲突过程中又添加了非同义词的冲突，对查找不利。但使用线性探测再散列处理冲突可以保证只要哈希表未填满，总能找到一个不发生冲突的地址。二次探测再散列只有在哈希表长 m 为形如 4j+3 的素数时才能较好处理冲突。

⑵拉链法
实现方法：取所有关键字为同义词的记录存储在统一线性链表中。如下图所示

拉链法可以理解为用于存放记录的数组被声明为了指针数组。如图，左边是一个数组，数组成员是一个指向链表头的指针，链表可能为空，也可能链接多个元素，通过这种方法就能解决多个值对应一个存储位置的冲突。

⑶建立公共溢出区
假设哈希函数的值域为[ 0, m-1 ]，则设向量HashTable[0…m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0…v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。