散列技术与策略设计 ——原理，技术及实现 Tomsdinary Editor 前言 数据库德存储结构中必须考虑的一个核心问题是数据的插入，查找和检索的效率问题。索引技术结合散列技术可以成倍的提高数据库数据的查找和操作。此文将讨论一般散列技术的具体实现。但它并没有涉及到具体的数据库系统中的设计实现。此文的一大特色就在于C++高级语言特性和先进设计思想的使用——基于策略的设计。虽然在国际上此设计方式早已传开，但作为学习的个人能够实际运用上还是有成就感的。 散列技术 在基于比较的排序算法最好效率复杂度是 O(nlog n).。而针对已经排好序或某种特殊结构的查找算法的最好效率也只是O(log n)。是否存在一种既不需要对数列排序又可获得比O(log n)更好的查找效率的数据结构。 这就是散列技术用到的哈希表。散列技术是根据记录的查找键值，使用一个函数计算得到的函数值作为磁盘块的地址，对记录进行存储和访问的方法。 根据已有的文献显示，散列技术一般包括三个部分：一个哈希表，键值到存储位置的映射函数——哈希函数，以及处理哈希函数冲突的有效方法。 哈希表用于存放键值，它可以采用多种形式实现。比如，数组、链表、平衡树、红黑树或 B 树。不同的哈希表结构在效率和算法实现上都会有很大的差异。具体情况视设计者权衡而定。 哈希表只是用来存放键值，如何存放键值并没有规定。哈希函数就是用于计算键值到存放键值位置的。哈希表与其它基于比较存储最大的不同就在于键值位置的存放是由哈希函数决定的。 使用散列方法首先需要一个好得哈希函数，由于在设计哈希函数时不可能精确知道要存储的键值，因此要求散列函数在把键值转换成存储地址时满足：散列后的地址是均匀的，并且地址分布是均匀的。这不仅设计到哈希函数的设计也必须考虑一但哈希函数映射冲突如何解决。 其中映射冲突的解决构成了散列技术的第三个方面。通常处理冲突的方法有：开放定址法、再哈希法、链地址法和建立一个公共溢出区。 开放地址法是这样一种方法：当进行哈希函数映射后，发现遇到冲突；此时就开始从冲突位置开始向哈希表后搜索第一个没有被使用的位置作为映射后的位置直道搜索到映射位置的前一个位置。 再哈希法是这样一种方法：当进行哈希函数映射后，发现遇到冲突；于是对此键值使用另外一个其它机制设计的哈希函数进行再次映射；如果还是冲突就使用不同于以上哈希函数的新哈希函数进行映射直道找到一个不再冲突的位置停止。 链地址法是...
