【基础知识】|作者 / Edison Zhou
从本篇开始，我们开始讨论基于哈希技术的查找方法。哈希（散列）技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而哈希技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，哈希主要是面向查找的存储结构。哈希技术最适合的求解问题是查找与给定值相等的记录。
本篇为哈希技术的基础概念部分，阅读时间大约为5min+。
1哈希定义的引入
这里首先看一个场景：在大多数情况下，数组中的索引并不具有实际的意义，它仅仅表示一个元素在数组中的位置而已，当需要查找某个元素时，往往会使用有实际意义的字段。例如下面一段代码，它使用学生的学号来查找学生的地址。
（1）学生实体类定义
public class StudentInf{ public string Number { get; set; } public string Address { get; set; } public StudentInfo(string number, string address) { Number = number; Address = address; }}
（2）通过索引遍历查找
static StudentInfo[] InitialStudents()
{
StudentInfo[] arrStudent = {
new StudentInfo("200807001","四川达州"),
new StudentInfo("200807002","四川成都"),
new StudentInfo("200807003","山东青岛"),
new StudentInfo("200807004","河南郑州"),
new StudentInfo("200807005","江苏徐州")
};
return arrStudent;}
static void NormalSearch(StudentInfo[] arrStudent, string searchNumber)
{
bool isFind = false;
foreach (var student in arrStudent)
{
if (student.Number == searchNumber)
{
isFind = true;
Console.WriteLine("Search successfully!{0} address:{1}", searchNumber, student.Address);
}
}
if (!isFind) {
Console.WriteLine("Search {0} failed!", searchNumber);
}
}
static void Main(string[] args)
{
StudentInfo[] arrStudent = InitialStudents();
// 01.普通数组遍历查找
NormalSearch(arrStudent, "200807005");
Console.ReadKey();
}
运行结果如下图所示，可以看到圆满完成了查找任务。
但是，如果查找的记录位于数组的最后或者根本就不存在，仍然需要遍历整个数组。当数组非常巨大时，还以这样的方式查找将会消耗较多的时间。是否有一种方法可以通过学号关键字就能直接地定位到相应的记录？
（3）改写查找方式为哈希查找
通过观察学号记录与索引的对应关系，学号的后三位数组恰好是一组有序数列，如果把每个学生的学号后三位数组抽取出来并减去1，结果刚好可以与数组的索引号一一对应。于是，我们可以将上例改写为如下方式：
static int GetHashCode(string number)
{
string index = number.Substring(6);
return Convert.ToInt32(index) - 1;
}
static void HashSearch(StudentInfo[] arrStudent, string searchNumber)
{
Console.WriteLine("{0} address:{1}", searchNumber, arrStudent[GetHashCode(searchNumber)].Address);
}
static void Main(string[] args)
{
StudentInfo[] arrStudent = InitialStudents();
HashSearch(arrStudent, "200807005");
HashSearch(arrStudent, "200807001");
Console.ReadKey();
}
可以看出，通过封装GetHashCode()方法，实现了学号与数组索引的一一对应关系，在查找中直接定位到了索引号，避免了遍历操作，从而提高了查询效率，从原来的O(n)提高到了O(1)，运行结果如下图所示：
上例中的学号是不重复的，它可以唯一标识学生集合中的每一条记录，这样的字段就被称为key（关键字）。而在记录存储地址和它的关键字之间建立一个确定的对应关系h，使得每个关键字和一个唯一的存储位置相对应。在查找时，只需要根据这个对应关系h，就可以找到所需关键字及其对应的记录，这种查找方式就被称为哈希查找，关键字和存储位置的对应关系可以用函数表示为：
h(key)=存储地址
2构造哈希函数的方法
构造哈希函数的目标在于使哈希地址尽可能均匀地分布在连续的内存单元地址上，以减少发生冲突的可能性，同时使计算尽可能简单以达到尽可能高的时间效率，这里主要看看两个构造哈希函数的方法。
（1）直接地址法
直接地址法取关键字的某个线性函数值为哈希地址，即h(key)=key 或 h(key)=a*key+b
其中，a、b均为常数，这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。
（2）除留余数法
除留余数法采用取模运算（%）把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址，它也是最常用的构造哈希函数的方法，其形式为：h(key)=key%p
本方法的关键就在于选择合适的p，p如果选得不好，就可能会容易产生同义词。
PS：根据前辈们的经验，若哈希表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。
3解决哈希冲突的方法
（1）闭散列法
闭散列法时把所有的元素都存储在哈希表数组中，当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程则称为探测。上述方法可用如下公式表示为：
其中，h(key)为哈希函数，m为哈希表长度，di为递增的序列。根据di的不同，又可以分为几种探测方法：线性探测法、二次探测法以及双重散列法。
（2）开散列法
开散列法的常见形式是将所有关键字为同义词的记录存储在一个单链表中。我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}，我们用前面同样的12为除数，进行除留余数法，可得到如下图所示的结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。
该方法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。在.NET中，链表的各个元素分散于托管堆各处，也会给GC垃圾回收带来压力，影响程序的性能。
4小结
本篇介绍了哈希技术的基本概念及为何引入哈希技术，构造哈希函数的方法以及如何解决哈希冲突。下一篇，我们会了解.NET BCL中的HashTable、Dictionary与SortedDictionary（其内部是红黑树数据结构实现）。
5参考资料
程杰，《大话数据结构》
陈广，《数据结构（C#语言描述）》
段恩泽，《数据结构（C#语言版）》
许两会，《.NET集合类的研究-有序集合》
