其意）、打印任务处理等。然而在现实生活很难找到和Stack近似的范例，但它在各种应用程序中却是一种非常重要的数据结构。
设想一下我们用以编程的计算机语言，例如：C#。当执行C#程序时，CLR（公共语言运行时）将调用Stack以跟踪功能模块（译注：这里原文为function，我理解作者的含义不仅仅代表函数，事实上很多编译器都会调用堆栈以确定其地址）的执行情况。每当调用一个功能模块，相关信息就会压入堆栈。调用结束则弹出堆栈。堆栈顶端数据为当前调用功能的信息。（如要查看功能调用堆栈的执行情况，可以在Visual Studio.Net下创建一个项目，设置断点（breakpoint），在执行调试。当执行到断点时，会在调试窗口（Debug/Windows/Call Stack）下显示堆栈信息。
序数索引的限制
我们在第一部分中讲到数组的特点是同种类型数据的集合，并通过序数进行索引。即：访问第i个元素的时间为定值。（请记住此种定量时间被标记为O(1)。）
也许我们并没有意识到，其实我们对有序数据总是―情有独钟‖。例如员工数据库。每个员工以社保号（social security number）为其唯一标识。社保号的格式为DDD-DD-DDDD（D的范围为数字0——9）。如果我们有一个随机排列存储所有员工信息的数组，要查找社保号为111-22-3333的员工，可能会遍历数组的所有元素——即执行O(n）次操作。更好的办法是根据社保号进行排序，可将其查找时间缩减为O(log n)。
理想状态下，我们更愿意执行O(1)次时间就能查找到某员工的信息。一种方案是建立一个巨型的数组，以实际的社保号值为其入口。这样数组的起止点为000-00-0000到999-99-9999，如下图所示：
图七：存储所有9位数数字的巨型数组
如图所示，每个员工的信息都包括姓名、电话、薪水等，并以其社保号为索引。在这种方式下，访问任意一个员工信息的时间均为定值。这种方案的缺点就是空间极度的浪费——共有109，即10亿个不同的社保号。如果公司只有1000名员工，那么这个数组只利用了0.0001%的空间。（换个角度来看，如果你要让这个数组充分利用，也许你的公司不得不雇佣全世界人口的六分之一。）
用哈希函数压缩序数索引
显而易见，创建10亿个元素数组来存储1000名员工的信息是无法接受的。然而我们又迫切需要提高数据访问速度以达到一个常量时间。一种选择是使用员工社保号的最后四位来减少社保号的跨度。这样一来，数组的跨度只需要从0000到9999。图八显示了压缩后的数组。
图八：压缩后的数组
此方案既保证了访问耗时为常量值，又充分利用了存储空间。选择社保号的后四位是随机的，我们也可以任意的使用中间四位，或者选择第1、3、8、9位。
在数学上将这种9位数转换为4位数成为哈希转换（hashing）。哈希转换可以将一个索引器空间（indexers space）转换为哈希表（hash table）。
哈希函数实现哈希转换。以社保号的例子来说，哈希函数H()表示为： H(x) = x 的后四位
哈希函数的输入可以是任意的九位社保号，而结果则是社保号的后四位数字。数学术语中，这种将九位数转换为四位数的方法称为哈希元素映射，如图九所示：
图九：哈希函数图示
图九阐明了在哈希函数中会出现的一种行为——冲突（collisions）。即我们将一个相对大的集合的元素映射到相对小的集中时时，可能会出现相同的值。例如社保号中所有后四位为0000的均被映射为0000。那么000-99-0000，113-14-0000，933-66-0000，还有其他的很多都将是0000。
看看之前的例子，如果我们要添加一个社保号为123-00-0191的新员工，会发生什么情况？显然试图添加该员工会发生冲突，因为在0191位置上已经存在一个员工。
数学标注：哈希函数在数学术语上更多地被描述为f：A->B。其中|A|>|B|，函数f不是一一映射关系，所以之间会有冲突。
显然冲突的发生会产生一些问题。在下一节，我们会看看哈希函数与冲突发生之间的关系，然后简单地犯下处理冲突的几种机制。接下来，我们会将注意力放在System.Collection.Hashtable
类，并提供一个哈希表的实现。我们会了解有关Hashtable类的哈希函数，冲突解决机制，以及一些使用Hashtable的例子。 避免和解决冲突
当我们添加数据到哈希表中，冲突是导致整个操作被破坏的一个因素。如果没有冲突，则插入元素操作成功，如果发生了冲突，就需要判断发生的原因。由于冲突产生提高了代价，我们的目标就是要尽可能将冲突压至最低。
哈希函数中冲突发生的频率与传递到哈希函数中的数据分布有关。在我们的例子中，假定社保号是随机分配的，那么使用最后四位数字是一个不错的选择。但如果社保号是以员工的出生年份或出生地址来分配，因为员工的出生年份和地址显然都不是均匀分配的，那么选用后四位数就会因为大量的重复而导致更大的冲突。
注：对于哈希函数值的分析需要具备一定的统计学知识，这超出了本文讨论的范围。必要地，我们可以使用K维（k slots）的哈希表来保证避免冲突，它可以将一个随机值从哈希函数的域中映射到任意一个特定元素，并限定在1/k的范围内。（如果这让你更加的糊涂，千万别担心！） 我们将选择合适的哈希函数的方法成为冲突避免机制（collision avoidance），已有许多研究设计这一领域，因为哈希函数的选择直接影响了哈希表的整体性能。在下一节，我们会介绍在.Net Framework的Hashtable类中对哈希函数的使用。
有很多方法处理冲突问题。最直接的方法，我们称为―冲突解决机制‖（collision resolution），是将要插入到哈希表中的对象放到另外一块空间中，因为实际的空间已经被占用了。其中一种最简单的方法称为―线性挖掘‖（linear probing），实现步骤如下： 1． 当要插入一个新的元素时，用哈希函数在哈希表中定位；
2． 检查表中该位置是否已经存在元素，如果该位置内容为空，则插入并返回，否则转向步骤3。 3． 如果该地址为i，则检查i+1是否为空，如果已被占用，则检查i+2，依此类推，知道找到一个内容为空的位置。
例如：如果我们要将五个员工的信息插入到哈希表中：Alice(333-33-1234)，Bob(444-44-1234), Cal (555-55-1237), Danny (000-00-1235), and Edward (111-00-1235)。当添加完信息后，如图十所示：
图十：有相似社保号的五位员工
Alice的社保号被―哈希（这里做动词用，译注）‖为1234，因此存放位置为1234。接下来来，Bob的社保号也被―哈希‖为1234，但由于位置1234处已经存在Alice的信息，所以Bob的信息就被放到下一个位置——1235。之后，添加Cal，哈希值为1237，1237位置为空，所以Cal就放到1237处。下一个是Danny，哈希值为1235。1235已被占用，则检查1236位置是否为空。既然为空，Danny就被放到那儿。最后，添加Edward的信息。同样他的哈希好为1235。1235已被占用，检查1236，也被占用了，再检查1237，直到检查到1238时，该位置为空，于是Edward被放到了1238位置。
搜索哈希表时，冲突仍然存在。例如，如上所示的哈希表，我们要访问Edward的信息。因此我们将Edward的社保号111-00-1235哈希为1235，并开始搜索。然而我们在1235位置找到的是Bob，而非Edward。所以我们再搜索1236，找到的却是Danny。我们的线性搜索继续查找知道找到Edward或找到内容为空的位置。结果我们可能会得出结果是社保号为111-00-1235的员工并不存在。
线性挖掘虽然简单，但并是解决冲突的好的策略，因为它会导致同类聚合（clustering）。如果我们要添加10个员工，他们的社保号后四位均为3344。那么有10个连续空间，从3344到3353均被占用。查找这10个员工中的任一员工都要搜索这一簇位置空间。而且，添加任何一个哈希值在3344到3353范围内的员工都将增加这一簇空间的长度。要快速查询，我们应该让数据均匀分布，而不是集中某几个地方形成一簇。