UE4的TMap实现原理

TMap的成员ElementSetType是TSet类型,此TSet的成员是

1
TTuple<Key, Value>

TSet类由两个动态数组组成,一个用于Hash表,一个是TSparseArray。

先说TSparseArray,其成员Data是TArray类型,即动态数组,TSparseArray的特点是通过空闲成员内部指针将空闲成员链起来,这样可方便增加删除操作,但其中的增加操作的Index是无法预先指定的。

所以TSet类又用到了一个动态数组用于Hash表,这样可以计算Hash Key找到指定Hash表项,这个表项存的是Hash桶的最后一个入桶的成员在TSparseArray数组中的Index,而其它相同Hash Key的桶成员都在最后入桶成员结构内部链起来了。