引言

这是个系列文章，会通过分析源码，从数据结构层面来分析UE4/UE5中的几种基本容器：TArray、TSparseArray、TBitArray、TSet、TMap、TMultiMap，并与传统实现方案进行比较。

本文基于的源码版本是UE5 release 5.0.0。不过源码与UE4对比过基本一致，可通用。

本文作为系列文章的第二篇，会分析TSet、TMap、TMultiMap的实现。

数据结构是程序员的基本功，因此本文不会赘述教科书上人尽皆知的概念，只会从UE4/UE5的基本容器的特色机制出发来分析其具体实现。

TSet

上一篇文章中，详细分析了TSparseArray的机制。TSparseArray在UE5的哈希结构（TSet、TMap）中，有着重要的应用，也是TSet的底层容器。

TSet的功能与std::set类似，用于查询某个元素是否已经位于set容器中。std::set使用红黑树来进行查询，并且由于红黑树的性质可以天然保证遍历的有序性。std::unordered_set则使用哈希表来实现，无法保证有序性。

而UE的TSet容器，不仅仅使用哈希表来进行查询来保证的查询效率，还能支持排序并且按顺序遍历！！这在很大程度上，也要归功于TSet使用的特殊设计。

TSet内部成员结构

我们先来看TSet内部的成员变量：

1
2
3
4
5
6
7
8
9
10
11
12
// 为了方便注释，调整了一下声明顺序

// 实际存储的元素内容，由于使用了SparseArray，因此可以认为是在连续内存上。
typedef TSparseArray<SetElementType,typename Allocator::SparseArrayAllocator>     ElementArrayType;
ElementArrayType Elements;

// 存储每个哈希值在Elements上的索引。
typedef typename Allocator::HashAllocator::template ForElementType<FSetElementId> HashType;
mutable HashType Hash;

// 当前hash部分的总大小。需要保证是2的幂次方，用于快速取模
mutable int32    HashSize;

Elements是一个数组，存储添加进哈希表的元素。这个数组存储的元素类型为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename InElementType, bool bTypeLayout>
class TSetElementBase
{
public:
    typedef InElementType ElementType;
    
    // ... 默认构造函数声明

    /** The element's value. */
    ElementType Value;

    // 如果发生哈希冲突，链表上的下一个HashId
    /** The id of the next element in the same hash bucket. */
    mutable FSetElementId HashNextId;

    // 当前元素对应在Hash部分的索引
    /** The hash bucket that the element is currently linked to. */
    mutable int32 HashIndex;
};

而Hash也是一个数组，存储了每个元素的KeyHash所对应的在Elements数组中的索引。其核心数据类型如下（其实就一个Index）：

1
2
3
4
5
6
7
8
9
10
class FSetElementId
{
    // ... 各种函数定义

private:
    
    // 存储在Elements数组中的索引
    /** The index of the element in the set's element array. */
    int32 Index;
}

从TSet的内部成员变量的结构可以分析出，其与传统的哈希表的结构有一个较大的不同，不是直接用哈希值查找元素，而是先查找索引，再根据索引来查找元素。

Find元素

其查找流程先用一个简要流程图来描述：

image.png

其核心流程全部在FindId()函数中。有一点需要注意的是：

Hash数组并不管哈希冲突。实际哈希冲突的处理放在Elements数组的元素中。

总体查找流程与传统的哈希表相似，计算哈希 -> 在哈希桶中找到元素 -> 遍历比较 -> 返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
FORCEINLINE FSetElementId&amp; GetTypedHash(int32 HashIndex) const
{
    // HashSize永远是2的幂次方。因此这里相当于快速取模
    // 这里直接通过对HashIndex取模得到ElementId索引，哈希冲突留到外部解决
    return ((FSetElementId*)Hash.GetAllocation())[HashIndex &amp; (HashSize - 1)];
}

/**
 * Finds an element with the given key in the set.
 * @param Key - The key to search for.
 * @return The id of the set element matching the given key, or the NULL id if none matches.
 */
