hashmap是一个map集合吗（一文读懂map和hashmap的差异原理）

在平时的工作或面试中，经常需要考虑容器的选择问题，其中“map和hash_map的差异点”出现的概率最高。那么，我们从底层原理上看看具体都有哪些区别和联系。

目录

为了方便大家阅读文章，我们先介绍一下文章结构，大家可以直接跳到感兴趣的位置进行阅读。

1. 先简单介绍map和hash_map的底层原理，hash_map会从c 和java两个语言进行描述。
2. 通过表格形式对比介绍map和hash_map的特点。
3. 通过代码分析hash_map的原理。
4. 展示c 的hash_map存储数据的效果图
5. 文章总结，快速进行map和hash_map选型的方法。
6. 测试代码源码。

map底层结构原理

使用红黑树进行数据存储。

红黑树有四个原则，遵守这四个原则就可以构建红黑树：

　　（1）根节点为黑色；

　　（2）叶子结点为空值的黑色结点；

　　（3）红色结点的两个子节点必须为黑色；

　　（4）所有叶子结点到根结点的路径中，黑色结点个数要一样；

红黑树存储数据示意图

c 的hash_map/unordered_map底层结构原理

备注：unordered_map和hash_map基本一样，只是unordered_map已经加到C 11标准，而hash_map未加入在C 11标准中。

使用哈希表进行数据存储，主要涉及如下几点，

①哈希表：使用数组(bucket数组，实际使用的vector) 链表等结构一起构成了哈希表。

②哈希函数：哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。

哈希表中哈希函数的实现步骤大概如下：

✓生成 key 的哈希值（必须是整数），

✓再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值。

③map的key ：

常见种类有整数、浮点数、字符串、自定义对象。

不同种类的 key，哈希值的生成方式不一样，但目标是一致的

✓ 尽量让每个 key 的哈希值是唯一的

✓ 尽量让 key 的所有信息参与运算

④bucket数组的扩容机制

　　　　扩容时需要满足两个条件：存放新值的时候当前hash_map所有元素的个数大于等于阈值；存放新值的时候当前存放数据发生hash碰撞。

　　　　STL会默认指定初始桶大小为16，负载因子是0.75，因此阈值就是16*0.75 = 12，所以当新插入元素时，当前的元素个数超过12，并且发生了冲突，就会扩容hash桶。扩容的大小是之前的数组翻倍。

　　　　在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。 所以如果已经预知HashMap中元素的个数，那么预设元素的个数能够有效地提高hashmap的性能，例如最多有1000个元素，则创建时：new HashMap(2048)（1024是不够的，要考虑负载因子：1024*0.75 = 768）。

　　　　另外桶的大小为2的幂次方时，hash_map的效率最高。这是因为：正常的取index方法为hash%length，但是由于位运算比取余快，所以代码中实现为index = hash & (length - 1)，所以只有length大小为2的次幂时：hash % length == hash & (length - 1)。

c 哈希表存储数据示意图

　　思考：我们可以发现，这个桶数组的效率，高不高，完全取决于我们的哈希表的长度取得是否恰当，如果桶数组太短，那么链表就会累积的很长，如果桶数组太长，又会造成很大的空间浪费，所以，这也是哈希表的缺点不足之一，为了尽量避免，哈希表的长度，一般取为质数。

java的hash_map底层结构原理

在jdk8中，使用链表和红黑树两种方式对接哈希表的桶，我们都知道，链表构建很简单，而红黑树，一个结点就会多4个区域，也存在空间的浪费，但是查询效率会高很多，所以为了达到最好的效果，设置了一个阈值控制桶下的结点数，如果超过了这个值，那么就会转为为红黑树存放。

java哈希表存储数据示意图

map和hash_map的特点

(1)共同点：

• 都是map的实现类，都是键值对集合；
• 里边的元素都跟添加顺序无关；

(2)差异点：

类型	特点	优点	缺点	应用场景
map	底层是用红黑树实现的，查找时间复杂度是O(log(n))； 因使用红黑树实现，所以数据是有序存储的，因此map的key需要重载operator<； 键对象在集合中是唯一的，可以通过键来直接查找值；	有序存储，元素可以自动按照键值排序。 内存占用比hash_map少。	l 查找速度比hash_map慢，map的查找速度是log(n)级别。	适用于有顺序要求的问题，使用map会更高效一些； 如果对内存使用特别严格，需要程序尽可能少消耗内存，那么应该使用map，因为hash_map占用内存较多。
hash_map	底层是用hash表存储的，查询时间复杂度是O(1)； 基于hash无序存储的，因此需要重载operator==； 使用哈希算法对键去重复，效率高，但无序； HashMap是Map接口的主要实现类；	查找的时间复杂度几乎是常数时间O(1)。 备注：hash_map的查找不一定是o(1)，在有哈希冲突进行桶内数据查找时，需要遍历链表。	无自动排序功能； 占用比较多的内存； 扩容会自动扩大使用内存：	如果在元素达到一定数量级时同时要考虑效率，但是不考虑内存消耗，此时应该使用hash_map。

