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