递归火山软件开发平台

标题: 请问无序哈希集是什么意思？ [打印本页]

作者: az3346 时间: 2023-3-6 20:47
标题: 请问无序哈希集是什么意思？
如题，请问无序哈希集对象和普通的哈希集对象有什么区别呢？

作者: 小蜗牛 时间: 2023-3-6 21:24
有序:顺序插入:1,2,3,4,5,6,7,8,9 更快
无序:随机插入:5,66,51,99,8,3 更快

其它的我没测试,大概可能是这样吧..具体以自己测试为准

作者: 创世魂 时间: 2023-3-6 22:11
就是没有顺序吧

作者: 龙纹 时间: 2023-3-6 22:54
本帖最后由龙纹于 2023-3-7 12:41 编辑

官方库的普通哈希表我认为是命名不当，其封装的是C++标准库中的map，跟哈希没什么关系，底层实现是红黑树，key和value是一对一的关系，插入一个值时内部会根据key进行排序，所以是有序的，插入、删除、搜索的时间复杂度是O(log(n))。
无序哈希表则是把一个key通过hash(哈希)操作变为另一个值，通过这个值能直接找到对应的value，所以在一般情况下，插入、删除、搜索是O(1)，比map快，但在某些情况下达不到这个效率。
简单的讲，在数据量不大的时候，两者皆可，需要有序的情况下使用map，数据量非常大就根据实际场景决定。
（看错字了，这里解释的是哈希表...哈希集看下面 @Xelloss0618 的解释吧）

作者: Xelloss0618 时间: 2023-3-7 11:35
上面龙纹把火山里的哈希表当成哈希集了，火山里的哈希集是 std::set，无序哈希集是 std::unordered_set。
诚如龙纹所说，只有 std::unordered_set 是跟哈希有关的，std::set 实际是红黑树。

先说哈希集（std::set），相比数组，它有去重和排序功能。
首先是它的元素值是唯一的，不会重复插入同样的值。
其次，它插入值的时候，会通过比较函数进行排序，比如你按顺序插入 2、3、1，它内部会自动排序成 1、2、3。
相比数组，它不能用索引来访问元素值，只能通过迭代器访问元素值。

在C++里，std::set 的比较函数是可以自定义的，但火山的模板类无法实现自定义函数，只能按照从小到大排序，也无法针对性处理一些自定义类型。

无序哈希集（std::unordered_set），在插入值的时候会计算值的哈希值，通过该哈希值能快速找到要访问的值。
对于整数等基本类型，库的默认哈希函数自然能处理，例外的是文本型和字节集类，所以在「对象无序哈希集模板类」中使用了自定义的哈希函数，因为这个哈希函数的限制，你要封装其他类型，就要自己实现对应的哈希函数。

最后来个总结，有序和无序哈希集都有去重的作用，其中哈希集能同时实现排序功能。

插入速度上，理论上是无序比有序慢，因为哈希函数的耗时通常大于比较函数。
访问速度上（火山里的「是否存在」和「删除」方法），理论上是无序比有序快，因为只需要对检查的值进行哈希，然后通过哈希值就能到达要访问的值，而有序往往会从头到尾比较寻找要访问的值。

当然，在某些情况下，两者各自拥有的速度优势也不是绝对的。

作者: 龙纹 时间: 2023-3-7 12:37

Xelloss0618 发表于 2023-3-7 11:35
上面龙纹把火山里的哈希表当成哈希集了，火山里的哈希集是 std::set，无序哈希集是 std::unordered_set。
...

我看错字了...看成哈希表了，所以解释的也是哈希表，哈希集其实是手误，我改正一下。

欢迎光临递归火山软件开发平台 (https://bbs.voldp.com/)