通过代码分析hash_map的原理

1.输入数据：

我们顺序输入以下增序数据进行测试，{5,"5"},{10,"10"},{15,"15"},{20,"20"},{25,"25"},{30,"30"},{35,"35"},{40,"40"},{45,"45"},{50,"50"},{55,"55"},{60,"60"},{65,"65"},{70,"70"},{75,"75"},{80,"80"},{85,"85"},{90,"90"},{95,"95"},{100,"100 "},{101,"101 "},{102,"102 "},{103,"103 "},{104,"104 "},{105,"105 "},{106,"106 "},{107,"107 "},{108,"108 "},{109,"109 "},{200,"200 "}。

2.根据输出日志分析原理：

数据结构内部存储数据的顺序并不是完全按照输入顺序或数值大小进行排序的；

哈希表中单链表存储的数据，先输入的数据在链表的最后面，后输入的数据在链表的最前面；

重置bucket大小后(重置的bucket大小大于原bucket大小)，哈表表要重建表格，会打乱桶(vector)和链表(单链表)节点的存储和位置定位。扩充后的bucket大小，扩容的大小是之前的数组翻倍(直到能涵盖住重置大小的数值)。

重置bucket时重建表格的原理：

hash_map示意图

因为我使用的hash_map演示工具暂时只能设置12个桶，所以下面展示的示意图和上面的测试代码的实际效果不一样。但是大家一样可以通过这个示意图看出来哈希表的特点：

数据结构内部存储数据的顺序并不是完全按照输入顺序或数值大小进行排序的；

哈希表中单链表存储的数据，先输入的数据在链表的最后面，后输入的数据在链表的最前面；

hash_map示意图

总结

需要无序容器，快速查找删除，不担心略高的内存时用unordered_map；

有序容器稳定查找删除效率，内存很在意时候用map。

示例代码

#include<iostream>

#include <unordered_map>

using namespace std;

void fun_unordered_map_test()

{

//构造数据

unordered_map<int, string> hash_map_obj = {

{5,"5"},{10,"10"},{15,"15"},{20,"20"},{25,"25"},{30,"30"},{35,"35"},

{40,"40"},{45,"45"},{50,"50"},{55,"55"},{60,"60"},{65,"65"},{70,"70"},

{75,"75"},{80,"80"},{85,"85"},{90,"90"},{95,"95"},{100,"100 "},

{101,"101 "},{102,"102 "},{103,"103 "},{104,"104 "},{105,"105 "},

{106,"106 "},{107,"107 "},{108,"108 "},{109,"109 "},{200,"200 "}

};

//打印数据

cout << endl;

size_t bucket_count = hash_map_obj.bucket_count();

cout << " unordered_map bucket的总数bucket_count:" << bucket_count << " 桶数量最大值max_bucket_count:" << hash_map_obj.max_bucket_count() << endl;

cout << " unordered_map 实际元素个数:" << hash_map_obj.size() << " 遍历迭代器打印存储的数据:" << endl;

unordered_map<int, string>::iterator iter_print = hash_map_obj.begin();

for (; iter_print != hash_map_obj.end(); iter_print)

{

cout << " 键：" << (*iter_print).first << " 值：'" << (*iter_print).second << "' is in bucket #" << hash_map_obj.bucket((*iter_print).first) << endl;

}

//bucket操作

cout << endl;

cout << " unordered_map 按照bucket打印存储的数据:" << endl;

//bucket_size() 返回第i个bucket桶子里有几个元素，注意：函数不会判断n是否在count范围内

for (size_t i = 0; i < bucket_count; i)

{

cout << " bucket #" << i << "'s size:" << hash_map_obj.bucket_size(i) << " contains: ";

//输出每个list节点

for (auto it = hash_map_obj.begin(i); it != hash_map_obj.end(i); it)

{

cout << " [键：" << it->first << " 值：'" << it->second << "'] ";

}

cout << endl;

}

cout << endl;

cout << " unordered_map 调整bucket_size为100" << endl;

hash_map_obj.reserve(100);//调整bucket_size为100

cout << " unordered_map bucket_count:" << hash_map_obj.bucket_count() << " max_bucket_count:" << hash_map_obj.max_bucket_count() << endl;

iter_print = hash_map_obj.begin();

for (; iter_print != hash_map_obj.end(); iter_print)

{

cout << " 键：" << (*iter_print).first << " 值：'" << (*iter_print).second << "' is in bucket #" << hash_map_obj.bucket((*iter_print).first) << endl;

}

}

int main()

{

fun_unordered_map_test();

return 0;

}

---

原创不易，欢迎点赞、收藏、关注！

,