Optimizing Lookups Using TMap and TSet

In this lesson, you will learn how to replace slow, iterative search operations with instantaneous lookups using the TMap and TSet containers.

The Problem with Iteration

When you store game data in a TArray, finding a specific element—like checking if a player owns a specific UInventoryItem*—requires a linear search. You must loop through every element until you find a match, which results in $O(N)$ time complexity. As your inventory or entity list grows, this becomes a major performance bottleneck.

Enter Hashed Containers

TMap and TSet solve this using a process called hashing. Instead of checking every item, these containers take a "key" and transform it into a numerical index. This allows the engine to jump directly to the memory address where the item lives, achieving $O(1)$ constant-time lookup.

• TSet: Use this when you only need to store unique items and quickly check if an item exists (e.g., "Is this specific player in my 'ActivePlayers' list?").
• TMap: Use this when you need to associate a key with a value (e.g., mapping a PlayerID to a PlayerScore).

Hashing Custom Types

To use UObject pointers or custom UStructs as keys, Unreal needs to know how to generate that hash. For UObject pointers, this is handled automatically. For custom UStructs, you must provide a GetTypeHash function:

uint32 GetTypeHash(const FMyCustomStruct& Thing)
{
    // Combine hashes of members to ensure uniqueness
    return HashCombine(GetTypeHash(Thing.ID), GetTypeHash(Thing.Category));
}

// Usage
TSet<FMyCustomStruct> UniqueItems;
UniqueItems.Add(MyStructInstance);
if (UniqueItems.Contains(MyStructInstance)) { /* Instant lookup! */ }

Managing Overhead

While hashing is fast, it isn't "free." The engine performs a calculation every time you add or look up an item. Only use TMap and TSet when you have a significant number of items or perform frequent lookups; for very small lists (e.g., 3–5 items), a TArray is often faster due to better memory locality and zero hashing overhead.

Key Takeaway: Use TMap and TSet to trade a small amount of hashing overhead for O(1) constant-time lookups, drastically improving performance in systems with large, frequently searched datasets.