FSetElementId FindId(KeyInitType Key) const
{
    if (Elements.Num())
    {
        // 这里KeyFuncs::GetKeyHash(Key)会将传入的元素类型通过哈希函数转换为一个int32
        // GetTypedHash只负责找到Elements数组中的位置，不负责哈希冲突处理
        for(FSetElementId ElementId = GetTypedHash(KeyFuncs::GetKeyHash(Key));
            ElementId.IsValidId();
            ElementId = Elements[ElementId].HashNextId)
        {
            // 遍历HashBucket中的元素，如果找到则返回，否则继续比较桶中的下一个元素
            if(KeyFuncs::Matches(KeyFuncs::GetSetKey(Elements[ElementId].Value),Key))
            {
                // Return the first match, regardless of whether the set has multiple matches for the key or not.
                return ElementId;
            }
        }
    }
    return FSetElementId();
}

Add元素

添加元素会存在不同的情况：

  1. 如果元素已存在，那么替换元素

  2. 如果元素不存在，那么创建元素添加到Elements中，并且将ElementId与HashKey进行连接存储到Hash中。

用简要流程图来描述如下：

image.png

这里有两点可以注意：

  1. 入参使用了万能引用，意味着内部构造新对象时，可能使用拷贝构造，也可能使用移动构造。

  2. 内部实现即使是替换元素的分支，也会走先构造，再移动，再移除的逻辑。这个过程中，会走Memmove的操作。

其核心流程在Emplace函数中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename ArgsType>
FSetElementId Emplace(ArgsType&amp;&amp; Args, bool* bIsAlreadyInSetPtr = nullptr)
{
    // 直接使用传入的元素构造一个新的Element，可能使用拷贝构造或者移动构造
    // 这里会直接在Elements数组中构造一个新元素
    // Create a new element.
    FSparseArrayAllocationInfo ElementAllocation = Elements.AddUninitialized();
    SetElementType&amp; Element = *new (ElementAllocation) SetElementType(Forward<ArgsType>(Args));
    FSetElementId ElementId = ElementAllocation.Index;

    uint32 KeyHash = KeyFuncs::GetKeyHash(KeyFuncs::GetSetKey(Element.Value));
    if (!TryReplaceExisting(KeyHash, Element, ElementId, bIsAlreadyInSetPtr))
    {
        RehashOrLink(KeyHash, Element, ElementId);
    }
    return ElementId;
}

注意在上面的Emplace函数中，会直接在Elements数组中添加一个位置，并构造一个新元素。而如果走到了替换元素的分支，再走Move和删除的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool TryReplaceExisting(uint32 KeyHash, SetElementType&amp; Element, FSetElementId&amp; InOutElementId, bool* bIsAlreadyInSetPtr)
{
    // ... 一系列判断，替换核心逻辑如下
    
    // 对于Set中的一般情况，MoveByRelocate内部逻辑，会先执行Elements[ExistingId].Value的析构函数，再进行Memmove
    // If there's an existing element with the same key as the new element, replace the existing element with the new element.
    MoveByRelocate(Elements[ExistingId].Value, Element.Value);
    
    // 上一步已经执行了Memmove，因此直接将Elements中新创建的已经无效的Element移除
    // Then remove the new element.
    Elements.RemoveAtUninitialized(InOutElementId);
    
    // Then point the return value at the replaced element.
    InOutElementId = ExistingId;

    // ...
}

笔者在这里是有一些疑惑，理论上先FindExistingId，再根据其是否有效来决定是直接在原有地址上构造，还是构造新节点，这样是可以省去Memmove的开销的。可能考虑到代码复用的原因？

如果走到元素不存在的分支，那么代码很简单，就是将元素添加到HashBucket链表表头。

1
2
3
4
5
6
7
8
9
FORCEINLINE void LinkElement(FSetElementId ElementId, const SetElementType&amp; Element, uint32 KeyHash) const
{
    // Compute the hash bucket the element goes in.
    Element.HashIndex = KeyHash &amp; (HashSize - 1);
    
    // Link the element into the hash bucket.
    Element.HashNextId = GetTypedHash(Element.HashIndex);
    GetTypedHash(Element.HashIndex) = ElementId;
}

