请问无序哈希集是什么意思？

az3346

如题，请问无序哈希集对象 和普通的 哈希集对象 有什么区别呢？

小蜗牛

有序:顺序插入:1,2,3,4,5,6,7,8,9 更快
无序:随机插入:5,66,51,99,8,3   更快

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

创世魂

就是没有顺序吧

龙纹

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

Xelloss0618

上面龙纹把火山里的哈希表当成哈希集了，火山里的哈希集是 std::set，无序哈希集是 std::unordered_set。
诚如龙纹所说，只有 std::unordered_set 是跟哈希有关的，std::set 实际是红黑树。

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

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

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

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

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

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

龙纹

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

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