UE4/UE5的TSet和TMap

TSet和TMap是UE里面最常用的容器之一，和数组不同的是，元素本身并不连续存储，而是通过hash映射存储，因此相对于数组，查询元素是非常快速的。在之前的一篇文章里有提到，TSet是通过TSparseArray实现的，而TMap是通过TSet实现的。C++11也有类似的容器：std::unordered_set和std::unordered_map，实现也基本一致

TSparseArray本质上就是数组，只是元素不一定保证连续，可以产生间隙，所以TSet和TMap通过TSparseArray来实现，就也拥有了相同的特性。TSparseArray本身是通过index来索引的，而TSet和TMap在查询的时候，是通过Key的Hash来索引（TSet中元素的Key就是元素本身），那么TSet和TMap内部做的主要工作，肯定就是把Hash值映射到index上。下面来具体讲解：

TSet的实现

可以看到TSet一共有3个成员变量，Elements就是存储元素的结构，类型是TScriptSparseArray，这个实际就是不需要指定元素类型的TSparseArray。因为TSparseArray模板在实例化的时候，必须知道类型，而业务代码如果只是前向声明TSet，并没有定义Element类型时候，又因为使用TSparseArray作为内部容器，就会导致编译错误，这显然是不合适的，所以只能选择了TScriptSparseArray作为底板。UE在很多容器上都是使用类似技巧来做到类型的擦除，让容器的前向声明变得可以实现。这里可以不用关心太多的细节，其实只要清楚，这个容器保存了TSetElement，并且通过index来索引。TSetElement实际是个内部结构体，保存了元素本身以及一些额外的信息。如下：

其中Value就是元素本身，而HashNextId是Hash冲突时，下一个元素的位置，HashIndex是自己在Hash数组上的Index

而Hash的类型是ForElementType<FSetElementId>，可以简单认为就是个连续的FSetElementId数组即可。这个类型跟Allocator相关，因为默认使用的是HeapAllocator，所以其实是new出来的连续的FSetElementId数组，如果自己手动使用FixedAllocator，那么可能就是代码作用域内/函数栈上的FSetElementId数组。这里也只需要清楚Hash保存了FSetElementId，而这个FSetElementId是什么呢？

其实就是上面Elements的index。这里你肯定会说，为什么要中转一层，直接用Hash值作为index不就好了？这是因为Elements本身是一个有限大小的容器，而hash值并不是，怎样把一个hash值映射到index上呢，答案在这里：

(实际的Hash值) & (HashSize - 1)，其实是对Hash取余的快速操作，等价于%HashSize。如果没有学过数据结构，没自己实现过HashMap，肯定不清楚这是什么意思，这里简单科普一下。自己实现HashMap的时候，有一个问题就是怎样把一个任意数字，映射到有限的范围内，最简单做法就是取余。而这里为什么说是快速操作呢？这是因为TSet和TMap在分配内存时，当需要扩容，就会把容量翻一倍，也就是说TSet和TMap的容量总是1，2，4，8，16，32...这样的大小，那么在做index映射时，& (HashSize - 1)就是取低位，就等价于%1，%2，%4，%8，而计算机的&操作要比取余%快多了，所以写成了这样，这里要注意等价的前提是HashSize要是2的倍数。

因为把很大的Hash值映射到了有限的范围内，那一定有概率发生Hash冲突，UE的解决办法是先不管冲突，拿到index访问TSetElement。前面说了TSetElement的结构：

先比较Value，如果Value并不是想要的那个Value，也就是冲突了，就通过内部HashNextId，访问下一个TSetElement。可以看Find代码，就是这样实现的。

GetSetKey以及Matches默认实现，间接包一层可以方便业务自己修改，这样会更灵活。

那么，HashNextId是怎样生成的呢？

ReHash就不说了，其实就是容量不够了，先把容量翻倍，把所有元素的Hash值重新算一遍，这样新的Hash值也会一起算好。如果没扩容，就会调用LinkElement。

可以看到，下一个值就是取当前HashIndex值的Hash。这确实是一个办法，但是思考一个问题，假如容器的容量为1，这里就变成了自己的Next指向自己的一个链表，假如取值发现不匹配，就会取下一个，但下一个还是自己，也就是FindId函数会死循环，会这样吗？

答案是不会。这里还是看上面的LinkElement。

在什么元素都没有的时候，GetTypeHash(Element.HashIndex)，其实就是GetTypeHash(0)，当还没有给Hash的0号位赋值时，其实内部的Index并不是0，而是-1，所以上面的代码会将-1赋值给HashNextId，那么查询第一次就会停止。

为什么要专门提这一点呢？因为这里UE写的非常晦涩，但这又是一个非常关键的细节，之前我的项目中碰到过这里的BUG，就是因为有人随手加了一个内存置空（好像是Memzero）引发的死循环血案。因此对于UE的容器，在做置空等操作的时候，即使知道内部结构，也不要自信的在外部做任何内存相关操作，一定要使用提供的Empty或Reset等函数处理。

TMap的实现

TMap只有一个成员变量，Pairs。可以看到类型就是TPair作为元素的TSet，而TPair就是只有两个元素Key-Value的TTuple，关于TTuple这里不细说，其实就可以认为是两个元素的结构体。等价于

而在计算Hash的时候，只计算Key的Hash

前面说了，Set在这几个计算Hash的函数没有直接计算，而是中转了一层，可以让外层修改默认的方法，TMap就利用上了这个特性，复用TSet代码实现，简单的完成了功能。因此具体内部实现就不用多说了。

排序

TSet和TMap是支持排序的，如果你用过C++的unordered_set或unordered_map，你可能会觉得很震惊，一个本身通过hash索引的无序容器，名字都叫unordered，还能排序？这就是UE4这两个容器最有特色的地方。其实实现非常简单，前面也说了，因为内部实现本身是TSparseArray，迭代的时候是包装的TSparseArray迭代器进行访问的，而TSparseArray肯定是可以排序的，又因为Hash数组保存的是hash到index的映射，那么只要在排序后重新Rehash一遍，就完成了排序功能。

所以，UE的这两个容器，即可以排序，又可以快速查找，游戏业务用起来就真的非常爽了。

操作

这些就没什么需要多说的了，具体可以自行看源码，我这里把函数大致列了一下

TSet和Map都有的函数

TSet函数

需要额外提几点：

1. 访问可能不存在的元素时。不要先判断Contain再Find取值或通过[]取值，这样内部会进行两次查询，虽然本身不影响逻辑执行，但效率会低一些，较好的做法是直接Find并对结果判空即可。插入可以直接使用FindOrAdd一次完成修改或插入。
2. 不要Contain或Find后再Remove，原因和上面一样也是会查询两遍，如果不需要Remove的元素内容，就直接Remove，会返回Remove的个数，如果不存在个数会为0。如果需要Remove的元素内容，可以使用RemoveAndCopyValue，会把值拷到参数提供的变量上。
3. 使用迭代器遍历中可以删除，删除要使用迭代器提供的RemoveCurrent函数，按照下面的方式写，不用考虑遍历中删除问题，UE的容器已经解决好了这个麻烦。

因为UE的容器，都实现了begin()，end()，所以支持C++的range-for语法，可以放心使用：