unorderedmap的特性研究———胡明哲.docVIP

PAGE  哈尔滨师范大学 学　年　论　文 题 目 unordered_map的特性研究 学 生 胡明哲 指导教师 韩贤东 副教授 年 级 2010级 专 业 数字媒体技术 系 别 信息工程系 学 院 计算机科学与信息工程 哈尔滨师范大学 2013年06月 论 文 提 要 用于访问基于关键字查找数据的方式，C++标准库提供了很多查找方式，通常都是使用平衡树，查找时间具有对数复杂度来实现的。虽然通常的查找方式很好，但很多情况会使用哈希表来查询，但是游戏查询方式哈希表实现上有些困难，所以就引入了无序关联容器，更好的实现了查找方式。 PAGE 5 unordered_map的特性研究 胡明哲 摘 要：用于访问基于关键字查找数据的方式，C++标准库提供了std::set，std::map，std::multiset，std::multimap。这些通常都是使用平衡树，查找时间具有对数复杂度来实现的。这样通常是可行的，但在许多情况下，一个哈希表可以表现的更好，作为访问数据具有恒定的复杂性，平均性。最坏情况下的复杂度是线性的，但很少发生。但这些并不能完全的实现，所以，unordered_map的出现试图解决上述问题。 关键词：std::map 哈希表 unordered_map C++中的Map类 映射（Map），又称为字典（Dictionary），是由关键字（Key）及其对应的元素值（Value）所组成的元素单元（Element）的表单式集合。通常，对于Map而言，使用给定的Key，可以迅速地从单元集合中检索到相应的元素。因此，在需要对大量数据进行查找操作而查找的性能又占据重要地位的场合，Map无疑是一种较理想的容器。譬如，在MFC中，使用Map来实现Handle Maps（句柄映射），以及其他的一些内部数据结构。同时，MFC也提供了公共Map类。使用公共Map类，MFC程序员可以轻易地高效地根据自身的需求实现程序中自定义的映射。通常，当一个Map对象被删除时，或者，当其中的元素被移除时，关键字和元素值也将被完全删除。 （一）Map的典型操作 1、向Map中插入具有给定关键字的元素单元。 2、在Map中查找具有给定关键字的元素单元。 3、在Map中删除具有给定关键字的元素单元。 4、枚举Map中的所有元素单元。 （二）Map的工作原理 使用Map的最大优势是它的快速查找的优秀性能，而取得最优性能的关键在于尽量使得在检索周期内所需进行的元素检查次数达到最少。顺序查找的性能是最差的，因为如果使用顺序查找算法在包含n个元素单元的Map中查找某个元素，最坏情况下可能需要进行n次独立的比较运算。 二元查找的性能表现要稍好一些，可是，二元查找要求待查序列为有序排列，这会降低Map自身的操作灵活性。所谓的最佳算法应当是不论元素单元数目的多少，也不论元素是以什么顺序进行排列，查找过程都无需任何额外的比对操作，而能够仅仅通过简单的计算方法，就可以直接指向最终的相应元素的快速、高效算法。 在MFC的CMap及其相关的Map类中，只要对Map进行正确设置，Lookup函数通常能够一次到位的查找到任意元素，而很少需要进行两次或者三次以上的查找比对。在Map被创建之后，系统会为一个指向CAssoc结构体的指针数组的哈希表分配内存。MFC使用CAssoc结构体描述元素值和关键字的组合对。 无论何时，只要有一个元素值-关键字单元被加入到Map中，就会随之创建一个新的CAssoc结构体，并根据单元中的关键字的实际值来计算出相应的哈希 值。同时，拷贝一个指向CAssoc结构体的指针并将其插入到哈希表中索引值为i的位置中。 如果在哈希表中的索引值为i的位置已经容纳了一个CAssoc指针，那么MFC将建立一个单独的CAssoc结构体的链表（List）,链表中的第一个CAssoc结构体的地址被存储到哈希表中，而将第二个CAssoc结构体的地址存储到前一个CAssoc结构体的pNext域，以此类推。在该哈希表中，共有10个元素，其中5个元素地址分别唯一的存储，另外5个分别存储在长度为2和3的两个链表中。 调用一个Map的Lookup()函数时，MFC根据输入的关键字的实际值计算相应的哈希值，然后使用前面提到的公式将哈希值转换为索引值，并从哈希表中的相应位置检索CAssoc指针。 理想情况下，该位置只包含一个CAssoc指针，而非CAssoc指针链表。如果单一地址对应单一CAssoc指针，那么，元素单元将能够被一次查找到位，并直接读出；如果从哈希表中检索到的是CAssoc链表的指针头地址，则MFC顺序比对链表元素CAssoc结构所包含的关键字，直至查找到正确结果。但是，只要正确设置Map