如何处理Hash冲突？

虽然TSet的哈希表结构使用了连续内存，但本质上还是一个开链法的哈希表。我们可以对传统开链法哈希表中的各实现做如下的转换：

传统开链法哈希表 TSet
堆 Elements分配器
桶数组 Hash数组
链表节点 Elements内部元素
链表节点记录地址 链表节点记录索引

这样转换之后，我们会发现其实现依然是一个开链法的哈希表！

因此，其处理哈希冲突的方法也和传统开链法一致，如果发现哈希冲突，构造一个节点，并添加到链表表头即可。

Remove元素

由于使用了开链法，删除元素的处理就比开放定址法简单很多。只需要将节点从链表中移除即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Remove(FSetElementId ElementId)
{
    if (Elements.Num())
    {
        const auto&amp; ElementBeingRemoved = Elements[ElementId];
        
        // 由于只记录了HashNextId，因此需要从链表头开始遍历查找
        // Remove the element from the hash.
        for(FSetElementId* NextElementId = &amp;GetTypedHash(ElementBeingRemoved.HashIndex);
            NextElementId->IsValidId();
            NextElementId = &amp;Elements[*NextElementId].HashNextId)
        {
            // 找到元素后，从链表中移除
            if(*NextElementId == ElementId)
            {
                *NextElementId = ElementBeingRemoved.HashNextId;
                break;
            }
        }
    }
    
    // 从Elements移除。由于是TSparseArray，因此是O(1)的时间复杂度
    // Remove the element from the elements array.
    Elements.RemoveAt(ElementId);
}

Rehash

任何哈希表的Rehash操作都是开销比较高的，TSet也不例外。Rehash流程需要清除Hash桶，并遍历所有的Elements，依次重新计算哈希，映射到Hash桶中。

Rehash目前只会在5种情况下调用：

  1. 添加元素时，需要的HashSize比当前HashSize大

  2. 执行Compact、Reserve等操作重新分配空间时。

  3. 排序之后。

  4. 当前空间过大，自动释放空间时

  5. 序列化之后，进行TSet的初始化

其源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/** Resizes the hash. */
void Rehash() const
{
    // Free the old hash.
    Hash.ResizeAllocation(0,0,sizeof(FSetElementId));

    int32 LocalHashSize = HashSize;
    if (LocalHashSize)
    {
        // 重新分配合适大小的HashBucket数组
        // Allocate the new hash.
        checkSlow(FMath::IsPowerOfTwo(HashSize));
        Hash.ResizeAllocation(0, LocalHashSize, sizeof(FSetElementId));
        for (int32 HashIndex = 0; HashIndex < LocalHashSize; ++HashIndex)
        {
            GetTypedHash(HashIndex) = FSetElementId();
        }

        // 遍历Elements所有元素，依次重新HashElement
        // Add the existing elements to the new hash.
        for(typename ElementArrayType::TConstIterator ElementIt(Elements);ElementIt;++ElementIt)
        {
            // ElementIt.GetIndex()返回当前Element在Elements数组中的下标。由于Rehash目的是重建Hash与Elements之间的关系，不需要改变Element的顺序
            // 只需要将Element.HashIndex重新设为正确的Hash桶索引，且重建链表关系即可
            HashElement(FSetElementId(ElementIt.GetIndex()),*ElementIt);
        }
    }
}

TSet的遍历

前文已经分析过TSparseArray的遍历。TSet的遍历则直接包装了Elements数组的遍历，与HashBuckets没有关系。

TSet的迭代器内引用了一个TSparseArray的迭代器，迭代器的自增函数也仅仅是调用TSparseArray迭代器的自增，再返回TSparseArray迭代器的解引用所得值。

