这个文章是对前面 小王职场记 谈谈你的STL理解(1) 修正,仅仅通过测试结果来得出判断和结论 距离 实际还有很大的差距并且还有误区
纳秒基本
unordered_map是基于hash_table实现
Hash表,在数据无冲突 的情况下,插入、查询和删除都可以认为是O(1)的时间复杂度,最完美 常数时间,操作 https://en.wikipedia.org/wiki/Hash_table
链地址法冲突的缺点
意思是说:vector扩容期间,回阻塞业务
Redis 通过增量式扩容解决了这个扩容期间业务无法访问的缺点</u>
Redis默认初始化值为4
渐进式哈希`的精髓在于:数据的迁移不是一次性完成的,而是可以通过dictRehash()这个函数分步规划的
在迁移的过程中,数据是在新表还是旧表中并不是一个非常急迫的需求,迁移的过程并不会丢失数据,在旧表中找不到再到新表中寻找就是了(一般情况)
遇到内存不足,然后ha切换 也会有问题。
即使扩容以后他们的位置也不会变化,性能不会发生变化 .
意思是说 :根据 **负载因子** (总键值对数 / 箱子个数) 来调整扩容也无法解决哈希函数设计不*合理的问题
旁白: 负载因子超过某个阈值时,出于链表性能的考虑,会进行Resize的操作
Java :openjdk/jdk/src/share/classes/java/util/HashMap.java
jdk 8 对于链表长度超过 8 的链表将转储为红黑树
image.png
> Redis:经过严格测试,表现良好的默认哈希函数,避免了链表过长的问题,解决了这个缺点
有两个字典,分别存有 100 条数据和 10000 条数据,如果用一个不存在的 key 去查找数据,在哪个字典中速度更快? 这个你不好回答了
能够保证二叉树的插入和查找操作一直都是O(log(n))的时间复杂度(无最坏情况)
The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Algorithm | Average | Worst case |
---|---|---|
Space | O(n) | O(n) |
Search | O(log n) | O(log n) |
Insert | O(log n) | O(log n) |
Delete | O(log n) | O(log n) |
旁白:理解时间复杂度O(log n)
如果有1000个记录,最多查找10次,1,000,000个记录,最多查找20次
image
https://en.wikipedia.org/wiki/Big_O_notation
image.png
旁白:rb tree从众多平衡tree胜出,是因为 功能、性能、空间开销的折中结果,最优。 红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长 )
适合频繁更新,删除等操作。
image
为了解决这些限制,研究人员已经开发了替代结构,例如跳过列表[4],以及可以更加适应并发性的红黑树变种 无锁链接列表和跳过列表
代码: https://github.com/wangcy6/weekly/blob/master/reading-notes/unix_nework/code/unordered_map.cpp
map insert time: 1421.571000 (1.4秒)
map find time: 557.019000 (0.5秒)
map erase time: 662.265000 (0.6秒,删除需要旋转,因此耗时)
unordered_map insert time: 709.372000 (0.7秒)
unordered_map find time: 258.488000 (0.2秒)
unordered_map erase time: 318.419000 (0.3秒)
map insert time: 1133.790000 (1.1秒)
map find time: 770.932000 (0.77增多)
map erase time: 888.817000 (0.88增多)
unordered_map insert time: 357.746000 (0.35秒)
unordered_map find time: 291.077000 (0.29秒 没有发生明显变化)
unordered_map erase time: 331.654000 (0.33秒 没有发生明显变化)
map insert time: 12667.974000 (1.1秒-12秒)
map find time: 8834.936000 (0.7秒-8秒)
map erase time: 9612.398000 (0.88秒-9秒)
unordered_map insert time: 4051.746000 (0.35秒-4秒)
unordered_map find time: 2574.762000 (0.29-2.5秒)
unordered_map erase time: 3100.294000(0.33-3秒)
map insert time: 21340.048000 (1.4秒-21秒)
map find time: 6861.261000 (0.5秒-6.8秒)
map erase time: 7965.711000 (0.6秒-7.9秒)
unordered_map insert time: 10610.533000 (0.7秒-10.6秒)
unordered_map find time: 3981.091000 (0.2秒-3.9秒)
unordered_map erase time: 4738.190000 (0.3秒4.7秒)
说明: 虽然测试unordered_map性能都好于map .并且没有测试 扩容 切换等情况,因为里面算法不是很清楚。 上面的测试根本没有找到结果
redis测试500w(毫秒级别)
[root@bj02-im-video05 bin]# ./redis-benchmark -r 5000000 -n 5000000 hset myhash
====== hset myhash ======
5000000 requests completed in 28.24 seconds
50 parallel clients
3 bytes payload
keep alive: 1
100.00% <= 1 milliseconds
100.00% <= 2 milliseconds
100.00% <= 2 milliseconds
177028.75 requests per second
纳秒基本
image.png
gcc4.9.3的哈希算法移植到 ServerFrame::HashMap
image.png
在看这个张图 stl::unordered_map 解释了很多问题
冲突