[TOC] ### hah_map ***** hash_map 不是标准的。笔者写该文档时本来想尝试些一个 hash_map 例程，但发现自己用 Qt + MSVC2010 编译器出现了编译错误。网上原因好像说是 STL 加入标准C++之时，hash_map系列当时还没有完全实现，所以很多平台上虽然安装了 g++ 编译器，但不一定有 hash_map 的实现。所以如果有平台移植的内容，尽量少用 hash_map。 ### map ***** #### map 容器属性 * 关联性： 关联容器中的元素的参考地址指的是其 Key 值，而不是他们在容器中的绝对地址； * 有序性： 容器中的元素一直按照排序方式严格排序，所有插入元素都按照该顺序排列； 映射： 每个元素中，一个 Key 值与一个映射值相关。Key 值是用来标识其主要内容是映射值的元素； * 唯一 Key 值： 容器中不存在同时拥有相同 Key 值的两个元素； * 分配感知 (Allocator-aware)： map 容器使用分配器对象动态处理其存储需求。 ` ` ### unordered_map ***** unordered\_map 是一种关联容器，用于存储由**关键值 (Key Value，以下称为Key 值)**和**映射值 (Mapped Value，以下称为映射值)**组成的元素，并且允许根据其 Key 值快速检索各个元素。 `unordered_map`(等价于`hash_map`)和`map`类似，都是存储的`key-value`的值，可以通过`key`快速索引到`value`。 不同的是`unordered_map`不会根据`key`的大小进行排序， unordered\_map 内部实现了一个 Hash 表，所以其元素的排列顺序是杂乱无序的。 ` ` #### 容器属性 * 关联性 关联容器中的元素的参考地址指的是其 Key 值，而不是他们在容器中的绝对地址； * 无序性 无序容器使用 Hash 表来组织元素，这些 Hash 表允许无序容器通过 Key 值快速访问元素； * 映射 每个元素将一个 Key 值与映射值关联起来，Key 值用于标识其主要内容是映射值的元素； * 唯一关键值 容器中不存在同时拥有相同 Key 值的两个元素； * 分配器感知 map 容器使用分配器对象动态处理其存储需求。 ` ` ### **unordered_map和map的区别在哪里** ***** `hash_map`，`unordered_map`本质是一样的，只不过`unordered_map`被纳入了C++标准库标准。 1. map 内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。 2. unordered_map(hash_map) 基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。 3. 用法的区别就是，map的key需要定义operator<。 而unordered_map需要定义hash_value函数并且重载operator==。对于内置类型，如string，这些都不用操心。对于自定义的类型做key，就需要自己重载operator==或者hash_value()了。 ` ` ### 优缺点 ***** #### map： * 优点： 有序性：这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作； 红黑树，内部实现一个红黑书使得 map 的很多操作在 log n 的时间复杂度下就可以实现，因此效率非常的高； * 缺点： 空间占用率高，因为 map 内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，子节点以及红/黑性质，使得每一个节点都占用大量的空间； 适用于具有顺序要求的问题； #### hash_map： * 优点： hash_map 查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别（但不能说一定比 map 的 log n 级别快，因为 hash 函数本身也有耗时）； * 缺点： 空间占用多，如果对内存使用很严格，需要认真考虑是否使用 hash_map ；特别是当 hash_map 对象特别多时，更加难以控制； 适用于对效率要求较高的环境； #### unordered_map： * 优点： 内部实现了 Hash 表，所以查找速度很快； * 缺点： Hash 表的建立比较比较费时； 适用于查找问题； ### **红黑树和hash表的时间复杂度** ***** `红黑树`保证了一个稳定的动态操作时间，查询、插入、删除都是O(logN)，最坏和平均都是. `哈希表`的查询时间虽然是O(1)，但是并不是`unordered_map`查询时间一定比`map`短，因为实际情况中还要考虑到数据量，而且`unordered_map`的hash函数的构造速度也没那么快.所以不能一概而论，应该具体情况具体分析。 ` `