1
2
3
4
5
6
7
8
9
10
FORCEINLINE TBaseIterator&amp; operator++()
{
    ++ElementIt;
    return *this;
}

FORCEINLINE ItElementType&amp; operator*() const
{
    return ElementIt->Value;
}

TSet能保证Add的顺序与遍历顺序一致吗？

不能。本质上是因为TSparseArray由于有空闲链表，每次Add之后都会返回一个索引，而遍历时是根据下标从小到大遍历，自身就无法保证Add的顺序与其遍历顺序一致。

但是有一种特殊情况。由于TSparseArray的Reserve函数实现方式，在分配控件之后，空闲链表的可用索引是从下标0开始依次往后递增的。因此对于一个新的TSet，可以保证在没有触发Rehash之前，其遍历顺序与Add顺序一致。

TSet的排序

可能很多同学熟悉传统的哈希表之后，会对TSet表示惊奇，TSet居然可以排序？？std::unordered_set也是哈希表，不都说是无序的吗？

实际上，传统哈希表无法进行排序的原因，是因为HashBuckets数组是由元素的哈希值来决定存放顺序的，元素有序并不意味着哈希值有序。如果想要排序的话怎么办呢？那就需要额外记录有序的元素的哈希值的顺序，遍历时读取这个有序哈希值数组，通过哈希值访问Value去进行遍历。

而你会发现，对于TSet的Elements与Hash分离的结构而言，天生就支持有序遍历！如果我们想要有序遍历TSet，只需要对Elements进行排序，然后进行一次Rehash，即可将“有序的元素的哈希值的顺序”记录在Element中。我们遍历时甚至不需要再通过哈希值去访问Value，而是直接遍历Elements数组即可。这样通过哈希值查找元素时，由于经历过Rehash，也不会影响添加、查找、删除等任何流程。

换种思路来说，传统哈希表无法进行有序遍历是因为在堆上申请内存是无序的。但是TSet的“堆”——Elements数组可以做到有序，这样就可以直接在“堆”上有序遍历元素。

排序代码如下：

1
2
3
4
5
6
7
8
9
template <typename PREDICATE_CLASS>
void Sort( const PREDICATE_CLASS&amp; Predicate )
{
    // Sort the elements according to the provided comparison class.
    Elements.Sort( FElementCompareClass< PREDICATE_CLASS >( Predicate ) );
    
    // Rehash.
    Rehash();
}

分析TSet的性能和内存优势

由于底层使用的是数组，且并未使用开链法，因此TSet的Elements排列非常紧密，能取得很高的内存占用率。另外排列紧密的另一个好处是对于缓存非常友好，能降低CacheMiss概率。使用链表法相比开放定址法，也降低了添加操作的耗时。另外，由于使用了TSparseArray，在TSet遍历时能取得较高的效率。

TMap

TMap作为UE5的字典结构，与TSet有着类似的功能，例如快速查找，添加、删除、更新健值对等。

利用TSet进行扩展

常见的使用set的结构来实现map的思想，就是将map的健值对组装成一个struct，这个struct使用其key来计算哈希，然后直接塞进set容器中即可。

例如一个简单的MapElement的实现如下：

1
2
3
4
5
6
7
8
9
10
struct FMapElement
{
    KeyType Key;
    ValueType Value;
}

inline uint32 GetTypeHash(const FMapElement&amp; Item)
{
    return GetTypeHash(Item.Key);
}

TMap也采用了类似的思想，不过其使用了一个更通用的模板类：TTuple。

TTuple是UE自己实现的类似于std::tuple的模板类，用于承载UE自己的元祖相关的代码。TMap便采用了TTuple作为其MapElement类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename KeyType, typename ValueType>
using TPair = TTuple<KeyType, ValueType>;

template <typename KeyType, typename ValueType, typename SetAllocator, typename KeyFuncs>
class TMapBase
{
    // ...
public:
    typedef TPair<KeyType, ValueType> ElementType;
    
protected:
    // ...
    typedef TSet<ElementType, KeyFuncs, SetAllocator> ElementSetType;
    
