文档介绍：2008级软件设计模式课程设计
（基于迭代器、适配器、策略模式的hashmap设计）
指导老师：蒋湘涛
小组成员:
刘应华(20083848)
王紫龙(20083855)
陈理平(20083837) 王 旭(20083854)
教师意见:
2011年7月4日
一、目的及简要介绍
大家都知道，C++为广大爱好者提供了诸如Iterator、list等容器供大家使用，大 大的方便了大家处理数据。这里，我们同样为大家提供一个满足STL要求的容 器来供大家使用，让大家在数据处理的过程中能更方便快捷。
C++标准对容器提出了许多需求，只有满足这些需求，才能算得上是STL容器。
基本hashmap（散列表）：STL中的最大的疏忽吗？在STL中，没有定义hashmap容器，这里 我们实现了。
散列表在平均情况下可以提供常量时间的插入、删除和查找。散列表并不是将元素有序地存 储，而是把各元素散列（hash）或映射至某个桶（bucket）o只要所存储的元素个数不比桶数大太 多，插入、删除和查找操作都能在常量时间内运行。
Hashmap也存储键/值对，它提供的操作与map几乎一样，这个hashmap实现使用链式散列 （也称开放散列），而且没有提供诸如再散列等高级操作。
二、 程序实现
Hashmap的访问操作：
标准要求为键比较和值比较对象提供访问方法：
Operator[]与STL中的map的原型相似。如果原来的hashmap中没有该键对应的值，则 会插入一个，它会调用被映射的元素的默认构造函数进行填充，并且反回这个值。
模板的分离编译：
在模板类的声明文件（）的最后添加一个include语句，将模板类的实 现文件包含进来，例如：
#include i',,
将模板类的实现类文件从项目中移除（）,但并不 从磁盘上移除，不改变其路径。使它不能显示的参与编译。
在声明main函数的文件中包含要使用的模板类的声明文件。
三、 设计模式
四、相关内容
1、Hashmap应当允许客户指定自己的散列函数和桶数，而针对特定工作负载制定散列 行为。另一方面，客户如果没有这种需求，或者没有能力来编写一个好的散列函数及选 择桶数，也应该能够不做任何定制地直接使用容器。一种解决方案是允许客户在hashmap 构造函数中提供散列函数和桶数，并为之提供默认值。另外，把散列函数和桶数包装在 一个散列类中也是一种合理的做法：
Hash。的实现要难一些，部分原因在于它必须应用于任何类型的键，它要把键映射至某 个mNumBuckets桶。此函数使用了除留余数法来完成散列，即键所对应的桶（号）是 键对桶数取余后得到的一个整数值。
遗憾的是，前面的方法无法应用于string,因为不同的string对象可能包含相同的string 值。因此相同的string值就可能散列到不同的桶中。这样…来，可以想到，专门针对string 提供DefaultHash类的一个部分特殊化。
2、 它支持3个基本操作：插入、删除、查找。
比较器：hashmap允许客户指定比较类型作为模板参数，并且能在构造函数中传递该类 的一个特定比较对象o Hashmap不会按键对元素排序，而是必须比较键的相等性。因此， ,比较对象只是用于检测是否试图向容器中插入重复键。
散列器：允许客户定义自己的类，以便构造此类对象传入构造函数，此时必须明确如何 在构造函数中指定该参数的类型。
散列模板参数：使用typedef定义：
键类型，值类型，比较类型，散列类型
3、 基本散列表结构通常包括固定数目桶，每个桶可以存储一个或多个元素。应当能够 基于，，个bucket-id在常量时间内访问桶。因此vector是对桶最为适合的容器。每个桶必 须存储一个元素列表，因此STLlist可以用作桶类型。
查找操作使用findElement帮助完成查找工作：findElement（）首先使用散列对象将键散列 至一个特定的桶。然后，在该桶中查找是否有元素的键与给定键匹配。所存储的元素是 键/值对，所以具体的比较会在元素第一个字段上进行。构造函数中指定的比较函数对象 就是用于完成这个比较。List需要完成线性查找来寻找匹配的元素，因此可以使用find（） 算法而不是•个显式的for循环。
Insert操作必须首先检查hashmap中是否已经存在此键的元素。如果没有，会把元素插 入到适当的桶中的list。需要说明，findElement（）会按引用返回散列到的那个桶，即在该 桶中并没有找到此键的元素。
4、将hashmap作为容器
有关type