Hash技术策略设计与实现

散列技术与策略设计——原理，技术及实现TomsdinaryEditor前言数据库德存储结构中必须考虑的一个核心问题是数据的插入，查找和检索的效率问题。索引技术结合散列技术可以成倍的提高数据库数据的查找和操作。此文将讨论一般散列技术的具体实现。但它并没有涉及到具体的数据库系统中的设计实现。此文的一大特色就在于C++高级语言特性和先进设计思想的使用——基于策略的设计。虽然在国际上此设计方式早已传开，但作为学习的个人能够实际运用上还是有成就感的。散列技术在基于比较的排序算法最好效率复杂度是O(nlogn).。而针对已经排好序或某种特殊结构的查找算法的最好效率也只是O(logn)。是否存在一种既不需要对数列排序又可获得比O(logn)更好的查找效率的数据结构。这就是散列技术用到的哈希表。散列技术是根据记录的查找键值，使用一个函数计算得到的函数值作为磁盘块的地址，对记录进行存储和访问的方法。根据已有的文献显示，散列技术一般包括三个部分：一个哈希表，键值到存储位置的映射函数——哈希函数，以及处理哈希函数冲突的有效方法。哈希表用于存放键值，它可以采用多种形式实现。比如，数组、链表、平衡树、红黑树或B树。不同的哈希表结构在效率和算法实现上都会有很大的差异。具体情况视设计者权衡而定。哈希表只是用来存放键值，如何存放键值并没有规定。哈希函数就是用于计算键值到存放键值位置的。哈希表与其它基于比较存储最大的不同就在于键值位置的存放是由哈希函数决定的。使用散列方法首先需要一个好得哈希函数，由于在设计哈希函数时不可能精确知道要存储的键值，因此要求散列函数在把键值转换成存储地址时满足：散列后的地址是均匀的，并且地址分布是均匀的。这不仅设计到哈希函数的设计也必须考虑一但哈希函数映射冲突如何解决。其中映射冲突的解决构成了散列技术的第三个方面。通常处理冲突的方法有：开放定址法、再哈希法、链地址法和建立一个公共溢出区。开放地址法是这样一种方法：当进行哈希函数映射后，发现遇到冲突；此时就开始从冲突位置开始向哈希表后搜索第一个没有被使用的位置作为映射后的位置直道搜索到映射位置的前一个位置。再哈希法是这样一种方法：当进行哈希函数映射后，发现遇到冲突；于是对此键值使用另外一个其它机制设计的哈希函数进行再次映射；如果还是冲突就使用不同于以上哈希函数的新哈希函数进行映射直道找到一个不再冲突的位置停止。链地址法是这样一种方法：当进行哈希函数映射后，不管是否发生冲突都在相应位置后添加一个属于这个位置的节点元素。这个节点称之为桶。于是被映射到相同地址的键值构成了一个链表。当发生冲突时就在链表中查找对应键值就可以了。建立一个公共溢出区:开辟一个新内存区块用于存放产生哈希冲突的数据。不管哈希表采用何种数据结构，冲突避免采用何种处理办法；一个好的散列方法必然有一个好的哈希函数。一般的哈希函数构造方式有：直接定址法、数字分析法、平方取中法、折叠法、保留余数法和随机数法。在这里介绍下文将要用到的保留余数法：如果键值是一些整数并且哈希表大小为一个质数，那么我们可以用一个简单的方法来确定键值的位置。让键值和哈希表大小整除，取其余数作为键值的存放位置。而其他方式都是根据不同方式对键值进行处理从而获得哈希表中的位置。策略设计设计的选择：程序设计技术发展到当前设计手法也在不断发展。从面向过程的范型到泛型程序设计。在这里将要讨论的设计选择是面向对象的。而从面向过程，基于对象，面向对象和泛型程序设计这些泛型都支持的当今只有一种语言C++。所以一下的讨论都将带有浓厚的C++色彩。在面向对象领域里有一颗神奇的“银弹”——继承和多态。但经过面向对象方法论长期的发展我们听到的教诲永远是不要使用继承而多使用组合；即使继承那就针对接口编程的。还有程序设计的关键是针对抽象设计而不是实现设计的观念在每一个面向对象分析和设计人员心目中根深蒂固。继承与多态的确是好东西，但并不是“银弹”。而一些不成熟设计者对它们的滥用使得系统越来越复杂，越来越不好维护和管理。后来才发现，模块之间耦合太密而内部聚合太松。对继承和多态的依赖让设计变得越来越难。于是在综合过去系统好的设计方案中，人们发现了很多经典的不断在各种稳健系统中出现的设计权衡——设计模式。于是继承，多态，接口这些概念被重新审视，在遵循一些好的设计模式下设计有了更多好的选择，这对于一个普通开发者而言无疑是一个福音。面向对象系统中鼓吹一种称为复用的精神。那下面看看为了复用我们有哪些设计选择。第一个很自然的设计倾向就是将全部功能集成在一个类实现中。对这样一个富接口的重大缺点就是不利于服用这个类其它可以复用的功能，同时这样一个全功能的类是笨拙的且不利于和系统其它部分交互。第二个设计方式就是多继承了。我们首先设计些具有小功能的类，然后通过多继承把这些功能复用到一个子类中。这样设计的弊病就是多继承的复杂性以及这些内模块耦合得太紧。如果一个基类发生变化，所有继承自它的类都必须重新编译或者重新设计。第三个设计方式是泛型编程。运用模板技术设计各种容器复用各种数据结构。写于数据类型无关代码。这是一种静态多态。其最大的不足就是与面向对象设计的关系不是那么紧密和自然。面向对象中的接口多态是动态的，而模板中的类型签名是静态多态。在以上三种方案中，主要讨论了他们的缺点，当然优点也是喜人的。但作为寻求更好设计的目标，这些设计都显得不足。那么综合运用这三种设计手法怎么样呢？这就是基于策略的设计了。策略设计：策略设计就是基于策略的设计。策略实际上是一个一个完成特定功能的小的类模板。它们关注于一个特定功能的实现，它们可以作为小的功能部件集成到更大的类中。而基于这些策略而设计出来的类的功能实际上比这些小类功能的总和还要强大。更为可观的是这个基于策略设计的类可以根据具体应用环境使用不同策略来构造自身。这不同于动态多态的行为，动态多态是根据运行时创建不同对象来对同一动作作出不同反应，而这种基于策略设计的类是通过编译时模板具体化实现的。这其中有一个好处就是模板在编译时只做语法检查，只生成具体会用到的函数方法。同时也有个不好的地方就是针对不同类型会有不同类型版本的模板实现，这增加了最终可执行代码的大小。但作为具高伸缩性和复用性的设计方案，它结合了面向对象设计方法和泛型技术。策略设计主要通过模板和多继承实现。策略设计在散列技术上的应用以下讨论在实现散列过程中如何应用策略的设计方法。在本例中我分别写了两种解决冲突问题的方法，冲突问题的方法可以用策略表示。一种是线性地址开放策略，另一种是溢出链表策略。由于各种用户对关键字要求有各自需要的类型，同样哈希函数会因不同的键值类型不同而不同。于是将键值类型参数化，将哈希函数仿函数化，让用户有充分的选择自由。提供策略模板让用户根据喜爱决定解决冲突问题的不是更人性化吗。如果用户不满意可以开发自己的策略模板来。哈希表ADT。由于所有实现都用C++写成，所有哈希表的抽象数据类型也用她表示，同时采用了策略设计，所以它的模板描述如下：//集合哈希表templatetypenameKey,//键值类型typenameFunc,//键值类型到位置的映射仿函数类型templatetypename,typenameclassManagerPolicy//冲突避免策略classHash_Set:protectedManagerPolicyKey,Func{public:explicitHash_Set(intsize);//初始化散列表大小intCount()const;//统计已经散列的元素个数voidClear();//清空散列表boolInsert(constKey&k);//插入关键值boolLookup(constKey&k);//找特定关键值是否已经映射protected://不可访问函数Hash_Set(constHash_Set&other);Hash_Set&operator=(constHash_Set&rbs);};从这个类模板可以看到，我设计的哈希表提供五个操作：初始化哈希表大小，统计已经映射的元素个数，清空哈希表，插入新关键值，和查找是否存在给定的关键字。只要通过小小的改动，很容易将这个哈希表改成键/值对的字典结构。为了说明问题就不把它搞复杂了。这个模板定义也说明了，键值类型可以任意，哈希函数可以任意，冲突解决方案可以任意。事实上，这个模板类就是用基于策略的思想设计出来的。现在的问题就是策略的设计和哈希表的管理了。这些在本实例中都将由一个管理策略来实现。模板签名的第三个模板类型和这个哈希类继承这个管理策略这个事实就说明了。同时看到由于不同的解决冲突方法和哈希表结构是密切相关的。也就是说冲突解决策略是和哈希表结构策略一起设计与同一个策略的。这就是为什么不把哈希表的表示和冲突解决方案分离的原因——纯粹是为了使实现简单，突出我要说明的问题。管理策略实现尽管不同，但它们提供的接口是一致的。这是由模板类型签名机制决定的了。//开放定址策略templatetypenameKey,//键值类型typenameFunc//必须是仿函数类classOpenAddressPolicy{public:OpenAddressPolicy();~OpenAddressPolicy();voidInit(intsize);//初始化散列表大小voidClear();//清空散列表intCount()const;//计算当前散列表中元素个数boolInsert(constKey&k);//插入键值boolLookup(constKey&k);//查找是否存在键值private://用于开放定址策略的数据结构Key*m_pData;//一个存放键值的数组bool*m_bUsage;//一个标志对应位置是否使用的数组intm_nSize;//散列表大小};//溢出链策略templatetypenameKey,//键值类型typenameFunc//必须是仿函数类classOverflowChainPolicy{protected://内部数据结构structNode//桶{Keym_k;//键值Node*m_next;//下一个桶};structChain//链{Chain(booluse=false,Node*p=NULL):m_bUsage(use),m_list(p){}boolm_bUsage;//该位是否使用标志Node*m_list;//桶链};voidDestroyAllNode();//删除所有桶节点public:OverflowChainPolicy();~OverflowChainPolicy();voidInit(intsize);//初始化散列表大小voidClear();//清空散列表intCount()const;//计算当前散列表中元素个数boolInsert(constKey&k);//插入键值boolLookup(constKey&k);//查找是否存在键值private://用于溢出链策略的数据结构Chain*m_pData;//链intm_nSize;//散列表大小};好了，我们有了散列类，及其两个策略类。现在的问题是如何设计哈希函数的问题了。由于实例采用的是C++机制，我采用的是仿函数机制。也就是重载了函数运算符的类。其一般形式如下：templatetypenameKeyclassf{public:intoperator()(Keyk){return//;}};但是用户具体采用何种方式实现就留给用户决定了。下面看看如何使用这个基于策略思想实现的散列技术了。如果我们要101个元素大小的哈希表，采用整除留余数映射机制和使用开发地址策略。我们可以如下声明仿函数和散列对象。templatetypenameKey,intSIZEclassf{public:intoperator()(Keyk){returnk%SIZE;}};Hash_Setint,fint,101,OpenAddressPolicyhs(101);如果改用溢