    /** A set of the key-value pairs in the map. */
    ElementSetType Pairs;
}

TTuple实现逻辑

TTuple是笔者在UE源码中见过的最复杂的模板元编程代码，没有之一。。这里尝试简单分析一下其实现原理和模板展开过程：

首先看TTuple类定义：

1
2
3
4
5
template <typename... Types>
struct TTuple : UE::Core::Private::Tuple::TTupleBase<TMakeIntegerSequence<uint32, sizeof...(Types)>, Types...>
{
    // ...
}

这里上来就使用了TMakeIntegerSequence类。这是UE自己包装的IntegerSequence功能，底层也是直接桥接了编译器内置的__make_integer_seq。其作用是接收一个类型模板参数和一个数字N，会在编译期自动将N...转为生成0, 1, ..., N-1的模板代码。（可以参考C++14的std::make_integer_sequence功能）

例如这里我们传入的定义是：

1
2
template <typename KeyType, typename ValueType>
using TPair = TTuple<KeyType, ValueType>;

因此这里sizeof...(Types)就是2，因此TTupleBase<TMakeIntegerSequence<uint32, sizeof...(Types)>, Types...>这行代码，会自动展开生成：

1
TTupleBase<TMakeIntegerSequence<uint32, 2>, KeyType, ValueType>

我们可以找到TTupleBase的定义为：

1
2
template <uint32... Indices, typename... Types>
struct TTupleBase<TIntegerSequence<uint32, Indices...>, Types...> : TTupleBaseElement<Types, Indices, sizeof...(Types)>...

这里TIntegerSequence<uint32, Indices...>会接收TMakeIntegerSequence<uint32, 2>的参数，会展开为0和1来生成两份代码。注意这里变长模板形参展开在TTupleBaseElement<Types, Indices, sizeof...(Types)>外部，因此这里会进行多继承，并将每一个展开的类都作为自己的父类。因此这里会展开为：

1
struct TTupleBase<TIntegerSequence<uint32, Indices...>/* 只是为了展开 */, KeyType, ValueType> : TTupleBaseElement<KeyType, 0, 2>, TTupleBaseElement<ValueType, 1, 2>`

由于该struct并不包含虚函数，自身也没有数据，因此多继承的两个父类内部的数据会默认平铺的方式包含在该TTuple中。

而TTupleBaseElement只有两种实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T, uint32 Index, uint32 TupleSize>
struct TTupleBaseElement
{
    // ...

    T Value;
};

template <typename T>
struct TTupleBaseElement<T, 0, 2>
{
    // ...

    T Key;
};

即TTuple<KeyType, ValueType>和我们实现的FMapElement结构体在内存结构和用法上都是一样的！

根据TTuple获取KeyHash

这部分实现在类TDefaultMapKeyFuncs中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/** Defines how the map's pairs are hashed. */
template<typename KeyType, typename ValueType, bool bInAllowDuplicateKeys>
struct TDefaultMapKeyFuncs : BaseKeyFuncs<TPair<KeyType, ValueType>, KeyType, bInAllowDuplicateKeys>
{
    typedef typename TTypeTraits<KeyType>::ConstPointerType KeyInitType;
    typedef const TPairInitializer<typename TTypeTraits<KeyType>::ConstInitType, typename TTypeTraits<ValueType>::ConstInitType>&amp; ElementInitType;
    
    // 外部会通过KeyFuncs::GetSetKey来获取参与哈希计算的元素，这里直接返回Element.Key，表示使用TTuple.Key来进行哈希运算
    static FORCEINLINE KeyInitType GetSetKey(ElementInitType Element)
    {
        return Element.Key;
    }
    
    // 外部会通过KeyFuncs::GetKeyHash来计算哈希值。
    static FORCEINLINE uint32 GetKeyHash(KeyInitType Key)
    {
        return GetTypeHash(Key);
    }
    
    // ... 其它函数
}

既然TMap底层也使用了TSet，TSet拥有的功能TMap也都有，并且也能支持KeySort和ValueSort、按顺序遍历等操作。

分析TMap的性能和内存占用优势

性能方面，TMap由于组合使用了TSet，因此具有TSet的一切优点。除此之外，TPair类型的使用，使得Key和Value在内存上排列在一起，而TMap通过Key查找Value，或者遍历，都是非常常见的操作，Key和Value内存上紧密排列能大大提高缓存命中率，进而提升性能。

TMultiMap

TMap只支持一对一的查询，但是实际使用中往往需要一对多的查询（例如ObjectHash中使用了大量的MultiMap，来支持通过某个UClass查询其所有的UObject的龚梦）。这种情况要怎么办呢？

可能很容易想到的一种方案是嵌套，Key依然是Key，Value使用一个数组，类似于：TMap<KeyType, TArray<ValueType>>。这样功能确实没问题，但是会存在非常严重的性能开销和内存浪费。那UE直接实现了这种容器，它是怎么做的呢？

其实TMultiMap和TMap在定义上的差别，只有在ContainersFwd.h中定义时的差别：

1
2
template<typename InKeyType, typename InValueType, typename SetAllocator = FDefaultSetAllocator, typename KeyFuncs = TDefaultMapHashableKeyFuncs<InKeyType, InValueType, false> > class TMap;
template<typename KeyType, typename ValueType, typename SetAllocator = FDefaultSetAllocator, typename KeyFuncs = TDefaultMapHashableKeyFuncs<KeyType, ValueType, true > > class TMultiMap;

注意，只有最后一个参数的true和false的差别！！

TMultiMap与TMap的差别

TDefaultMapHashableKeyFuncs在模板参数中有一个bInAllowDuplicateKeys，直接决定当前Map和Set是否允许重复的Key。这个参数的影响，其实只有三处会有差别：

  1. 在TryReplacingExisting时，如果允许重复Key的话，即如果是MultiMap的话，将永远不会去替换已存在的元素，而是构造新元素添加至Bucket链表中。

  2. 在RemoveImpl()实现中，如果不允许重复Key，那么在移除一个之后就会break，否则会重复移除所有匹配的元素。

  3. 在TMapBase::GetKeys()中，如果不允许重复Key，会预先使用Reserve分配返回数组大小，否则不会预分配（因为无法知道Key的数量）。

TMultiMap类为自己专门提供了MultiFind的接口，使用这个接口可以获取所有与Key匹配的Values作为数组通过引用形参返回。

其实现则再简单不过，根据Key，遍历HashBucket中的所有元素，只要Key匹配成功，就塞到返回数组中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template<typename Allocator> void MultiFind(KeyInitType Key, TArray<ValueType, Allocator>&amp; OutValues, bool bMaintainOrder = false) const
{
	for (typename Super::ElementSetType::TConstKeyIterator It(Super::Pairs, Key); It; ++It)
	{
		// 遍历到所有Key匹配的元素，都添加到OutValues中
		new(OutValues) ValueType(It->Value);
	}
	// ...
}

// 迭代器的代码如下：
template<bool bConst>
class TBaseKeyIterator
{
	// ...
	
	/** Advances the iterator to the next element. */
	FORCEINLINE TBaseKeyIterator&amp; operator++()
	{
		Id = NextId;

		while(Id.IsValidId())
		{
			NextId = Set.GetInternalElement(Id).HashNextId;
			checkSlow(Id != NextId);
			if(KeyFuncs::Matches(KeyFuncs::GetSetKey(Set[Id]),Key))
			{
				// 只有当匹配成功，才会停止循环。能让迭代器每次返回都能找到正确的值
				break;
			}

			Id = NextId;
		}
		return *this;
	}
}

总结

本文通过分析源码，简单介绍了TSet、TMap、TMultiMap几种UE常用容器的关键技术和实现原理。其实现既融合了传统数据结构的思想，并进行了优化，又融合了C++模板元编程的若干技巧。 至此，UE4/UE5的哈希表关联结构的容器就介绍完毕了。